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

В работе Миллера и Майерса [9] рассматривается задача парного выравнивания последовательностей, в которой мера расстояния основана на модели штрафа за открытие гэпа. Авторы предложили эффективный алгоритм для решения задачи в ситуации, когда штраф за открытие гэпа является вогнутой функцией от длины гэпа.

Для оценки качества выравнивания было предложено множество различных метрик (например, расстояние редактирования, матрица замен [11]). В данной статье рассматривается модель ''штрафа за открытие гэпа''.

Штрафная функция W(k) является ''аффинной'', если W(k) = a + bk, где a, b – константы. Аффинная функция является частным случаем вогнутой функции. Задача об аффинных штрафах рассматривалась в работах [1, 6] и в [[Локальное выравнивание (с аффинными штрафами за открытие гэпа)|одноименной статье]].

'''Дано''': Две строки X и Y, функция оценки <math>\delta</math> и функция штрафа за открытие гэпа W(k).