Vraag:
Hoe maak je een onderscheid tussen de "klassieke" de Bruijn-grafiek en die beschreven in NGS-papers?
Leo Martins
2017-05-19 15:32:45 UTC
view on stackexchange narkive permalink

In Computer Science heeft een De Bruijn-grafiek (1) m ^ n hoekpunten die alle mogelijke reeksen van lengte n over vertegenwoordigen m symbolen, en (2) gerichte randen die knooppunten verbinden die verschillen door een verschuiving van n-1 elementen (de opvolger heeft het nieuwe element aan de rechterkant).

Maar in Bio-informatica, terwijl conditie (2) behouden blijft, lijkt wat een De Bruijn-grafiek wordt genoemd niet te voldoen aan voorwaarde (1). In sommige gevallen lijkt de grafiek helemaal niet op een de Bruijn-grafiek (bijv. http://genome.cshlp.org/content/18/5/821.full).

Dus mijn vraag is: als ik expliciet wil maken dat ik de Bioinformatics-interpretatie van een de Bruijn-grafiek gebruik, is er dan een term voor? Iets als "vereenvoudigde de Bruijn-grafiek", "projectie van een de Bruijn-grafiek" of "grafiek van naburige k-mers"? Zijn er kranten die dit onderscheid maken, of heb ik het helemaal verkeerd?

In feite betekent voorwaarde 1 dat zelfs randloze hoekpunten in de grafiek aanwezig moeten zijn, toch?
Ik bedoel, ik vraag me af of een niet-bio-informatica-implementatie van De Bruijn-grafiek ze daadwerkelijk opslaat, aangezien ze geen bruikbare informatie bevatten.
Er is nog een verschil in De Bruijn-grafieken die worden gebruikt voor genoomassemblage - randen worden gewogen.
Hallo @Slim re. Q1, ik geloof dat de grafieken van de Bruijn met elkaar verbonden zijn (één onderdeel). Je kunt ze bouwen door `m` en` n` (http://mathworld.wolfram.com/deBruijnGraph.html) op te geven. Q2: ja, implementaties hebben niet alle knooppunten nodig; de Bruijn-grafiek is een abstracte entiteit, een combinatorische structuur, zoals een "complete grafiek". Maar als mijn zeer belangrijke grafiek enkele randen mist (b / c nutteloos), kan ik het niet "compleet" noemen. Het maakt het trouwens niet minder belangrijk! Q3: dat is waar! Bedankt voor het bewerken van de vraag.
Drie antwoorden:
#1
+7
Leo Martins
2017-05-23 01:33:56 UTC
view on stackexchange narkive permalink

Verschillende kranten hebben dit onderscheid gemaakt, en een paar gebruiken inderdaad verschillende termen om ze van elkaar te onderscheiden. Bijvoorbeeld, Kazaux et al. (2016) erkennen dat:

Deze beperkingen begunstigen het gebruik van een versie van de de Bruijn Graph (dBG) gewijd aan genoomassemblage - een versie die verschilt van de uitgevonden combinatorische structuur door NG de Bruijn.

Kingsford et al. (2010) erkennen ook het onderscheid:

Merk op dat deze definitie van een de Bruijn-grafiek verschilt van de traditionele definitie beschreven in de wiskundige literatuur in de jaren 1940, die vereist dat de grafiek alle strings van lengte-k die uit een alfabet kunnen worden gevormd (in plaats van alleen de strings die in het genoom aanwezig zijn).

De oudste referentie die ik vond voor een specifieke term om te verwijzen naar de assembly-gerelateerde structuur is Skiena en Sundaram (1995), waar ze het een subgraaf van de de Bruijn digraph . Later, in 2002, zullen Błażewicz et al. ernaar verwijzen als een de Bruijn geïnduceerde subgraaf . De term de Bruijn-subgraaf wordt ook formeel gedefinieerd in Quitzau's proefschrift (2009). Daar, en ook in het artikel ( Quitzau en Stoye, 2008), beschrijven de auteurs de sequentiegrafiek als een wijziging van de spaarzame de Bruijn-subgraaf (vaak gebruikt bij montageproblemen) , waar niet-vertakkende paden worden vervangen door een enkel hoekpunt. De term sparse de Bruijn graph wordt ook gebruikt door Chauve et al. (2013).

Een andere term die ik vond was woordgrafiek , beschreven door Malde et al. (2005) en door Heath en Pati (2007) als een subgraaf of als een generalisatie van een de Bruijn-grafiek. Rødland (2013) vat enkele van de termen samen die voor deze gegevensstructuur worden gebruikt:

De datastructuur wordt het best begrepen in termen van de de Bruijn-subgraafweergave van S [k]. (...) Sommige auteurs noemen dit een woordgrafiek, of zelfs gewoon een de Bruijn-grafiek.

Hoewel we kunnen erkennen dat het onderscheid niet erg relevant is, is de vraag specifiek vragen naar de situatie waarin men een dergelijk onderscheid wil maken.

Zoals veel kranten en ikzelf al zeiden, is assembly de Bruijn-grafiek slechts een subgraaf van de volledige de Bruijn-grafiek. Iemand die iets anders zegt, erkent deze eenvoudige relatie niet. "Sequentiegrafiek" is te algemeen en wordt in een andere context gebruikt (bijv. Sequentiegrafiek). "Sparse de Bruijn graph" is geschikter voor een graaf die is geconstrueerd door enkele k-mers over te slaan in reads (bijv. In sparse assembler). Gerichte acyclische woordgrafiek (DAWG) is een reeds bestaand concept, althans daterend uit de jaren 80, waardoor "woordgrafiek" ook dubbelzinnig is. Mensen moeten stoppen met het verzinnen van nieuwe namen voor een subgraaf.
Pevzner heeft baanbrekend werk verricht door de Bruijn-grafieken te gebruiken bij montage (http://www.pnas.org/content/98/17/9748.full) en alternatieve splitsing (https://www.ncbi.nlm.nih.gov/ gepubliceerd / 12169546)
#2
+4
holmrenser
2017-05-19 16:07:00 UTC
view on stackexchange narkive permalink

Naast de reguliere De Bruijn-grafiek zoals afgebeeld op de wikipedia, bevatten sommige implementaties in bio-informatica aanvullende verwerking. Ik denk dat de belangrijkste reden waarom figuur 1 in het artikel dat je hebt gelinkt (betreffende de Velvet genome assembler) enigszins verschilt, is dat een knooppunt een reeks overlappende k-mers vertegenwoordigt. Om dit te visualiseren als een meer klassieke De Bruin-grafiek, zou je de k-mers moeten verbinden die boven de knooppunten zijn afgebeeld. Het bijschrift naast figuur één beschrijft de verwerking heel duidelijk.

Zoals je laatste vraag betreft: ik denk niet dat er een 'Bioinformatische interpretatie van een De Bruijn-grafiek' is. Er zijn verschillende implementaties, die allemaal hun specifieke kenmerken hebben. Het is dus het beste om te verwijzen naar de daadwerkelijke implementatie.

Als voorbeeld: dit is een mooi artikel over hoe je een pan-genoom De Bruijn-grafiek van meerdere genomen tegelijkertijd kunt construeren. .

Maar een "implementatie" van een de Bruijn-grafiek die niet alle k-mers omvat, is niet meer een de Bruijn-grafiek (in de oorspronkelijke zin), toch? Als de implementatie niet voldoet aan voorwaarde (1) hierboven, vraag ik me af of er een andere naam (of een kwalificatie) wordt gebruikt.
Ik ben er vrij zeker van dat alle originele k-mers in een of andere vorm aanwezig zijn.
#3
+3
user172818
2017-05-19 19:14:34 UTC
view on stackexchange narkive permalink

Laten we eerst aannemen dat DNA maar één streng heeft. Een assembly de Bruijn-grafiek is een subgraaf van een complete de Bruijn-grafiek. Het bevat een hoekpunt u als u een k-mer is bij het lezen; het bevat een rand u-> v, als u en v aangrenzende k-mers zijn bij het lezen. Als alternatief merken we op dat een rand u-> v wordt weergegeven door een (k + 1) -mer. Een assembly de Bruijn-grafiek kan worden beschouwd als een subgraafrand die wordt geïnduceerd door alle (k + 1) -mers in reads - in feite nemen sommige assembleurs de lijst van (k + 1) -mer als een beknopte weergave van de Bruijn-grafieken. / p>

DNA heeft twee strengen. We hoeven alleen maar een assembly de Bruijn-grafiek te maken van alle (k + 1) -mers en hun omgekeerde complement. Het is nog steeds een subgraaf van een complete de Bruijn-grafiek.

Omdat een assembly de Bruijn-grafiek slechts een subgraaf is. Het is niet nodig om het een nieuwe naam te geven.

PS: ik heb mijn oude antwoord verwijderd, want dat was niet waar je om vroeg op basis van je opmerkingen. Ik was in de war door uw vermelding van fluweel. Velvet gebruikt een gelijkwaardige maar ongebruikelijke weergave van de Bruijn-grafieken, wat uw vraag ingewikkelder maakt.



Deze Q&A is automatisch vertaald vanuit de Engelse taal.De originele inhoud is beschikbaar op stackexchange, waarvoor we bedanken voor de cc by-sa 3.0-licentie waaronder het wordt gedistribueerd.
Loading...