Algorytm Smitha-Watermana
Algorytm Smitha-Watermana to metoda oparta na programowaniu dynamicznym, która pozwala na znajdowanie optymalnych lokalnych dopasowań sekwencji. Jest on szeroko stosowany w bioinformatyce do identyfikacji dopasowań sekwencji zarówno nukleotydów, jak i aminokwasów.
Po raz pierwszy algorytm ten został przedstawiony przez Temple’a F. Smitha oraz Michaela S. Watermana w 1981 roku. Podobnie jak algorytm Needleman-Wunscha, z którym jest powiązany, algorytm Smitha-Watermana również opiera się na programowaniu dynamicznym. Dzięki temu zapewnia on znalezienie optymalnego lokalnego dopasowania w odniesieniu do stosowanego systemu punktacji, który zawiera macierz substytucji oraz schemat punktacji dla przerw. Główną różnicą w porównaniu z algorytmem Needleman-Wunscha jest to, że ujemne wartości w komórkach macierzy punktacji są ustawiane na zero, co umożliwia widoczność lokalnych dopasowań (a więc tych punktowanych dodatnio). Proces śledzenia ścieżki rozpoczyna się w komórce macierzy o najwyższej punktacji i kontynuuje, aż natrafi na komórkę o punktacji zero, co prowadzi do uzyskania najlepiej punktowanego lokalnego dopasowania. Z uwagi na swoją złożoność czasową, która wynosi rzędu sześcianowego, algorytm ten często nie jest praktycznie wykorzystywany przy dużych problemach i jest zastępowany bardziej efektywnymi alternatywami, takimi jak (Gotoh, 1982), (Altschul i Erickson, 1986) oraz (Myers i Miller, 1988).
