Algorytm Needleman-Wunsch wykonuje globalne dopasowania na dwóch sekwencjach. Jest on powszechnie stosowany w dziedzinie bioinformatyki do wyrównywania białek lub sekwencji nukleotydów. Algorytm ten został opublikowany w 1970 roku przez Saula B. Needleman’a oraz Christiana D. Wunsch’a. Algorytm Needleman-Wunsch jest przykładem programowania dynamicznego i był pierwszą aplikacją do porównywania sekwencji biologicznych.
Krok 1) Algorytm oblicza macierz F na podstawie wprowadzonych przez użytkownika dwóch sekwencji i kary za luki.
F(i,j) = max of [
Przekątna: S(i,j) + F(i-1, j-1)
Lewa S(i,j) + F(i-1, j) + Gp
Góra: S(i,j) + F(i, j-1) + Gp
]
Gdzie S i jest macierzą podstawienia, a Gp jest karą za luki
Macierz podstawienia używa BLOSUM62
Krok 2)
Gdy macierz F jest obliczana, pozycja FNM daje maksymalny wynik wśród wszystkich możliwych przebiegów..
Obliczanie optymalnego dostosowania:
a. Zacznij od dolnej prawej komórki i porównaj wartość trzech możliwych źródeł (przekątna, lewo, powyżej), aby zobaczyć skąd pochodzi.
b. Jeśli przekątna, następnie Ai oraz Bj są wyrównane
c. Jeśli góra, następnie Ai jest wyrównane z luką, oraz
d. Jeśli lewo, następnie Bj jest wyrównane z luką.
(Więcej niż jeden wybór może mieć taką samą wartość, co prowadzi do alternatywnych optymalnych przebiegów)
Krok 3)
Algorytm będzie obliczał wynik wyrównania oraz w oparciu o ścieżki wcześniej stworzona macierz będzie kolorowana.
Implementacja dostępna w pliku NeedlemanWunsch.zip dostępnym pod adresem
http://cs.elitepc.pl/NeedlemanWunsch
lub
tutaj
Autor: Krzysztof Wołk
