Pitanje:
Kako razlikovati "klasični" de Bruijn-ov graf i onaj opisan u NGS-ovim radovima?
Leo Martins
2017-05-19 15:32:45 UTC
view on stackexchange narkive permalink

U Computer Science-u De Bruijn-ov graf ima (1) m ^ n vrhove koji predstavljaju sve moguće nizove duljine n preko m simbola i (2) usmjerenih rubova koji povezuju čvorove koji se razlikuju pomakom n-1 elemenata (nasljednik s novim elementom zdesna).

Međutim, u bioinformatici dok je uvjet (2) sačuvan, čini se da ono što se naziva De Bruijn grafom ne poštuje uvjet (1). U nekim slučajevima graf uopće ne izgleda poput de Bruijn grafa (npr. http://genome.cshlp.org/content/18/5/821.full).

Dakle, moje pitanje glasi: ako želim izričito objasniti da koristim interpretaciju bioinformatike de Bruijn grafa, postoji li pojam za to? Nešto poput "pojednostavljenog de Bruijn grafa", "projekcije de Bruijn grafa" ili "grafa susjednih k-mersa"? Postoje li neki papiri koji to razlikuju ili sam sve pogrešno shvatio?

U osnovi uvjet 1 znači da bi na grafu trebali biti prisutni i vrhovi bez rubova, zar ne?
Mislim, pitam se da li ih ne-bioinformatička implementacija De Bruijn grafa zapravo pohranjuje, jer ne sadrže nikakve korisne informacije.
Postoji još jedna razlika u De Bruijn grafovima koji se koriste za sastavljanje genoma - rubovi su ponderirani.
Pozdrav @Slim re. Q1, vjerujem da su grafovi de Bruijn povezani (jedna komponenta). Možete ih izgraditi samo davanjem m i n (http://mathworld.wolfram.com/deBruijnGraph.html). P2: da, implementacije ne trebaju sve čvorove; de Bruijnov graf je apstraktna cjelina, kombinacijska struktura, poput "cjelovitog grafa". Ali ako moj vrlo važan graf propusti neke rubove (b / c beskoristan), ne mogu ga nazvati "dovršenim". Ne čini ga manje važnim BTW! P3: to je istina! Hvala što ste uredili pitanje.
Tri odgovori:
#1
+7
Leo Martins
2017-05-23 01:33:56 UTC
view on stackexchange narkive permalink

Nekoliko je radova to razlikovalo, a nekoliko ih uistinu koristi različite izraze da bi ih razlikovalo. Na primjer, Kazaux i sur. (2016) potvrđuju da:

Ova ograničenja favoriziraju upotrebu verzije grafika de Bruijn (dBG) posvećene sastavljanju genoma - verzije koja se razlikuje od kombinirane strukture izumljene NG de Bruijn.

Kingsford i sur. (2010) također prepoznaju razliku:

Imajte na umu da se ova definicija de Bruijn grafa razlikuje od tradicionalne definicije opisane u matematičkoj literaturi 1940-ih koja zahtijeva da graf sadrži sve nizove dužine k koji se mogu oblikovati iz abecede (a ne samo one žice prisutne u genomu).

Najstarija referenca koju sam pronašao za određeni pojam koji se odnosi na strukturu povezanu sa sklopom je Skiena i Sundaram (1995), gdje je nazivaju podgraf de Bruijn digrafa . Kasnije, 2002. godine, Błażewicz i sur. to će nazivati ​​ de Bruijn induciranim podgrafom . Pojam de Bruijn podgraf formalno je definiran i u Quitzau's thesis (2009). Tamo, a također u članku ( Quitzau i Stoye, 2008.) autori opisuju grafikon sekvenci kao modifikaciju oskudnog de Bruijn podgrafa (obično korištenog u problemima montaže) , gdje su nerazgranate staze zamijenjene jednim vrhom. Pojam rijetki de Bruijn-ov graf koriste i Chauve i sur. (2013).

Još jedan pojam koji sam pronašao bio je graf riječi , koji su opisali Malde i sur. (2005.) i Heath i Pati (2007.) kao podgraf ili kao generalizacija de Bruijn grafa. Rødland (2013) sažima neke pojmove koji se koriste za ovu strukturu podataka:

Struktura podataka najbolje se razumije u smislu predstavljanja de Bruijna podgrafa S [k]. (...) Neki autori ovo mogu nazvati grafom riječi ili čak samo de Bruijn grafom.

Iako možemo prepoznati da razlika nije vrlo relevantna, pitanje je tražeći posebno situaciju u kojoj se želi napraviti takva razlika.

Kao što su rekli mnogi drugi radovi, i sam osobni graf de Bruijn samo je podgraf cijelog grafa de Bruijn. Svatko tko kaže drugačije ne uspijeva priznati ovu jednostavnu vezu. "Grafikon niza" previše je općenit i koristi se u drugom kontekstu (npr. Graf sklopa niza). "Sparse de Bruijn graf" prikladniji je za graf konstruiran preskakanjem nekih k-mersa u čitanjima (npr. U rijetkom asembleru). Usmjereni aciklički grafikon riječi (DAWG) je već postojeći koncept, barem još iz 80-ih, što i "grafikon riječi" čini dvosmislenim. Ljudi bi trebali prestati izmišljati nova imena za podgraf.
Pevzner je obavio osnovni posao koristeći de Bruijn grafove u montaži (http://www.pnas.org/content/98/17/9748.full) i alternativno spajanje (https://www.ncbi.nlm.nih.gov/ objavljeno / 12169546)
#2
+4
holmrenser
2017-05-19 16:07:00 UTC
view on stackexchange narkive permalink

Uz redovni De Bruijnov graf kako je prikazan na wikipediji, neke implementacije u bioinformatiku sadrže i dodatnu obradu. Pretpostavljam da je glavni razlog što je slika 1 u radu koji ste povezali (koji se odnosi na aparat za genom Velvet) nešto drugačiji taj što čvor predstavlja niz preklapajućih k-mer . Da biste ovo vizualizirali kao klasičniji De Bruinov graf, morali biste povezati k-merove prikazane iznad čvorova. Natpis uz prvu sliku opisuje obradu sasvim jasno.

Kao i na vaše posljednje pitanje: Mislim da ne postoji "bioinformatička interpretacija De Bruijn grafa". Postoje različite implementacije, koje sve tamo imaju specifičnosti. Stoga bi bilo najbolje pozvati se na stvarnu provedbu.

Kao primjer: ovo je lijep rad o tome kako istodobno konstruirati pan-genomov De Bruijn-ov graf višestrukih genoma .

Ali "implementacija" de Bruijn grafa koji ne uključuje sve k-mers više nije de Bruijn graf (u izvornom smislu), zar ne? Ako implementacija ne zadovoljava gornji uvjet (1), pitam se koristi li se drugo ime (ili kvalifikator).
Sasvim sam siguran da su svi izvorni k-meri prisutni u nekom obliku.
#3
+3
user172818
2017-05-19 19:14:34 UTC
view on stackexchange narkive permalink

Pretpostavimo prvo da DNA ima samo jedan lanac. Skupni de Bruijn-ov graf podgraf je cjelovitog de Bruijn-ovog grafa. Sadrži vrh u ako je u k-mer u čitanjima; sadrži rub u-> v, ako su u i v susjedne k-mjere na čitanju. Alternativno, napominjemo da je rub u-> v predstavljen (k + 1) -merom. Grafikon de Bruijn-a može se smatrati rubom podgrafa induciranim od svih (k + 1) -mjerača u očitanjima - zapravo neki asembleri uzimaju popis (k + 1) -mera kao sažeti prikaz de Bruijn grafova.

DNA ima dva lanca. Samo trebamo inducirati skup de Bruijn grafa od svih (k + 1) -mera i njihovog obrnutog komplementa. To je još uvijek podgraf cjelovitog de Bruijn grafa.

Budući da je skup de Bruijn grafa samo podgraf. Nije potrebno davati mu novo ime.

PS: Izbrisao sam stari odgovor jer to nije ono što tražite na temelju vaših komentara. Zbunilo me vaše spominjanje baršuna. Velvet koristi ekvivalentan, ali neobičan prikaz de Bruijn grafova, što komplicira vaše pitanje.



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