Algorytm parami
Algorytm parami to technika algorytmiczna wywodząca się z programowania dynamicznego . Algorytmy parami mają kilka zastosowań, w tym porównanie profilu białkowego (macierz punktacji reszt dla jednej lub więcej wyrównanych sekwencji) z trzema ramkami translacji nici DNA, umożliwiając przesunięcie ramek. Najbardziej niezwykłą cechą PairWise w porównaniu z innymi narzędziami do wyrównywania białek-DNA jest to, że PairWise umożliwia przesunięcie ramek podczas wyrównywania.
Historia
Jednym z najwcześniejszych zastosowań PairWise do problemów w bioinformatyce był Ewan Birney .
Przesunięcie ramki odnosi się do zjawisk, w których w jednej nici DNA występuje więcej niż jedna ramka translacji. W przypadku normalnych narzędzi do dopasowywania białka do DNA najpierw wybierają jedną z trzech ramek do translacji DNA na sekwencję białka , a następnie porównują ją z danym białkiem. Takie dopasowanie opiera się na założeniu, że ramka translacji DNA nie jest przerywana dla całej nici DNA. Jednak generalnie nie jest to prawdą.
Algorytm PairWise jest wariantem najlepszego lokalnego algorytmu wyrównania algorytmu Smitha-Watermana . Wszystkie te algorytmy należą do klasy znanej jako algorytmy minimalnej edycji łańcucha. Główne różnice między algorytmem PairWise a innymi algorytmami dopasowywania polegają na tym, że oprócz zwykłych kar, takich jak kara za otwarcie przerwy (GOP), kara za przedłużenie przerwy (GEP) i dopasowanie, PairWise wprowadził dwie nowe kary zwane karą za otwarcie ramki (FOP) i karą za przedłużenie ramki ( FEP), które zostaną poniesione w przypadku odpowiednio zaakceptowania i przedłużenia przesunięcia ramek.
Ilustracja
Figura 1 ilustruje wynik dopasowania, gdy jedna sekwencja białka i jedna sekwencja DNA zostały dopasowane przy użyciu normalnego algorytmu dopasowania białko-DNA. Zastosowaną ramką była ramka 1 dla sekwencji DNA. Jak pokazano na rysunku, w dopasowaniu była przerwa 2 aminokwasów (6 kwasów nukleinowych), co daje łączny niski wynik -2.
Rysunek 2 ilustruje wyrównany wynik przy użyciu funkcji PairWise. Używając tej samej sekwencji DNA i białek oraz z karami zmodyfikowanymi jak poniżej. Strzałka wskazuje miejsce, w którym nastąpiło przesunięcie ramki. W tym nukleotydzie (G) ramka translacji została przesunięta z ramki pierwszej do ramki drugiej (linia przerywana). Ta zmiana zaowocowała znacznie lepszym dopasowaniem, które ma wynik 9.
- Bibliografia _ _ Thompson, J.; Gibson, T. (1996). „PairWise i SearchWise: Znalezienie optymalnego dopasowania w jednoczesnym porównaniu profilu białkowego ze wszystkimi ramkami translacji DNA” . Badania kwasów nukleinowych . 24 (14): 2730–2739. doi : 10.1093/nar/24.14.2730 . PMC 145991 . PMID 8759004 .