Traceback im Smith-Wateman-Algorithmus mit affiner Gap Penalty

Question

Traceback im Smith-Wateman-Algorithmus mit affiner Gap Penalty

8

Ich versuche, den Smith-Waterman-Algorithmus für die lokale Sequenzausrichtung unter Verwendung der affinen Gap-Penalty-Funktion zu implementieren. Ich denke, ich verstehe, wie man die Matrizen einleitet und berechnet, die für die Berechnung der Ausrichtungswerte benötigt werden, aber ich weiß nicht, wie ich dann zurückverfolgen soll, um die Ausrichtung zu finden. Um die 3 benötigten Matrizen zu erzeugen, habe ich den folgenden Code

%Vor%

Ich bin unsicher, ob ich eine einzelne Matrix für Traceback oder nur 1 brauche? Jede Klärung darüber, wie man von der Höchstpunktzahl in F zurückverfolgt werden kann, wäre sehr zu begrüßen.

python bioinformatics biopython sequence-alignment

jonwells 07.08.2013, 10:32

quelle

1 Antwort

Tags und Links python bioinformatics biopython sequence-alignment

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Python hat Probleme beim Zugriff auf das USB-Mikrofon mit Gstreamer, um die Spracherkennung mit Pocksphinx auf einem Raspberry Pi durchzuführen

score 4 · Accepted Answer

Die wichtige Sache, die Sie sich bei Traceback in Smith-Waterman merken sollten, ist, dass die Matrix, in der sich ein Wert befindet, die Richtung bestimmt, in die Sie sich bewegen. Also, wenn du in F bist, bewegst du dich diagonal, wenn du in Ix bist, bewegst du dich horizontal, und wenn du in Iy bist, bewegst du dich vertikal. Das bedeutet, dass Sie in der Zeigermatrix nur die Matrix speichern müssen, von der Sie ein Quadrat erreicht haben. Die Matrix, aus der du kommst, nicht die, zu der du gehst, bestimmt die Richtung, die du gehen sollst.

Beispiel:

Angenommen, Sie befinden sich bei F[5][5] :

Wenn die Zeigermatrix sagt, dass Sie zu Ix gehen sollen, gehen Sie zu Ix[4][4]
Wenn die Zeigermatrix sagt, dass Sie zu Iy gehen sollen, gehen Sie zu Iy[4][4]
Wenn die Zeigermatrix sagt, dass Sie zu F gehen sollen, gehen Sie zu F[4][4]

Wenn Sie bei Ix[5][5] sind:

Wenn die Zeigermatrix sagt, dass Sie zu Ix gehen sollen, gehen Sie zu Ix[4][5]
Wenn die Zeigermatrix sagt, dass Sie zu F gehen sollen, gehen Sie zu F[4][5]

Oder wenn Sie sich bei Iy[5][5] befinden:

Wenn die Zeigermatrix sagt, dass Sie zu Iy gehen sollen, gehen Sie zu Iy[5][4]
Wenn die Zeigermatrix sagt, dass Sie zu F gehen sollen, gehen Sie zu F[5][4]

Angenommen, der erste Index ist die x-Koordinate und der zweite die y-Koordinate.

Fahren Sie mit der Verfolgung fort, bis Sie eine Zelle mit einem Höchstwert von 0 erreichen.

Erstellen der Zeigermatrix: Sie benötigen jeweils eine Zeigermatrix für F , Ix und Iy . Diese Matrizen müssen nur angeben, aus welcher Matrix ein Wert stammt, denn das sagt Ihnen, in welche Richtung Sie sich bewegten. Wenn Sie also die dynamische Programmierungsphase des Algorithmus durchlaufen, sollten Sie auch die Zeigermatrizen aufbauen. Jedes Mal, wenn Sie einen neuen Maximalwert in einer Zelle in F , Ix oder Iy speichern, sollten Sie die entsprechende Matrix aktualisieren, um anzugeben, woher sie stammt. Wenn zum Beispiel der höchste Wert, den du in F[5][5] haben kannst, durch das Ausrichten der zwei nächsten Basen kommt, wenn du in F[4][4] bist, sollte der Fpointer [5] [5] auf F gesetzt werden, weil du hast dort von der F Matrix.