Algorytm Smitha-Watermana

Wikipedia:Weryfikowalność
Ten artykuł od 2022-05 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
Przykład algorytmu Smitha-Watermana. Strzałki pokazują ścieżkę algorytmu przez macierz. Czerwone strzałki pokazują ostateczne najlepsze lokalne dopasowanie.

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.

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ż

Przypisy

  1. ↑ T.F. Smith, M.S. Waterman, 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. Gotoh, 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. Altschul, Bruce W. Erickson, 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. Myers, W. Miller, 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].