Zeitschrift für Data Mining in Genomics & Proteomics

Abstrakt

Suffix Graph - Ein effizienter Ansatz für Network Motif Mining

Rahul Nikam und Usha Chauhan

Ein Netzwerkmotiv ist ein Muster von Verbindungen, die in komplexen Netzwerken in deutlich höherer Anzahl auftreten als in ähnlichen randomisierten Netzwerken. Die grundlegende Voraussetzung für die Entdeckung von Netzwerkmotiven ist die Fähigkeit, die Häufigkeit der Teilgraphen zu berechnen. Um ein Netzwerkmotiv zu entdecken, muss man eine Teilgraphenzählung im ursprünglichen Netzwerk durchführen, die die Häufigkeit aller Teilgraphen eines bestimmten Typs berechnet. Dann muss die Häufigkeit einer Reihe von Teilgraphen im randomisierten ähnlichen Netzwerk berechnet werden. Der Engpass des gesamten Motiventdeckungsprozesses ist daher die Berechnung der Teilgraphenhäufigkeiten, und dies ist das zentrale Rechenproblem. Die vorgeschlagene Arbeit soll den Suffix-Graph vorstellen, eine Datenstruktur, die Graphen effizient speichert, und einen Algorithmus zum effizienten Abrufen von Teilgraphen entwickeln, der Netzwerkmotive erkennt und sie auf transkriptionelle Interaktionen in Escherichia coli anwendet.