Domanda:
Perché alcuni assemblatori richiedono un kmer di lunghezza dispari per la costruzione dei grafici di de Bruijn?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

Perché alcuni assemblatori come SOAPdenovo2 o Velvet richiedono una dimensione k -mer di lunghezza dispari per la costruzione del grafo di de Bruijn, mentre alcuni altri assemblatori come ABySS vanno bene con k -mers di lunghezza pari?

Due risposte:
#1
+28
Kamil S Jaron
2017-05-19 23:52:35 UTC
view on stackexchange narkive permalink

Dal manuale di Velvet:

deve essere un numero dispari, per evitare i palindromi. Se inserisci un numero pari, Velvet lo decrementerà e procederà.

i palindromi in biologia sono definiti come sequenze complementari inverse. Il problema dei palindromi è spiegato in questa recensione:

I palindromi inducono percorsi che si ripiegano su se stessi. Almeno un assemblatore li evita elegantemente; Il velluto richiede che K, la lunghezza di un K-mer, sia dispari. Un K-mer di dimensioni dispari non può eguagliare il suo complemento inverso.

È possibile costruire grafo con palindromi, ma allora l'interpretazione sarà più difficile. Consentire solo grafici di k -mers dispari è solo un modo elegante per evitare di scrivere un codice per l'interpretazione di un grafico più complicato.

Per evitare che qualcuno in futuro interpreti erroneamente questo, va notato che [palindrome] (https://en.wikipedia.org/wiki/Palindromic_sequence) in questo contesto ha un significato leggermente più specifico di quello che [normalmente sarebbe in inglese] (https : //en.wiktionary.org/wiki/palindrome).
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

Per espandere la risposta sopra, nel caso in cui non sia chiara, mostriamo:

  1. Perché le sequenze palindromiche devono essere di lunghezza pari
  2. Perché le sequenze palindromiche inducono cicli automatici in un grafico di de Bruijn
  3. Perché i cicli automatici in un grafico di de Bruijn sono problematici

1. Sequenza palindromica ⇒ la sequenza è di lunghezza pari

Idea: in un k-mer di lunghezza dispari, il suo nucleotide medio è 'capovolto' nel suo complemento inverso, quindi il due non possono mai essere uguali.

Supponi di avere una sequenza palindromica $ X $ . Quindi $ X $ è identico al suo complemento inverso, che chiameremo $ \ bar {X} $ .

Supponi che $ X $ sia di lunghezza dispari. Quindi ha la forma $ AbC $ , dove $ len (A) = len (C) = \ frac {len (X) -1} {2} $ e $ len (b) = 1 $ .

Quindi

$ X = \ bar {X} \ implies AbC = \ overline {AbC} = \ bar {C} \ bar {b} \ bar {A} $ span>

E quindi:

$ b = \ bar {b} $

( poiché $ len (A) = len (C) = len (\ bar {C})) $ . Ma questa è una contraddizione, poiché $ b $ è un singolo nucleotide e non può essere uguale al suo complemento. Quindi i k-meri di lunghezza dispari non possono formare palindromi.

Quindi la lunghezza di un k-mer che forma un palindromo deve essere pari.


2. Perché i k-mer palindromici inducono cicli automatici

Ogni nodo in un grafo di de Bruijn tradizionale è una stringa univoca, ma nella maggior parte delle implementazioni bioinformatiche ogni coppia di k-1-meri complementari inversa è identificata come un nodo singolo, ad esempio per $ k = 6 $ :

A palindromico k-mer (di $ k \ geq 2 $ ) ha la forma:

$ xAy $

dove $ len (A) = k-2 $ span>, $ x = \ bar {y} $ e $ A = \ bar {A} $ (possibilmente la stringa vuota).

Quindi contribuirà con due nodi nel grafo di de Bruijn:

  1. la sua sinistra k-1-mer $ xA $
  2. è corretto k-1-mer $ Ay $

E un vantaggio che va da 1 a 2.

Ma poiché questo k-mer è palindromico, $ xA = \ overline {Ay} $ e quindi questi due nodi sono inversamente complementari, e quindi lo "stesso" nodo, e quindi questo arco è un ciclo autonomo in questo nodo.


3. Perché i loop automatici sono problematici?

I loop automatici (se si verificano in un nodo con $ in \ _degree \ geq 2 $ e $ out \ _degree \ geq 1 $ ) aumenta il numero di possibili percorsi euleriani in un grafo di de Bruijn (o più specificamente, nel componente connesso contenente questo nodo, che rappresenta un contig , di cui possono essere multipli), poiché hai un possibile percorso euleriano aggiuntivo per ogni volta che attraversi questo nodo.

Ciò aumenta l'ambiguità nella lettura del grafico, poiché ogni possibile percorso euleriano path è una possibile ricostruzione extra dell'intera sequenza.

Considera l'esempio:

enter image description here

Ce n'è solo uno possibile percorso euleriano:

  • $ ABCDBE $

Tuttavia, se includiamo un ciclo automatico a $ B $ , che è stato visitato due volte sopra, questo raddoppia a due possibili percorsi euleriani:

enter image description here

  • $ ABBCDBE $
  • $ ABCDBBE $

A seconda se attraversiamo il self loop durante la prima volta che raggiungiamo $ B $ o il secondo.

https://homolog.us/Tutorials/book4/p2.4.html "Anche i programmi di assemblaggio del genoma evitano anche k, perché con anche k, molti k-meri diventano complementi inversi delle proprie sequenze. ** Ciò causa ambiguità nel specificità del filamento del grafico. ** Pertanto, i valori k dispari sono preferiti. "
Bella risposta @ukemi. Mi ci è voluto un po 'per capire la conclusione del punto 1, quindi ho aggiunto lì una frase che mi avrebbe aiutato. Se non ti piace puoi invertire il cambiamento, ma direi che una piccola precisazione sarebbe utile lì.
@KamilSJaron non preoccuparti, più è chiaro, meglio è - sì, tecnicamente avrei dovuto anche mostrare l'esistenza per l'implicazione che devono essere pari da seguire (al contrario di non dispari), ma mostrare l'esistenza è banale tramite l'esempio (ad esempio AT, ATAT eccetera).


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...