Prześledzenie w algorytmie Smitha-Watemana z karą w postaci luki afektywnej

Question

Próbuję zastosować algorytm Smitha-Watermana do lokalnego wyrównania sekwencji za pomocą funkcji kary luki afinicznej. Myślę, że rozumiem, jak inicjować i obliczać macierze wymagane do obliczania wyników wyrównania, ale nie mam pojęcia, jak to zrobić, by znaleźć wyrównanie. W celu uzyskania macierzy 3 wymagane I mają następujące oznaczenia

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) 

Ja pewności, jeśli trzeba pojedynczą matrycę stosie z, lub po 1? Będziemy wdzięczni za wszelkie wyjaśnienia dotyczące sposobu śledzenia wyniku maks. W punkcie F.

Answer 1

Ważną rzeczą, o której należy pamiętać w związku ze śladami w Smith-Waterman, jest to, że macierz, której wartość określa, określa kierunek, w którym się poruszasz. Tak więc, jeśli jesteś w F poruszasz się po przekątnej, jeśli jesteś w Ix, poruszasz się poziomo, a jeśli jesteś w Iy, poruszasz się w pionie. Oznacza to, że wszystko, co musisz przechowywać w matrycy wskaźnika, to macierz, z której przybyłeś do kwadratu. Macierz, z której się wywodzisz, a nie ta, do której zmierzasz, wyznacza kierunek, z którego chcesz jechać.

Na przykład:

że jesteś w F[5][5]:

• Jeśli matryca wskaźnik mówi, aby przejść do Ix, przejdź do Ix[4][4]
• Jeśli matryca wskaźnik mówi, aby przejść do Iy, przejdź do Iy[4][4]
• Jeśli matryca wskaźnika mówi, aby przejść do F, przejdź do F[4][4]

natomiast jeśli jesteś w Ix[5][5]:

• Jeśli matryca wskaźnik mówi, aby przejść do Ix, przejdź do Ix[4][5]
• Jeśli matryca wskaźnik mówi, aby przejść do F, przejdź do F[4][5]

Lub jeśli jesteś na Iy[5][5]:

• Jeśli matryca wskaźnik mówi, aby przejść do Iy, przejdź do Iy[5][4]
• Jeśli matryca wskaźnik mówi, aby przejść do F, przejdź do F[5][4]

Zakładając, że pierwszy indeks jest współrzędna x, a drugi współrzędna y.

Kontynuuj śledzenie wstecz aż komórkę o maksymalnej wartości 0.

Budowanie matrycę wskaźnik: Musisz jedną matrycę wskaźnik za każdą F, Ix i Iy. Te macierze muszą jedynie wskazać, z jakiej matrycy pochodzi wartość, ponieważ to wskazuje kierunek, w którym się poruszasz.Tak więc, kiedy przechodzisz przez fazę programowania dynamicznego algorytmu, powinieneś także budować matryce wskaźnikowe. Za każdym razem, gdy przechowujesz nową maksymalną wartość w komórce w F, Ix lub Iy, powinieneś zaktualizować odpowiednią macierz, aby wskazać, skąd pochodzi. Jeśli na przykład najwyższa wartość, jaką można uzyskać w F[5][5], polega na wyrównaniu dwóch następnych zasad, gdy jesteś w F[4][4], Fpointer [5] [5] powinien być ustawiony na F, ponieważ dostałeś się tam z macierzy F.