Buffl

Sequenzanalyse

JK
by Julia K.

Needleman-Wunsch-Algorithmus

  1. Initialisierung: Eine (M+1) x (N+1) Matrix wird erstellt, wobei M und N die Längen der beiden Sequenzen sind. Die erste Spalte und die erste Zeile der Matrix werden mit 0 initialisiert.

  2. Berechnung der Kosten: Die Kostenmatrix wird erstellt, die die Kosten für die Einfügung, Löschung und Substitution von Basen oder Aminosäuren angibt. Für jede Zelle (i,j) in der Matrix werden die Kosten für das Alignment der ersten i Basen von Sequenz A und der ersten j Basen von Sequenz B berechnet, indem die Kosten für Einfügung, Löschung und Substitution verglichen werden.

  3. Ausfüllen der Matrix: Die Matrix wird von links nach rechts und von oben nach unten durchlaufen und jede Zelle (i,j) wird ausgefüllt, indem die Kosten für die Einfügung, Löschung und Substitution verglichen werden, um den kleinsten Wert auszuwählen. Der Wert in jeder Zelle (i,j) wird als das Minimum der folgenden drei Werte berechnet:

    • Der Wert in der Zelle (i-1, j-1) plus die Kosten für die Substitution der Basen oder Aminosäuren an Position (i,j).

    • Der Wert in der Zelle (i-1, j) plus die Kosten für die Löschung der Base oder des Aminosäure an Position (i,j) in der Sequenz A.

    • Der Wert in der Zelle (i, j-1) plus die Kosten für die Einfügung der Base oder des Aminosäure an Position (i,j) in der Sequenz B.

  1. Rückverfolgung: Nachdem die Matrix ausgefüllt wurde, wird das optimale Alignment durch Rückverfolgung von der unteren rechten Ecke der Matrix bis zur oberen linken Ecke gefunden. Der beste Pfad durch die Matrix wird durch das Verfolgen des niedrigsten Kostenpfades von (M,N) zur (0,0) erreicht. Dabei wird in jeder Zelle des Pfades bestimmt, ob eine Einfügung, Löschung oder Substitution durchgeführt werden muss.

  2. Ausgabe des Alignments: Das optimale Alignment wird durch die Auswahl der Aktionen definiert, die in jeder Zelle durchgeführt wurden, um die minimale Kosten zu erreichen. Das Ergebnis ist ein optimales globales Sequenz-Alignment zwischen den beiden Sequenzen.


Smith Waterman Algorithmus

  1. Initialisierung: Eine (M+1) x (N+1) Matrix wird erstellt, wobei M und N die Längen der beiden Sequenzen sind. Die erste Spalte und die erste Zeile der Matrix werden mit 0 initialisiert.

  2. Berechnung der Kosten: Die Kostenmatrix wird erstellt, die die Kosten für die Einfügung, Löschung und Substitution von Basen oder Aminosäuren angibt. Für jede Zelle (i,j) in der Matrix werden die Kosten für das Alignment der ersten i Basen von Sequenz A und der ersten j Basen von Sequenz B berechnet, indem die Kosten für Einfügung, Löschung und Substitution verglichen werden.

  3. Ausfüllen der Matrix: Die Matrix wird von links nach rechts und von oben nach unten durchlaufen und jede Zelle (i,j) wird ausgefüllt, indem die Kosten für die Einfügung, Löschung und Substitution verglichen werden, um den kleinsten Wert auszuwählen. Der Wert in jeder Zelle (i,j) wird als das Maximum der folgenden Werte berechnet:

    • Der Wert in der Zelle (i-1, j-1) plus die Kosten für die Substitution der Basen oder Aminosäuren an Position (i,j).

    • Der Wert in der Zelle (i-1, j) plus die Kosten für die Löschung der Base oder des Aminosäure an Position (i,j) in der Sequenz A.

    • Der Wert in der Zelle (i, j-1) plus die Kosten für die Einfügung der Base oder des Aminosäure an Position (i,j) in der Sequenz B.

    • 0 (wenn der Wert kleiner als 0 ist, wird 0 verwendet)

  1. Finden des maximalen Wertes: Nachdem die Matrix ausgefüllt wurde, wird der höchste Wert in der Matrix gesucht, der das optimale lokale Alignment zwischen den beiden Sequenzen darstellt. Der höchste Wert kann in einer beliebigen Zelle der Matrix sein.

  2. Rückverfolgung: Nachdem der höchste Wert in der Matrix gefunden wurde, wird das optimale Alignment durch Rückverfolgung von der Zelle mit dem höchsten Wert bis zur ersten Zelle mit dem Wert 0 gefunden. Dabei wird in jeder Zelle des Pfades bestimmt, ob eine Einfügung, Löschung oder Substitution durchgeführt werden muss.

  3. Ausgabe des Alignments: Das optimale Alignment wird durch die Auswahl der Aktionen definiert, die in jeder Zelle durchgeführt wurden, um den höchsten Wert in der Matrix zu erreichen. Das Ergebnis ist ein optimales lokales Sequenz-Alignment zwischen den beiden Sequenzen.

  4. Alle Werte die zum optimalen Alignment gehören, bzw damit zusammen hängen werden gelöscht. Nun wird das zweitbeste Alignment bestimmt (nächst höchste Zahl)


