Алгоритм Смита — Ватермана

Алгоритм Смита — Ватермана предназначен для получения локального выравнивания последовательностей, то есть для выявления сходных участков двух нуклеотидных или белковых последовательностей. В отличие от алгоритма Нидлмана — Вунша, который осуществляет выравнивание последовательностей по всей длине, алгоритм Смита — Ватермана сравнивает отрезки всех возможных длин и оптимизирует меру сходства по всем отрезкам и всем выравниваниям этих отрезков.

Алгоритм был предложен Т. Ф. Смитом^[англ.] и М. Ватерманом^[англ.] в 1981^[1]. Подобно алгоритму Нидлмана — Вунша, алгоритм Смита — Ватермана использует принцип динамического программирования. Он гарантирует нахождение оптимального, относительно используемой им меры оценки качества, локального выравнивания. Эта мера оценки — так называемый вес, или счёт (Score) выравнивания, предусматривающий использование матрицы замен^[англ.] и штрафов за «гэпы»^[англ.] (то есть вставки и делеции).

В другом языковом разделе есть более полная статья Smith–Waterman algorithm (англ.). Вы можете помочь проекту, расширив текущую статью с помощью перевода