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?
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 het bovenstaande antwoord uit te breiden, voor het geval het niet duidelijk is, laten we zien:
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.
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:
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.
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:
Er is er maar één mogelijk Euleriaans pad:
Als we echter een zelflus opnemen op $ B $ , dat hierboven tweemaal wordt bezocht, verdubbelt dit tot twee mogelijke Euleriaanse paden:
Afhankelijk van of we de self-loop doorlopen tijdens de eerste keer dat we $ B $ bereiken, of de tweede.