Локальное выравнивание (с вогнутыми штрафами за гэп): различия между версиями

''Гэпом'' в выравнивании <math>\mathcal{A}</math> строк X и Y считается максимальная подстрока из смежных пробелов в последовательности X' или Y'. В выравнивании имеются гэпы и выровненные символы (и X0[i], и Y0[i] не являются пробелами). Оценка пары выровненных символов основана на функции расстояния S(a, b), где a, b 2 S. Обычно S является метрикой, но в данной статье это предположение не требуется. Штраф за гэп длиной k основывается на неотрицательной функции W(k). Оценка выравнивания представляет собой сумму оценок всех выровненных символов и пробелов. Выравнивание является оптимальным, если оно имеет минимально возможную оценку.

Штрафная функция W(k) является вогнутой, если Д W(k) > Д W(k + 1) для всех k > 1, где Д W(k) = W(k + 1) - W(k).