Algorytm Smitha-Watermana

Algorytm Smitha-Watermana – algorytm bazujący na programowaniu dynamicznym umożliwiający poszukiwanie optymalnych lokalnych dopasowań sekwencji. Jest często wykorzystywany w bioinformatyce do poszukiwań dopasowań sekwencji nukleotydów i aminokwasów.

Przykład algorytmu Smitha-Watermana. Strzałki pokazują ścieżkę algorytmu przez macierz. Czerwone strzałki pokazują ostateczne najlepsze lokalne dopasowanie.

Algorytm został po raz pierwszy zaproponowany przez Temple'a F. Smitha(inne języki) i Michaela S. Watermana(inne języki) w 1981 roku.^[1] Podobnie jak algorytm Needleman-Wunscha, którego jest wariantem, algorytm Smitha-Watermana jest algorytmem programowania dynamicznego. W związku z tym posiada on pożądaną cechę, że gwarantuje znalezienie optymalnego lokalnego dopasowania względem używanego systemu punktacji (który obejmuje macierz substytucji(inne języki) i schemat punktacji przerw(inne języki)). Główną różnicą w stosunku do algorytmu Needleman-Wunscha jest to, że ujemne komórki macierzy punktacji są ustawiane na zero, co powoduje, że lokalne dopasowania (a więc dodatnio punktowane) są widoczne.^[2] Procedura śledzenia ścieżki rozpoczyna się w komórce macierzy o najwyższej punktacji i trwa do napotkania komórki o punktacji zero, co prowadzi do uzyskania najwyżej punktowanego lokalnego dopasowania. Ze względu na swoją złożoność czasową rzędu sześcianowego, często nie może być praktycznie stosowany w przypadku problemów o dużych skalach i jest zastępowany na rzecz bardziej efektywnych obliczeniowo alternatyw, takich jak (Gotoh, 1982),^[3] (Altschul(inne języki) i Erickson, 1986)^[4] i (Myers i Miller, 1988)^[5].

Zobacz też edytuj

algorytm Needlemana-Wunscha

Przypisy edytuj

↑ T.F.T.F. Smith T.F.T.F., M.S.M.S. Waterman M.S.M.S., Identification of common molecular subsequences, „Journal of Molecular Biology”, 147 (1), 1981, s. 195–197, DOI: 10.1016/0022-2836(81)90087-5, ISSN 0022-2836 [dostęp 2024-02-05] .
↑ Algorithms in bioinformatics : theory and implementation | WorldCat.org [online], search.worldcat.org [dostęp 2024-02-05] (ang.).
↑ O.O. Gotoh O.O., An improved algorithm for matching biological sequences, „Journal of Molecular Biology”, 162 (3), 1982, s. 705–708, DOI: 10.1016/0022-2836(82)90398-9, ISSN 0022-2836, PMID: 7166760 [dostęp 2024-02-05] .
↑ Stephen F.S.F. Altschul Stephen F.S.F., Bruce W.B.W. Erickson Bruce W.B.W., Optimal sequence alignment using affine gap costs, „Bulletin of Mathematical Biology”, 48 (5-6), 1986, s. 603–616, DOI: 10.1007/BF02462326, ISSN 0092-8240 [dostęp 2024-02-05] (ang.).
↑ E.W.E.W. Myers E.W.E.W., W.W. Miller W.W., Optimal alignments in linear space, „Computer applications in the biosciences: CABIOS”, 4 (1), 1988, s. 11–17, DOI: 10.1093/bioinformatics/4.1.11, ISSN 0266-7061, PMID: 3382986 [dostęp 2024-02-05] .

[1] T.F.T.F. Smith T.F.T.F., M.S.M.S. Waterman M.S.M.S., Identification of common molecular subsequences, „Journal of Molecular Biology”, 147 (1), 1981, s. 195–197, DOI: 10.1016/0022-2836(81)90087-5, ISSN 0022-2836 [dostęp 2024-02-05] .

[2] Algorithms in bioinformatics : theory and implementation | WorldCat.org [online], search.worldcat.org [dostęp 2024-02-05] (ang.).

[3] O.O. Gotoh O.O., An improved algorithm for matching biological sequences, „Journal of Molecular Biology”, 162 (3), 1982, s. 705–708, DOI: 10.1016/0022-2836(82)90398-9, ISSN 0022-2836, PMID: 7166760 [dostęp 2024-02-05] .

[4] Stephen F.S.F. Altschul Stephen F.S.F., Bruce W.B.W. Erickson Bruce W.B.W., Optimal sequence alignment using affine gap costs, „Bulletin of Mathematical Biology”, 48 (5-6), 1986, s. 603–616, DOI: 10.1007/BF02462326, ISSN 0092-8240 [dostęp 2024-02-05] (ang.).

[5] E.W.E.W. Myers E.W.E.W., W.W. Miller W.W., Optimal alignments in linear space, „Computer applications in the biosciences: CABIOS”, 4 (1), 1988, s. 11–17, DOI: 10.1093/bioinformatics/4.1.11, ISSN 0266-7061, PMID: 3382986 [dostęp 2024-02-05] .

[1]

[2]

[3]

[4]

[5]