Needleman-Algorithmus zur optimalen Ausrichtung zweier Aminosäuresequenzen

Ich möchte die optimale Ausrichtung zweier Aminosäuresequenzen gemäß der folgenden Definition aus einem Patent berechnen:

„Der Prozentsatz der Identität zwischen zwei Peptid- oder Nukleotidsequenzen ist eine Funktion der Anzahl von Aminosäuren oder Nukleotidresten, die in den zwei Sequenzen identisch sind, wenn ein Alignment dieser zwei Sequenzen erzeugt wurde. Identische Reste sind als Reste definiert, die die sind in den beiden Sequenzen an einer gegebenen Position des Alignments gleich.Der Prozentsatz der Sequenzidentität, wie hierin verwendet, wird aus dem optimalenAlignment berechnet, indem die Anzahl der Reste, die zwischen zwei Sequenzen identischsind, durch die Gesamtzahl der Reste am kürzesten dividiert wird Sequenz und Multiplizieren mit 100. Das optimale Alignment ist das Alignment, bei dem der Identitätsprozentsatz am höchstmöglichen ist.Lücken können in eine oder beide Sequenzen an einer oder mehreren Positionendes Alignments eingeführt werden, um das optimale Alignment zu erhalten.Diese Lücken werden dann als nicht identische Reste für die Berechnung des Prozentsatzes der Sequenzidentität berücksichtigt.“