Steps pf BLAST

  • Parameters: w = length of a word

  • T = min. score of a hit (for proteins: w=3, T=13 (BLOSUM62))


  1. Vorbereitung der Datenbank:

    • Datenbank mit Referenzsequenzen (Bsp: GenBank oder SwissProt)

    • Die Datenbank Sequenzen Q werden aufgetrennt in k-mers der Länge w

      • Sequenz: agcgacgt -> k-mers: 1. agc, 2. gcg, 3. cga, …

      • Gibt es zweimal das selbe k-mer werden sie zusammengenommen

  1. Query-Übereinstimmung:

    • Abfrage (Query) Sequenz = neue Sequenz die verglichen werden soll

    • sucht nach lokalen Übereinstimmungen innerhalb der Referenzdatenbank

    • Der Algorithmus beginnt mit einem Seed-Satz von kurzen, zusammenpassenden Subsequenzen zwischen dem Query und jeder Sequenz in der Datenbank.

    • Suche alle k-mere in der Datenbank die high-scoring word pairs mit den k-meren der Query Sequenz bilden

      • For every word x of length k in Q make a list of words that when aligned to x score at least T

      • Example: Let x=AIV then score for AIA is 5+5+0 (dropped) and for AII 5+5+4 (taken)

    • k=3 for proteins, k=11 for nucleotides

  2. Ausweitung der Übereinstimmung:

    • Die Seed-Übereinstimmungen werden dann erweitert, um längere Übereinstimmungen zu finden. Der Algorithmus erweitert die Übereinstimmungen schrittweise, indem er die Sequenzpositionen beider Sequenzen vergleicht und die Anzahl der übereinstimmenden Nukleotide (oder Aminosäuren) berechnet.

    • kann dann zb mit Smith Waterman berechnet werden

    • Extend hits in both directions until the score drops more than X relative to the best score yet obtained

    • High-scoring sequence pair

  3. Bewertung der Übereinstimmung:

    • Nach der Ausweitung der Übereinstimmungen wird jeder Treffer bewertet und mit einem Score versehen. Der Score basiert auf der Anzahl der übereinstimmenden Nukleotide oder Aminosäuren und der Anzahl der nicht übereinstimmenden Nukleotide oder Aminosäuren zwischen den beiden Sequenzen.

  4. Identifikation von signifikanten Übereinstimmungen:

    • Schließlich werden die Ergebnisse nach ihrer Signifikanz sortiert und nur die signifikanten Übereinstimmungen werden zurückgegeben. Die Signifikanz wird durch den Score und andere Faktoren wie die Länge der Übereinstimmungen und die Verteilung von Lücken in der Sequenz bestimmt.

    • Sequence alignment scores between random sequences are distributed following an extreme value distribution (EVD)

    • The EVD shows us the probability with which our biological alignment could be due to randomness


Schritt für Schritt Multiples Sequenzalignment (ClustalW)

  1. Paarweiser Vergleich aller Sequenzen -> Ähnlichkeits- / Distanzscore wird von jedem Paar bestimmt -> Erstellungs Distanzmatrix

  2. Guide Tree wird aus Distanzmatrix konstruiert

    • ist kein phylogenetischer Baum -> phylogenetic trees are constructed based on multiple sequence alignment

    • algorithms to construct the optimal tree have exponential complexity, so need heuristic again

    • Constructed with hierarchical clustering methods

      • UPGMA (unweighted pair group method of arithmetic averages)

      • alternative used in ClustalW: neighbor joining

        • similar, but a bit more complex and more accurate

  3. Der Baum wird von den äußersten Knoten (Sequenzen) ausgehend durchlaufen, und jeweils zwei Knoten werden paarweise ausgerichtet, um ein neues Alignment zu bilden.

  4. Die neuen Alignments werden schrittweise zusammengeführt, wobei diejenigen Alignments mit höherer Verwandtschaft im Baum zuerst zusammengeführt werden.

    • Starte mit den 2 Sequenzen, die im Guide-Tree am engsten benachbart sind

    • paarweises globales Alignment (z.B. Needleman-Wunsch)

    • berechne ein Profil (= "Mischsequenz") für diese Sequenzen und setze dieses Profil an den gemeinsamen Knoten

  5. Die Schritte 3 und 4 werden wiederholt, bis alle Sequenzen in das finale Alignment integriert sind.

    • aligniere die nächsten zwei Sequenzen oder Profile, die jetzt am engsten benachbart sind

    • berechne ihr Profil und setze sie an den gemeinsamen Knoten

    • Ende, wenn alle Sequenzen in einem Profil sind (das ist das fertige MSA)


Author

Julia K.

Information

Last changed