Frage:
Warum benötigen einige Assembler für die Erstellung von de Bruijn-Graphen einen ungeraden Kmer?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

Warum benötigen einige Assembler wie SOAPdenovo2 oder Velvet eine ungerade k -mer-Größe für die Erstellung des de Bruijn-Diagramms? Einige andere Assembler wie ABySS eignen sich gut für k -Mere mit gerader Länge?

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

Aus dem Handbuch von Velvet:

muss eine ungerade Zahl sein, um Palindrome zu vermeiden. Wenn Sie eine gerade Zahl eingeben, dekrementiert Velvet diese einfach und fährt fort.

Die Palindrome in der Biologie werden als umgekehrte komplementäre Sequenzen definiert. Das Problem der Palindrome wird in dieser Übersicht erläutert:

Palindrome induzieren Pfade, die sich auf sich selbst zurückfalten. Mindestens ein Assembler vermeidet diese elegant; Samt erfordert, dass K, die Länge eines K-Mer, ungerade ist. Ein K-mer ungerader Größe kann nicht mit seinem umgekehrten Komplement übereinstimmen.

Es ist möglich, einen Graphen mit Palindromen zu erstellen, aber dann ist die Interpretation schwieriger. Das Zulassen nur von Graphen mit ungeraden k -Meren ist nur eine elegante Methode, um das Schreiben eines Codes zur Interpretation eines komplizierteren Graphen zu vermeiden.

Damit dies in Zukunft nicht falsch interpretiert wird, sollte beachtet werden, dass [palindrome] (https://en.wikipedia.org/wiki/Palindromic_sequence) in diesem Zusammenhang eine etwas spezifischere Bedeutung hat als es [normalerweise auf Englisch] (https) : //en.wiktionary.org/wiki/palindrome).
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

Um die obige Antwort zu erweitern, falls es nicht klar ist, zeigen wir:

  1. Warum palindromische Sequenzen gerade sein müssen
  2. Warum palindromische Sequenzen induzieren Selbstschleifen in einem De-Bruijn-Diagramm
  3. Warum Selbstschleifen in einem De-Bruijn-Diagramm problematisch sind
  4. ol>

    1. Palindromische Sequenz ⇒ Sequenz hat eine gerade Länge

    Idee: In einem ungeraden k-mer ist sein mittleres Nukleotid in seinem umgekehrten Komplement "gespiegelt", so dass die zwei können niemals gleich sein.

    Angenommen, Sie haben eine palindromische Sequenz $ X $ span>. Dann ist $ X $ span> identisch mit seinem umgekehrten Komplement, das wir als $ \ bar {X} $ span> bezeichnen

    Angenommen, $ X $ span> hat eine ungerade Länge. Dann hat es die Form $ AbC $ span>, wobei $ len (A) = len (C) = \ frac {len (X) -1} {2} $ span> und $ len (b) = 1 $ span>.

    Dann

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

    Und daher:

    $ b = \ bar {b} $ span>

    ( da $ len (A) = len (C) = len (\ bar {C})) $ span>. Dies ist jedoch ein Widerspruch, da $ b $ span> ein einzelnes Nukleotid ist und nicht gleich seinem Komplement sein kann. Daher können k-mere mit ungerader Länge keine Palindrome bilden.

    Daher muss die Länge eines k-mers, das ein Palindrom bildet, gerade sein.


    2. Warum palindromische k-Mere Selbstschleifen induzieren

    Jeder Knoten in einem traditionellen De-Bruijn-Diagramm ist eine eindeutige Zeichenfolge, aber in den meisten bioinformatischen Implementierungen wird jedes Paar umgekehrt komplementärer k-1-Mere als a identifiziert einzelner Knoten, z. B. für $ k = 6 $ span>:

    A. palindromisches k-mer (von $ k \ geq 2 $ span>) hat die Form:

    $ xAy $ span>

    wobei $ len (A) = k-2 $ span>, $ x = \ bar {y} $ span> und $ A = \ bar {A} $ span> (möglicherweise die leere Zeichenfolge).

    Daher werden zwei Knoten in das De-Bruijn-Diagramm eingefügt:

    1. sein linkes k-1-mer $ xA $ span>
    2. sein rechtes k-1-mer $ Ay $ span>
    3. ol>

      Und eine Kante von 1 bis 2.

      Da dieses k-mer jedoch palindromisch ist, $ xA = \ overline {Ay} $ span> und daher sind diese beiden Knoten umgekehrt komplementär und somit der "gleiche" Knoten, und daher ist diese Kante eine Selbstschleife an diesem Knoten.


      3. Warum sind Selbstschleifen problematisch?

      Selbstschleifen (wenn sie in einem Knoten mit $ in \ _degree \ geq 2 $ span> und $ out \ _degree \ geq 1 $ span>) erhöht die Anzahl möglicher Euler-Pfade in einem de Bruijn-Diagramm (oder genauer gesagt in der verbundenen Komponente, die diesen Knoten enthält, der ein contig (von denen es mehrere geben kann), da Sie für jedes Mal, wenn Sie diesen Knoten durchqueren, einen zusätzlichen möglichen Euler-Pfad haben.

      Dies erhöht die Mehrdeutigkeit beim Lesen des Diagramms wie jeder mögliche Euler-Pfad Pfad ist eine zusätzliche mögliche Rekonstruktion der vollständigen Sequenz.

      Betrachten Sie das Beispiel:

      enter image description here

      Es gibt nur eine Möglicher Eulerscher Pfad:

  • $ ABCDBE $ span>

Wenn wir jedoch eine Selbstschleife einschließen Bei $ B $ span>, das oben zweimal besucht wird, verdoppelt sich dies auf zwei mögliche Eulersche Pfade:

enter image description here

  • $ ABBCDBE $ span>
  • $ ABCDBBE $ span>

Abhängig von ob wir die Selbstschleife beim ersten Mal durchlaufen, wenn wir $ B $ span> oder die zweite erreichen.

https://homolog.us/Tutorials/book4/p2.4.html "Genomassemblierungsprogramme vermeiden auch gerade k, da mit gerade k viele k-mere zu umgekehrten Komplementen ihrer eigenen Sequenzen werden. ** Dies führt zu Mehrdeutigkeiten in der Strangspezifität des Graphen. ** Daher werden ungerade k-Werte bevorzugt. "
Schöne Antwort @ukemi. Ich habe eine Weile gebraucht, um die Schlussfolgerung von Punkt 1 zu verstehen, deshalb habe ich dort einen Satz hinzugefügt, der mir geholfen hätte. Wenn es dir nicht gefällt, kannst du die Änderung rückgängig machen, aber ich würde sagen, dass eine kleine Klarstellung dort gut wäre.
@KamilSJaron keine Sorge, je klarer desto besser - ja, technisch hätte ich auch Existenz zeigen sollen, um zu implizieren, dass sie gerade sein müssen (im Gegensatz zu nicht ungerade), aber Existenz zu zeigen ist trivial anhand eines Beispiels (z. B. AT, ATAT) etc).


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...