Smith-Watermanův algoritmus je navržen tak, aby získal lokální zarovnání sekvencí , to znamená, aby identifikoval podobné oblasti dvou nukleotidových nebo proteinových sekvencí . Na rozdíl od Needleman-Wunschova algoritmu , který zarovnává sekvence po celé délce, Smith-Watermanův algoritmus porovnává segmenty všech možných délek a optimalizuje míru podobnosti ve všech segmentech a všechna zarovnání těchto segmentů.
Algoritmus navrhli T. F. Smith a M. Waterman v roce 1981 [1] . Stejně jako Needleman-Wunschův algoritmus, Smith-Watermanův algoritmus využívá principu dynamického programování . Zaručuje nalezení optimálního místního sladění ve vztahu k měřítku hodnocení kvality, které používá. Tímto měřítkem hodnocení je takzvaná váha zarovnání nebo skóre, které zahrnuje použití substituční matice a penalizací za "mezery" (tj. inzerce a delece).
| Struny | |
|---|---|
| Míry podobnosti řetězců | |
| Hledání podřetězců | |
| palindromy | |
| Sekvenční zarovnání | |
| Struktury přípon | |
| jiný | |