Succinct vs Compacting de Bruijn Graphen

Question

Ich bin nicht so Experte in dem Thema, also bitte nehmen Sie das in Betracht, während Sie antworten.

Ich las zwei Papiere
Succinct de Bruijn Graphs
und
Compacting de Bruijn graphs from sequencing data quickly and in low memory

Ich konnte die Differenz zwischen diesen beiden Verfahren nicht verstehen, so wenden Sie sich bitte helfen kann mir jemand den Unterschied zwischen den beiden Algorithmus zu verstehen? oder schlagen Sie weiter vor, um zwischen beiden zu unterscheiden.

Gibt es eine Implementierung in Java für die Prägnante de Bruijn Graphen (der Autor schrieb ein in Python) oder jede andere effiziente Sprache

Vielen Dank im Voraus.

Answer 1

A kompaktiert de Bruijn Graph ist ein anderes Objekt als ein de Bruijn Graph. Im letzteren Fall sind alle Knoten k-mers (der Länge k), und im ersteren werden Knoten durch Pfadkomprimierung des ursprünglichen de Bruijn-Graphen erzeugt. Daher haben die Knoten im komprimierten Graphen die Länge k oder größer.

Pfadkomprimierung bedeutet in diesem Zusammenhang, dass jeder Pfad maximaler Länge, bei dem interne Knoten einen Nachbarn und einen Nachbarn haben, auf einen einzigen Knoten reduziert wird.

Während ich sagte, dass beiden Graphen verschieden sind, sie repräsentieren dennoch genau die gleichen Informationen (die einen Satz von k-mers ist), so informell verweisen wir oft auf den „de Bruijn Graph“ für eine von ihnen.

Eine präzise Darstellung (für eines dieser Objekte) bezieht sich auf eine Datenstruktur, die wenig Speicher verwendet.

Ich bin nicht bewusst, eine Java-Implementierung von sDBGs, aber es ist auf in C++: https://github.com/cosmo-team/cosmo