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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Примечания[править | править код]

  1. Smith, Temple F.; and Waterman, Michael S. (1981). «Identification of Common Molecular Subsequences». Journal of Molecular Biology 147: 195-197. DOI:10.1016/0022-2836(81)90087-5. PMID 7265238. (недоступная ссылка)