Domanda:
Come fare una distinzione tra il grafo "classico" di de Bruijn e quello descritto negli articoli di NGS?
Leo Martins
2017-05-19 15:32:45 UTC
view on stackexchange narkive permalink

In Computer Science un grafo De Bruijn ha (1) m ^ n vertici che rappresentano tutte le possibili sequenze di lunghezza n su simboli m e (2) bordi diretti che collegano nodi che differiscono per uno spostamento di elementi n-1 (il successore che ha il nuovo elemento a destra).

Tuttavia in Bioinformatica mentre la condizione (2) è preservata, quello che viene chiamato un grafo di De Bruijn non sembra rispettare la condizione (1). In alcuni casi il grafico non assomiglia affatto a un grafico di de Bruijn (ad esempio http://genome.cshlp.org/content/18/5/821.full).

Quindi la mia domanda è: se voglio rendere esplicito che sto usando l'interpretazione bioinformatica di un grafo di de Bruijn, c'è un termine per questo? Qualcosa come "grafo di de Bruijn semplificato", "proiezione di un grafo di de Bruijn" o "grafo di k-meri vicini"? Ci sono documenti che fanno questa distinzione o ho sbagliato tutto?

Fondamentalmente la condizione 1 significa che anche i vertici senza bordi dovrebbero essere presenti nel grafo, giusto?
Voglio dire, mi chiedo se qualche implementazione non bioinformatica del grafico di De Bruijn li memorizzi effettivamente, dal momento che non contengono alcuna informazione utile.
C'è un'altra differenza nei grafici di De Bruijn usati per l'assemblaggio del genoma: i bordi sono ponderati.
Ciao @Slim re. D1, credo che i grafici di de Bruijn siano collegati (un componente). Puoi crearli semplicemente fornendo `m` e` n` (http://mathworld.wolfram.com/deBruijnGraph.html). Q2: sì, le implementazioni non richiedono tutti i nodi; Il grafico di de Bruijn è un'entità astratta, una struttura combinatoria, come un "grafo completo". Ma se il mio grafico molto importante manca di alcuni bordi (b / c inutile) non posso chiamarlo "completo". Non lo rende meno importante BTW! Q3: è vero! Grazie per aver modificato la domanda.
Tre risposte:
#1
+7
Leo Martins
2017-05-23 01:33:56 UTC
view on stackexchange narkive permalink

Diversi articoli hanno fatto questa distinzione, e alcuni in effetti usano termini diversi per distinguerli. Ad esempio, Kazaux et al. (2016) riconoscono che:

Questi vincoli favoriscono l'uso di una versione del grafico di de Bruijn (dBG) dedicata all'assemblaggio del genoma - una versione che differisce dalla struttura combinatoria inventata di NG de Bruijn.

Kingsford et al. (2010) riconoscono anche la distinzione:

Si noti che questa definizione di grafo di de Bruijn differisce dalla definizione tradizionale descritta nella letteratura matematica negli anni '40 che richiede che il grafo contenga tutte le stringhe di lunghezza k che possono essere formate da un alfabeto (piuttosto che solo quelle stringhe presenti nel genoma).

Il riferimento più antico che ho trovato per un termine specifico per riferirsi alla struttura correlata all'assemblaggio è Skiena e Sundaram (1995), dove lo chiamano sottografo del digrafo di de Bruijn . Successivamente, nel 2002, Błażewicz et al. lo chiameranno un sottografo indotto da de Bruijn . Il termine sottografo di de Bruijn è anche formalmente definito nella tesi di Quitzau (2009). Lì, e anche nell'articolo ( Quitzau e Stoye, 2008) gli autori descrivono il grafo di sequenza come una modifica del sottografo di de Bruijn sparse (comunemente usato nei problemi di assemblaggio) , dove i percorsi non ramificati sono sostituiti da un singolo vertice. Il termine grafo di Bruijn sparse è utilizzato anche da Chauve et al. (2013).

Un altro termine che ho trovato è stato word graph , descritto sia da Malde et al. (2005) e da Heath e Pati (2007) come sottografo o come generalizzazione di un grafico di de Bruijn. Rødland (2013) riassume alcuni dei termini utilizzati per questa struttura di dati:

La struttura dei dati è meglio compresa nei termini della rappresentazione del sottografo di de Bruijn di S [k]. (...) Alcuni autori potrebbero riferirsi a questo come a un grafico di parole, o anche solo un grafico di de Bruijn.

Anche se possiamo riconoscere che la distinzione non è molto rilevante, la domanda è chiedendo specificamente la situazione in cui si vuole fare una tale distinzione.

Come molti giornali e io stesso abbiamo detto, il grafo di Assembly de Bruijn è solo un sottografo dell'intero grafo di de Bruijn. Chiunque dica in modo diverso non riconosce questa semplice relazione. Il "grafico della sequenza" è troppo generico e viene utilizzato in un altro contesto (ad esempio, il grafico dell'assemblaggio della sequenza). "Sparse de Bruijn graph" è più appropriato per un grafo costruito saltando alcuni k-meri nelle letture (es. In sparse assembler). Directed Acyclic Word Graph (DAWG) è un concetto preesistente, almeno risalente agli anni '80, che rende ambiguo anche il "word graph". Le persone dovrebbero smetterla di inventare nuovi nomi per un sottografo.
Pevzner ha svolto un lavoro fondamentale nell'uso dei grafici di de Bruijn in assembly (http://www.pnas.org/content/98/17/9748.full) e nello splicing alternativo (https://www.ncbi.nlm.nih.gov/ pubmed / 12169546)
#2
+4
holmrenser
2017-05-19 16:07:00 UTC
view on stackexchange narkive permalink

Oltre al normale grafico di De Bruijn come illustrato su wikipedia, alcune implementazioni in bioinformatica presentano un'elaborazione aggiuntiva. Immagino che la ragione principale per cui la figura 1 nel documento che hai collegato (riguardante l'assemblatore del genoma di Velvet) sia leggermente diversa è che un nodo rappresenta una serie di k-meri sovrapposti . Per visualizzarlo come un grafo De Bruin più classico dovresti collegare i k-mers raffigurati sopra i nodi. La didascalia accanto alla figura uno descrive l'elaborazione in modo abbastanza chiaro.

