Pitanje:
Zašto neki sastavljači zahtijevaju kmer neparne duljine za konstrukciju de Bruijn grafova?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

Zašto neki sastavljači poput SOAPdenovo2 ili Velvet zahtijevaju k -mernu veličinu neparne duljine za izradu de Bruijn grafa, dok neki drugi sastavljači poput ABySS su u redu s k -merima duljine?

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

Iz priručnika za Velvet:

to mora biti neparan broj, kako bi se izbjegli palindromi. Ako unesete paran broj, Velvet će ga samo smanjiti i nastaviti.

palindromi u biologiji definirani su kao obrnuti komplementarni nizovi. Problem palindroma objašnjen je u ovom pregledu:

Palindromi induciraju putove koji se savijaju na sebi. Barem jedan montažer to izbjegava elegantno; Velvet zahtijeva da K, duljina K-mer, bude neparan. K-mer neparne veličine ne može se podudarati sa svojim obrnutim komplementom.

Graf je moguće konstruirati palindromima, ali tada će interpretacija biti teža. Dopuštanje samo grafova neparnih k -mera samo je elegantan način da se izbjegne pisanje koda za interpretaciju složenijeg grafa.

Da to netko u budućnosti ne bi pogrešno protumačio, treba imati na umu da [palindrom] (https://en.wikipedia.org/wiki/Palindromic_sequence) u ovom kontekstu ima malo specifičnije značenje od onog [normalno na engleskom] (https : //en.wiktionary.org/wiki/palindrome).
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

Da proširimo gornji odgovor, u slučaju da nije jasan, prikazujemo:

  1. Zašto palindromski nizovi moraju biti jednake dužine
  2. Zašto palindromski nizovi induciraju samo petlje u de Bruijn grafu
  3. Zašto su samo petlje u de Bruijn grafu problematične

1. Palindromski slijed ⇒ slijed je parne duljine

Ideja: u k-meru neparne duljine njegov je srednji nukleotid 'preokrenut' u svom obrnutom komplementu, pa je dva nikad ne mogu biti jednaka.

Pretpostavimo da imate palindromsku sekvencu $ X $ . Tada je $ X $ identičan njegovom obrnutom komplementu, koji ćemo označiti $ \ bar {X} $ .

Pretpostavimo da je $ X $ neparne duljine. Tada je oblika $ AbC $ , gdje $ len (A) = len (C) = \ frac {len (X) -1} {2} $ i $ len (b) = 1 $ .

Zatim

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

I stoga:

$ b = \ bar {b} $

( budući da $ len (A) = len (C) = len (\ bar {C})) $ . Ali to je kontradikcija, jer je $ b $ jedan nukleotid i ne može biti jednak njegovom komplementu. Stoga k-mjeri neparne duljine ne mogu tvoriti palindrome.

Stoga duljina k-mera koji tvori palindrom mora biti parna.


2. Zašto palindromični k-merovi induciraju samo petlje

Svaki čvor u tradicionalnom de Bruijn-ovom grafu jedinstveni je niz, ali u većini implementacija bio-informatike svaki par reverzno komplementarnih k-1-mjera identificiran je kao pojedinačni čvor, npr. za $ k = 6 $ :

A palindromski k-mer (od $ k \ geq 2 $ ) je oblika:

$ xAy $

gdje je $ len (A) = k-2 $ span>, $ x = \ bar {y} $ i $ A = \ bar {A} $ (moguće prazan niz).

Stoga će pridonijeti dva čvora u de Bruijn grafu:

  1. njegov lijevi k-1-mer $ xA $
  2. njegov desni k-1-mer $ Ay $

I rub koji ide od 1 do 2.

Ali budući da je ovaj k-mer palindromičan, $ xA = \ overline {Ay} $ i stoga su ova dva čvora obrnuto komplementarna, a time i 'isti' čvor, pa je ovaj rub samopetlja na ovom čvoru.


3. Zašto su samo petlje problematične?

Samopetlje (ako se javljaju u čvoru s $ u \ _degree \ geq 2 $ i $ out \ _degree \ geq 1 $ ) povećati broj mogućih Eulerovih putova u de Bruijn grafu (ili preciznije, u povezanoj komponenti koja sadrži ovaj čvor, koji predstavlja contig , od kojih mogu biti višestruke), jer imate dodatni mogući Eulerov put za svaki put kad pređete ovaj čvor.

To povećava dvosmislenost u čitanju grafa, jer svaki mogući Eulerov put je dodatna moguća rekonstrukcija cijelog niza.

Razmotrite primjer:

enter image description here

Postoji samo jedan mogući Eulerov put:

  • $ ABCDBE $

Međutim, ako uključimo samopetlju na $ B $ , koji je posjećen dva puta gore, ovo se udvostručuje na dvije moguće Eulerove staze:

enter image description here

  • $ ABBCDBE $
  • $ ABCDBBE $

Ovisno o bez obzira prelazimo li auto petlju tijekom prvog puta kad dođemo do $ B $ , ili drugog.

https://homolog.us/Tutorials/book4/p2.4.html "Programi za sastavljanje genoma također izbjegavaju čak i k, jer s čak k mnogi k-merovi postaju obrnuti komplementi vlastitih sekvenci. ** To uzrokuje nejasnoće u specifičnost grafa na nitima. ** Stoga su poželjne neparne k-vrijednosti. "
Lijep odgovor @ukemi. Trebalo mi je vremena da shvatim zaključak točke 1., pa sam tamo dodao rečenicu koja bi mi pomogla. Ako vam se ne sviđa, možete promijeniti promjenu, ali rekao bih da bi tamo bilo malo pojašnjenja.
@KamilSJaron ne brinite, što je jasnije to bolje - da, tehnički bih također trebao pokazati postojanje pod implikacijom da ih moramo ravnomjerno slijediti (za razliku od onih koji nisu neobični), ali pokazivanje postojanja je trivijalno putem primjera (npr. AT, ATAT itd.).


Ova pitanja su automatski prevedena s engleskog jezika.Izvorni sadržaj dostupan je na stackexchange-u, što zahvaljujemo na cc by-sa 3.0 licenci pod kojom se distribuira.
Loading...