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

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