Traceback im Smith-Wateman-Algorithmus mit affiner Gap-Strafe

Question

Ich versuche, den Smith-Waterman-Algorithmus für die lokale Sequenzausrichtung mit 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. Zur Erzeugung der drei Matrizen erforderlich Ich habe den folgenden Code

for j in range(1, len2): 
    for i in range(1, len1): 
     fxOpen = F[i][j-1] + gap 
     xExtend = Ix[i][j-1] + extend 
     Ix[i][j] = max(fxOpen, xExtend) 

     fyOpen = F[i-1][j] + gap 
     yExtend = Iy[i-1][j] + extend 
     Iy[i][j] = max(fyOpen, yExtend) 

     matchScore = (F[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]]) 
     xScore = Ix[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]] 
     yScore = Iy[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]] 
     F[i][j] = max(0, matchScore, xScore, yScore) 

Ich bin nicht sicher, ob ich eine einzelne Matrix für Zurückverfolgungs benötigen oder nur 1? Jede Klärung darüber, wie man von der Höchstpunktzahl in F zurückgeht, würde sehr geschätzt werden.

Answer 1

Die wichtige Sache, die man sich bei Traceback in Smith-Waterman merken sollte, ist, dass die Matrix, in der sich ein Wert befindet, die Richtung bestimmt, in die man sich bewegt. Also, wenn Sie in F sind Sie diagonal bewegen, wenn Sie in Ix sind, bewegen Sie sich horizontal, und wenn Sie in Iy sind, bewegen Sie sich 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.

Zum Beispiel:

Sagen Sie sind bei F[5][5]:

• Wenn Zeiger Matrix Ix zu gehen, sagt, gehen Sie zu Ix[4][4]
• Wenn Zeiger Matrix Iy zu gehen, sagt, gehen zu Iy[4][4]
• Wenn Zeiger Matrix sagt zu F gehen, gehen Sie zu F[4][4]

Während, wenn Sie bei Ix[5][5] sind:

• Wenn Zeiger Matrix sagt Ix zu gehen, gehen Sie zu Ix[4][5]
• Wenn Zeiger Matrix F zu gehen, sagt, gehen Sie zu F[4][5]

Oder wenn Sie unter Iy[5][5] sind:

• Wenn pointer Matrix Iy gehen sagt, gehen Iy[5][4]
• Wenn Zeiger Matrix sagt F zu gehen, gehen zu F[5][4]

Unter der Annahme, dass der erste Index ist die x-Koordinate und die zweite ist, die y-Koordinate.

Tracing weiter zurück, bis Sie eine Zelle mit einem Maximalwert von 0.

Aufbau der Zeiger Matrix erreichen: Sie benötigen einen Zeiger Matrix jeweils für F, Ix und Iy. Diese Matrizen müssen nur angeben, aus welcher Matrix ein Wert stammt, da dies Ihnen anzeigt, 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, wo sie herkommt. Wenn zum Beispiel der höchste Wert, den Sie in F[5][5] haben können, durch das Ausrichten der beiden nächsten Basen kommt, wenn Sie sich in F[4][4] befinden, sollte der Fpointer [5] [5] auf F eingestellt werden, da Sie von der F Matrix dorthin gekommen sind.