mały|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 i w 1981 roku. 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 i ). 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. 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) ( i Erickson, 1986) i (Myers i Miller, 1988).
Zobacz też algorytm Needlemana-Wunscha
Przypisy
Kategoria:Bioinformatyka