Algoritmul Smith-Waterman este conceput pentru a obține alinierea secvenței locale , adică pentru a identifica regiuni similare din două secvențe de nucleotide sau proteine . Spre deosebire de algoritmul Needleman-Wunsch , care aliniază secvențele de-a lungul întregii lungimi, algoritmul Smith-Waterman compară segmente de toate lungimile posibile și optimizează măsura similarității pe toate segmentele și toate aliniamentele acestor segmente.
Algoritmul a fost propus de T. F. Smith și M. Waterman în 1981 [1] . Ca și algoritmul Needleman-Wunsch, algoritmul Smith-Waterman folosește principiul programării dinamice . Acesta garantează găsirea optimă, raportată la măsura de evaluare a calității utilizată de acesta, alinierea locală. Această măsură de evaluare este așa-numita pondere de aliniere, sau Scor, care implică utilizarea unei matrice de substituție și penalități pentru „lacunele” (adică inserții și ștergeri).
| Siruri de caractere | |
|---|---|
| Măsuri de similitudine a șirurilor | |
| Căutare subșir | |
| palindromuri | |
| Alinierea secvenței | |
| Structuri de sufix | |
| Alte | |