Die Needleman- und Wunsch-Implementierung bei NCBI ( https://blast.ncbi.nlm.nih.gov/Blast.cgi ) funktioniert meistens, aber nicht genau. Vielen Dank an @David & @WYSIWIG von einem verwandten SE-Thread, der dies vorgeschlagen hat ( Berechnung der prozentualen Identität zwischen DNA- / Aminosäuresequenz ) .

Ich möchte wissen, ob es eine Möglichkeit gibt, die Diskrepanz zu beheben.

zB Mein Testfall ist:

Seq1: ABDE
Seq2: AAAAAAAAAAABCDE

Die NCBI-Implementierung ergibt das folgende Alignment, das nur 3 identische Reste hat:

Geben Sie hier die Bildbeschreibung ein

Aber sollte nicht eine optimale Ausrichtung mit 4 identischen Resten wie folgt möglich sein:

Seq1: ----------AB-DE
Seq2: AAAAAAAAAAABCDE

Gedanken? Gibt es eine Möglichkeit, die Implementierung zu optimieren, um das gewünschte Ergebnis zu erzielen? Alternativ irgendein anderer Algorithmus, der gezwungen werden kann, diese Ausrichtung zu erhalten? BLAST oder eine Variante?

Antworten (3)

Needleman-Wunsch führt eine End-to-End (globale) Ausrichtung durch (BLAST verwendet Smith-Waterman). Eine Nadel aus dem EMBOSS-Toolkit führt eine Needleman-Wunsch-Ausrichtung durch. Es wird die Ausrichtung mit der höchsten Punktzahl gemeldet. Ich bin mir nicht sicher, welche Ausrichtung es meldet, wenn es zwei von ihnen mit gleicher Punktzahl gibt (ich glaube nicht, dass es zufällig ist).

Ich habe gerade Ihren Fall ausprobiert: Ersetzt Bdurch W, da ersteres keine bestimmte Aminosäure bezeichnet (es ist mehrdeutig). Es gibt:

     1 ----------AW-DE      4
                 || ||
     1 AAAAAAAAAAAWCDE     15

Beachten Sie, dass Sie dieses Verhalten ändern können, indem Sie die Abzüge für das Öffnen und Erweitern von Lücken ändern . Sie können auch die Endlückenstrafen (Lücken am Anfang oder Ende der Ausrichtung; nicht in der Mitte) in Needle ändern .

In diesem Fall Gap-Open = 10, Gap-Extend = 0,5, End Gap Penalty = false und Matrix = BLOSUM62

Zur Durchführung einer lokalen Ausrichtung können Sie Smith-Waterman verwenden. Es richtet nur die Region mit der höchsten Punktzahl aus und führt keine End-to-End-Ausrichtung durch. Sie können Gap-Open- und Gap-Extend- Strafen auch in Smith-Wateman und BLAST ändern , aber diese Algorithmen beginnen oder beenden ein Alignment nicht mit einem Gap.

Dies ist die Ausgabe von Smith-Waterman mit Gap-Open =1 und Gap-Extend =0,5 und BLOSUM62 als Scoring-Matrix.

     1  AW-D  3
        || |
    11  AWCD 14

Weitere Informationen finden Sie unter Was ist der Unterschied zwischen lokalen und globalen Sequenzalignments?

Verdammt. Was für ein Glück, dass ich online unter diesem Link auf die falschen Codes gestoßen bin: fao.org/docrep/004/y2775e/y2775e0e.htm Da steht B für Asparagin oder Asparaginsäure. Es ist sogar der Top-Link bei Google. Und die FAO schien eine maßgebliche Seite zu sein. Mein Fehler!
@curious_cat Oh ja, das war mir nicht klar. Scheint, dass Needle mehrdeutige Codes wie Bund akzeptiert Z, aber viele Algorithmen wahrscheinlich nicht (obwohl ich mir da nicht so sicher bin). Wie auch immer, ist Ihr Zweifel klar?
Vielen Dank. Ja, ich denke es ist jetzt klar. Ich nähere mich den patentierten optimalen Ausrichtungen, indem ich alle Strafen auf Null setze. Vielleicht werde ich jetzt auch eine benutzerdefinierte Matrix bereitstellen, um es zu einer 1-0-Ausrichtung zu machen, anstatt der Scoring-Funktionsmatrix, die wie BLOSUM auf natürlichen Neigungen basiert.

Das ist ein sehr schlechter Testfall.

Das Problem ist, dass die Sequenzen zu kurz sind und eine lange Wiederholung beinhalten. Dies bedeutet, dass die standardmäßigen Lückenstrafen und die Lückenlängenstrafen nicht anwendbar sind. Sie sind so konzipiert, dass sie mit längeren Sequenzen funktionieren, bei denen die Strafe für das Einfügen einer Lücke durch eine Zunahme der Übereinstimmungen ausgeglichen werden kann. In jedem Fall kann es an den Enden von DNA-Sequenzen zu schlechten Ausrichtungen kommen, wenn der DNA-Abschnitt, der durch Einfügen einer Lücke ausgerichtet wird, außerhalb des Bildschirms liegt.

Obwohl der Algorithmus wasserdicht sein kann, macht seine Implementierung in einem Ausrichtungsprogramm bestimmte Annahmen, wo Werte für Punktzahlen und Strafen involviert sind. Sie müssen wissen, welche das sind und wann sie anwendbar sind. Es gibt sogar Situationen, in denen Sie Ihre eigene Matrix produzieren müssen, um eine Ausrichtung zwischen Paaren zu erzwingen, von denen Sie wissen, dass sie aus anderen Informationen ausgerichtet werden müssen (aktive Stellen, regulatorische Motive). Das ist ziemlich berechtigt, weil das Programm nichts über Biologie weiß – Sie schon.

Eine Ergänzung (analog zum Bereitstellen einer eigenen Matrix): PSI-BLAST führt eine Berechnung einer positionsspezifischen Bewertungsmatrix unter Verwendung der homologen Treffer durch. Mit jeder Iteration sollen die Hits besser werden. Dies ist eine Art maschinelles Lernen; nicht wirklich wie das Setzen Ihrer eigenen Matrix, aber es berücksichtigt etwas Biologie.
Wie gesagt, das ist etwas anders. Es ist Standard in MSA (Multiple Sequence Alignment) – oder zumindest Clustal tut dasselbe. Aber der entscheidende Punkt ist, über den Algorithmus und die Annahmen nachzudenken – offensichtlich schwierig für einen Anfänger.

Ihre Vermutung wird gemacht, ohne die Proteinsubstitutionswahrscheinlichkeiten zu kennen.

Die Optimalität der Ausrichtung in BLAST ist eine Metrik der Bewertungsfunktion. Die Bewertungsfunktion hängt von der Wortgröße (Länge des Seeds, der eine Ausrichtung einleitet), Belohnungen und Strafen für Übereinstimmungen und Nichtübereinstimmungen – Lückenkosten und Substitutionsmatrix – ab. Im Allgemeinen verwendet BLAST BLOSUM und PAM – diese Matrizen basieren auf evolutionären Daten. Mehr über Scoring-Parameter können Sie in der BLAST-Hilfe nachlesen .

Sie können diese Parameter unter "Algorithmusparameter" ganz unten auf der Analyseseite feinabstimmen. Wenn Sie die Parameter kennen, über die Sie entscheiden können, ist Ihre wilde Vermutungsausrichtung sinnvoll oder nicht.

Needleman-Algorithmus zur optimalen Ausrichtung zweier Aminosäuresequenzen
AntwortenHierDatenschutz-Bestimmungen1y, 0v