Vraag:
Waarom hebben sommige monteurs een kmer met oneven lengte nodig voor de constructie van de Bruijn-grafieken?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

Waarom hebben sommige assembleurs zoals SOAPdenovo2 of Velvet een k -mer-maat met oneven lengte nodig voor de constructie van de Bruijn-grafiek, terwijl zijn sommige andere assemblers zoals ABySS prima met k -mers van even lengte?

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

Uit de handleiding van Velvet:

het moet een oneven getal zijn om palindromen te vermijden. Als je een even getal invoert, verlaagt Velvet het en gaat verder.

de palindromen in de biologie worden gedefinieerd als omgekeerde complementaire sequenties. Het probleem van palindromen wordt uitgelegd in deze recensie:

Palindromen induceren paden die zichzelf terugvouwen. Minstens één assembler vermijdt deze op elegante wijze; Velvet vereist dat K, de lengte van een K-mer, vreemd is. Een K-mer met een oneven grootte kan zijn omgekeerde complement niet evenaren.

Het is mogelijk om een ​​grafiek te construeren met palindromen, maar dan zal de interpretatie moeilijker zijn. Alleen grafieken van oneven k -mers toestaan, is een elegante manier om te vermijden dat u een code schrijft voor interpretatie van een meer gecompliceerde grafiek.

Om te voorkomen dat iemand dit in de toekomst verkeerd interpreteert, moet worden opgemerkt dat [palindroom] (https://en.wikipedia.org/wiki/Palindromic_sequence) in deze context een iets specifiekere betekenis heeft dan [normaal gesproken in het Engels] (https : //en.wiktionary.org/wiki/palindrome).
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

Om het bovenstaande antwoord uit te breiden, voor het geval het niet duidelijk is, laten we zien:

  1. Waarom palindrome sequenties even lang moeten zijn
  2. Waarom palindrome sequenties induceren self-loops in een de Bruijn-graaf
  3. Waarom self-loops in een de Bruijn-graaf problematisch zijn

1. Palindrome sequentie ⇒ sequentie is van even lengte

Idee: in een k-mer met oneven lengte wordt de middelste nucleotide 'omgedraaid' in zijn omgekeerde complement, dus de twee kunnen nooit gelijk zijn.

Stel dat je een palindrome reeks $ X $ hebt. Dan is $ X $ identiek aan het omgekeerde complement, dat we $ \ bar {X} $ zullen noemen .

Stel dat $ X $ een oneven lengte heeft. Dan heeft het de vorm $ AbC $ , waarbij $ len (A) = len (C) = \ frac {len (X) -1} {2} $ , en $ len (b) = 1 $ .

Vervolgens

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

En dus:

$ b = \ bar {b} $

( sinds $ len (A) = len (C) = len (\ bar {C})) $ . Maar dit is in tegenspraak, aangezien $ b $ een enkele nucleotide is en niet gelijk kan zijn aan zijn complement. Daarom kunnen k-mers van oneven lengte geen palindroom vormen.

Daarom moet de lengte van een k-mer die een palindroom vormt even zijn.


2. Waarom palindrome k-mers zelflussen induceren

Elk knooppunt in een traditionele de Bruijn-grafiek is een unieke string, maar in de meeste bio-informatica-implementaties wordt elk paar omgekeerde complementaire k-1-mers geïdentificeerd als een enkel knooppunt, bijv. voor $ k = 6 $ :

A palindromic k-mer (van $ k \ geq 2 $ ) heeft de volgende vorm:

$ xAy $

waarbij $ len (A) = k-2 $ span>, $ x = \ bar {y} $ en $ A = \ bar {A} $ (mogelijk de lege string).

Daarom draagt ​​het twee knooppunten bij in de de Bruijn-grafiek:

  1. zijn linker k-1-mer $ xA $
  2. het is rechts k-1-mer $ Ay $

En een voorsprong van 1 naar 2.

Maar aangezien deze k-mer palindroom is, $ xA = \ overline {Ay} $ en daarom zijn deze twee knooppunten omgekeerd complementair, en dus hetzelfde knooppunt, en dus is deze rand een zelflus op dit knooppunt.


3. Waarom zijn self-loops problematisch?

Self-loops (als ze voorkomen in een node met $ in \ _degree \ geq 2 $ en $ out \ _degree \ geq 1 $ ) vergroot het aantal mogelijke Euleriaanse paden in een de Bruijn-grafiek (of meer specifiek, in de verbonden component die dit knooppunt bevat, dat een contig , waarvan er meerdere kunnen zijn), aangezien je een extra mogelijk Euleriaans pad hebt voor elke keer dat je dit knooppunt doorkruist.

Dit vergroot de ambiguïteit bij het lezen van de grafiek, aangezien elke mogelijke Euleriaans pad is een extra mogelijke reconstructie van de volledige reeks.

Beschouw het voorbeeld:

enter image description here

Er is er maar één mogelijk Euleriaans pad:

  • $ ABCDBE $

Als we echter een zelflus opnemen op $ B $ , dat hierboven tweemaal wordt bezocht, verdubbelt dit tot twee mogelijke Euleriaanse paden:

enter image description here

  • $ ABBCDBE $
  • $ ABCDBBE $

Afhankelijk van of we de self-loop doorlopen tijdens de eerste keer dat we $ B $ bereiken, of de tweede.

https://homolog.us/Tutorials/book4/p2.4.html "Genoomassemblageprogramma's vermijden ook zelfs k, want met even k worden veel k-mers omgekeerde complementen van hun eigen sequenties. ** Dat veroorzaakt onduidelijkheden in de strengspecificiteit van de grafiek. ** Daarom hebben oneven k-waarden de voorkeur. "
Leuk antwoord @ukemi. Het kostte me een tijdje om de conclusie van punt 1 te begrijpen, dus ik heb daar een zin toegevoegd die me zou hebben geholpen. Als het je niet bevalt, kun je de verandering ongedaan maken, maar ik zou zeggen dat een kleine verduidelijking daar goed zou zijn.
@KamilSJaron geen zorgen, hoe duidelijker hoe beter - ja, technisch gezien had ik ook het bestaan ​​moeten aantonen met de implicatie dat ze gelijk moeten zijn om te volgen (in tegenstelling tot gewoon niet-vreemd), maar het laten zien van het bestaan ​​is triviaal via voorbeeld (bijv. AT, ATAT enzovoort).


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