Secondo la tua ultima domanda: non credo che ci sia una "interpretazione bioinformatica di un grafico di De Bruijn". Esistono diverse implementazioni, tutte con specifiche. Quindi sarebbe meglio fare riferimento all'attuale implementazione.

Ad esempio: questo è un bel documento su come costruire un grafico De Bruijn pan-genoma di più genomi simultaneamente .

Ma una "implementazione" di un grafo di de Bruijn che non include tutti i k-mers non è più un grafo di de Bruijn (nel senso originale), giusto? Se l'implementazione non soddisfa la condizione (1) di cui sopra, mi chiedo se viene utilizzato un altro nome (o un qualificatore).
Sono abbastanza sicuro che tutti i k-meri originali siano presenti in qualche forma.
#3
+3
user172818
2017-05-19 19:14:34 UTC
view on stackexchange narkive permalink

Per prima cosa supponiamo che il DNA abbia solo un filamento. Un grafo di de Bruijn assieme è un sottografo di un grafo di de Bruijn completo. Contiene un vertice u se u è un k-mer nelle letture; contiene un arco u-> v, se ue v sono k-meri adiacenti in una lettura. In alternativa, notiamo che un arco u-> v è rappresentato da un (k + 1) -mer. Un grafo di de Bruijn di assemblaggio può essere considerato un arco di sottografo indotto da tutti i (k + 1) -mers nelle letture - infatti, alcuni assemblatori prendono la lista di (k + 1) -mer come una rappresentazione succinta dei grafi di de Bruijn.

Il DNA ha due filamenti. Dobbiamo solo indurre un grafo di assemblaggio di Bruijn da tutti i (k + 1) -meri e il loro complemento inverso. È ancora un sottografo di un grafo di de Bruijn completo.

Perché un grafo di de Bruijn di assemblaggio è solo un sottografo. Non è necessario dargli un nuovo nome.

PS: ho cancellato la mia vecchia risposta perché non era quello che chiedevi in ​​base ai tuoi commenti. Mi ha confuso il tuo accenno al velluto. Velvet utilizza una rappresentazione equivalente ma non comune dei grafici di de Bruijn, il che complica la tua domanda.



Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 3.0 con cui è distribuito.
Loading...