biotechnologia


 
 

Algorytm Needleman-Wunsch

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

Komentarze

Widok Uszereguj
Tylko zarejestrowani mogą dodawać komentarze. Zarejestruj się/Zaloguj

Podręcznik biotechnologii

Kto jest online

206 gości oraz 0 użytkowników online.

Jesteś niezarejestrowanym lub niezalogowanym użytkownikiem.


 
 
 
Partnerzy:

laboratoria.net Nauka w Polsce Academio Fundacja NanoNet BioCen - BioCentrum Edukacji Naukowej Notatek.pl cebioforum.com materialyinzynierskie.pl Wspieram.to - POLSKI KICKSTARTER - Polska platforma finansowania społecznoœciowego.Tu zrealizujš się Twoje pomysły. VitaInSilica Portal popularnonaukowy matura.biomist.pl

Portal: Redakcja . Współpraca . Kontakt . Polecamy



Wszystkie prawa zastrzeżone 2006-2016 e-biotechnologia.pl
stat4u