Frage:
Wie kann man zwischen dem "klassischen" de Bruijn-Graphen und dem in NGS-Papieren beschriebenen unterscheiden?
Leo Martins
2017-05-19 15:32:45 UTC
view on stackexchange narkive permalink

In der Informatik hat ein De Bruijn-Graph (1) m ^ n Eckpunkte, die alle möglichen Sequenzen der Länge n über darstellen m -Symbole und (2) gerichtete Kanten, die Knoten verbinden, die sich durch eine Verschiebung von n-1 -Elementen unterscheiden (der Nachfolger hat das neue Element rechts).

Während in der Bioinformatik die Bedingung (2) beibehalten wird, scheint das sogenannte De Bruijn-Diagramm die Bedingung (1) nicht zu berücksichtigen. In einigen Fällen sieht das Diagramm überhaupt nicht wie ein De-Bruijn-Diagramm aus (z. B. http://genome.cshlp.org/content/18/5/821.full).

Meine Frage lautet also: Wenn ich deutlich machen möchte, dass ich die Bioinformatik-Interpretation eines de Bruijn-Graphen verwende, gibt es einen Begriff dafür? So etwas wie "vereinfachter de Bruijn-Graph", "Projektion eines de Bruijn-Graphen" oder "Graph benachbarter k-mers"? Gibt es Papiere, die diese Unterscheidung treffen, oder habe ich alles falsch verstanden?

Grundsätzlich bedeutet die Bedingung 1, dass auch kantenlose Eckpunkte im Diagramm vorhanden sein sollten, oder?
Ich meine, ich frage mich, ob eine nicht-bioinformatische Implementierung des De Bruijn-Graphen sie tatsächlich speichert, da sie keine nützlichen Informationen enthalten.
Es gibt noch einen Unterschied bei den De Bruijn-Graphen, die für die Genomassemblierung verwendet werden: Die Kanten werden gewichtet.
Hallo @Slim re. Q1, ich glaube, de Bruijn-Graphen sind miteinander verbunden (eine Komponente). Sie können sie einfach erstellen, indem Sie "m" und "n" angeben (http://mathworld.wolfram.com/deBruijnGraph.html). F2: Ja, Implementierungen benötigen nicht alle Knoten. Der de Bruijn-Graph ist eine abstrakte Einheit, eine kombinatorische Struktur, wie ein "vollständiger Graph". Aber wenn mein sehr wichtiger Graph einige Kanten verfehlt (b / c nutzlos), kann ich ihn nicht als "vollständig" bezeichnen. Es macht es übrigens nicht weniger wichtig! Q3: das stimmt! Vielen Dank für die Bearbeitung der Frage.
Drei antworten:
#1
+7
Leo Martins
2017-05-23 01:33:56 UTC
view on stackexchange narkive permalink

Mehrere Artikel haben diese Unterscheidung getroffen, und einige verwenden tatsächlich unterschiedliche Begriffe, um zwischen ihnen zu unterscheiden. Zum Beispiel haben Kazaux et al. (2016) bestätigen Folgendes:

Diese Einschränkungen begünstigen die Verwendung einer Version des De-Bruijn-Graphen (dBG) für die Genomassemblierung - eine Version, die sich von der erfundenen kombinatorischen Struktur unterscheidet von NG de Bruijn.

Kingsford et al. (2010) erkennen auch die Unterscheidung:

Beachten Sie, dass diese Definition eines De-Bruijn-Graphen von der traditionellen Definition abweicht, die in der mathematischen Literatur in den 1940er Jahren beschrieben wurde und die den Graphen enthalten muss Alle Zeichenfolgen der Länge k, die aus einem Alphabet gebildet werden können (und nicht nur die im Genom vorhandenen Zeichenfolgen).

Die älteste Referenz, die ich für einen bestimmten Begriff gefunden habe, um sich auf die montagebezogene Struktur zu beziehen, ist Skiena und Sundaram (1995), wo sie als Untergraph des Digraphen von de Bruijn . Später, im Jahr 2002, wird Błażewicz et al. Es als de Bruijn-induzierten Subgraphen bezeichnen. Der Begriff de Bruijn-Subgraph ist auch in Quitzaus These (2009) formal definiert. Dort und auch in dem Artikel ( Quitzau und Stoye, 2008) beschreiben die Autoren den Sequenzgraphen als eine Modifikation des spärlichen de Bruijn-Teilgraphen (häufig bei Montageproblemen verwendet). , wobei nicht verzweigte Pfade durch einen einzelnen Scheitelpunkt ersetzt werden. Der Begriff sparse de Bruijn graph wird auch von Chauve et al. (2013).

Ein anderer Begriff, den ich gefunden habe, war Wortgraph , beschrieben von Malde et al. (2005) und von Heath and Pati (2007) als Untergraph oder als Verallgemeinerung eines de Bruijn-Graphen. Rødland (2013) fasst einige der für diese Datenstruktur verwendeten Begriffe zusammen:

Die Datenstruktur lässt sich am besten anhand der de Bruijn-Subgraphendarstellung von S [k] verstehen. (...) Einige Autoren bezeichnen dies möglicherweise als Wortgraph oder auch nur als De-Bruijn-Graph.

Obwohl wir erkennen können, dass die Unterscheidung nicht sehr relevant ist, ist die Frage speziell nach der Situation fragen, in der man eine solche Unterscheidung treffen möchte.

Wie viele Zeitungen und ich bereits sagten, ist das Assembly de Bruijn-Diagramm nur ein Teilgraph des vollständigen de Bruijn-Diagramms. Wer etwas anderes sagt, erkennt diese einfache Beziehung nicht an. "Sequenzgraph" ist zu allgemein und wird in einem anderen Kontext verwendet (z. B. Sequenzassemblierungsgraph). "Sparse de Bruijn-Graph" ist besser geeignet für einen Graph, der durch Überspringen einiger k-mers in Lesevorgängen (z. B. in einem Sparse-Assembler) erstellt wurde. Directed Acyclic Word Graph (DAWG) ist ein bereits existierendes Konzept, das zumindest bis in die 80er Jahre zurückreicht und auch "Word Graph" mehrdeutig macht. Die Leute sollten aufhören, neue Namen für einen Untergraphen zu erfinden.
Pevzner hat bahnbrechende Arbeit bei der Verwendung von De-Bruijn-Graphen in der Montage (http://www.pnas.org/content/98/17/9748.full) und beim alternativen Spleißen (https://www.ncbi.nlm.nih.gov/) geleistet. pubmed / 12169546)
#2
+4
holmrenser
2017-05-19 16:07:00 UTC
view on stackexchange narkive permalink

Zusätzlich zu dem in der Wikipedia dargestellten regulären De Bruijn-Diagramm bieten einige Implementierungen in der Bioinformatik eine zusätzliche Verarbeitung. Ich denke, der Hauptgrund, warum Abbildung 1 in dem von Ihnen verlinkten Artikel (in Bezug auf den Velvet-Genom-Assembler) etwas anders ist, ist, dass ein Knoten eine Reihe überlappender k-mers darstellt. Um dies als klassischeres De Bruin-Diagramm zu visualisieren, müssten Sie die über den Knoten dargestellten k-mers verbinden. Die Beschriftung neben Abbildung 1 beschreibt die Verarbeitung recht deutlich.

Gemäß Ihrer letzten Frage: Ich glaube nicht, dass es eine 'bioinformatische Interpretation eines De Bruijn-Graphen' gibt. Es gibt verschiedene Implementierungen, die alle dort Besonderheiten haben. Daher ist es am besten, sich auf die tatsächliche Implementierung zu beziehen.

Als Beispiel: Dies ist ein schönes Papier darüber, wie ein Pan-Genom-De-Bruijn-Diagramm mehrerer Genome gleichzeitig erstellt wird .

Aber eine "Implementierung" eines De-Bruijn-Graphen, der nicht alle k-mers enthält, ist kein De-Bruijn-Graph (im ursprünglichen Sinne) mehr, oder? Wenn die Implementierung die obige Bedingung (1) nicht erfüllt, frage ich mich, ob ein anderer Name (oder ein Qualifizierer) verwendet wird.
Ich bin mir ziemlich sicher, dass alle originalen K-Mers in irgendeiner Form vorhanden sind.
#3
+3
user172818
2017-05-19 19:14:34 UTC
view on stackexchange narkive permalink

Nehmen wir zunächst an, dass die DNA nur einen Strang hat. Ein Assembly de Bruijn-Diagramm ist ein Teilgraph eines vollständigen de Bruijn-Diagramms. Es enthält einen Scheitelpunkt u, wenn u beim Lesen ein k-mer ist; es enthält eine Kante u-> v, wenn u und v bei einem Lesevorgang benachbarte k-mere sind. Alternativ stellen wir fest, dass eine Kante u-> v durch ein (k + 1) -mer dargestellt wird. Ein Assembler-de-Bruijn-Graph kann als Subgraph-Kante betrachtet werden, die von allen (k + 1) -Meren in Lesevorgängen induziert wird. Tatsächlich nehmen einige Assembler die Liste der (k + 1) -Mer als prägnante Darstellung von de-Bruijn-Graphen / p>

DNA hat zwei Stränge. Wir müssen nur einen Assemblierungs-de-Bruijn-Graphen aus allen (k + 1) -Meren und ihrem umgekehrten Komplement induzieren. Es ist immer noch ein Untergraph eines vollständigen de Bruijn-Diagramms.

Da ein Assembly de Bruijn-Diagramm nur ein Untergraph ist. Es ist nicht erforderlich, ihm einen neuen Namen zu geben.

PS: Ich habe meine alte Antwort gelöscht, da Sie aufgrund Ihrer Kommentare nicht danach gefragt haben. Ich war verwirrt, als Sie Samt erwähnten. Velvet verwendet eine äquivalente, aber ungewöhnliche Darstellung von de Bruijn-Diagrammen, was Ihre Frage kompliziert.



Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...