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

Штрафная функция W(k) является ''вогнутой'', если <math>\bigtriangleup W(k) \ge \bigtriangleup W(k + 1)</math> для всех <math>k \ge 1</math>, где <math>\bigtriangleup W(k) = W(k + 1) - W(k)</math>.

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

Штрафная функция W(k) является ''P-кусочной аффинной кривой'', если область W можно разбить на P интервалов, <math>(\tau_1 = 1, \chi_1), (\tau_2, \chi_2), ..., (\tau_p, \chi_p = \infty)</math>, где <math>\tau_i = \chi_{i - 1} + 1</math> для всех <math>1 < i \le p</math>, такое, что для каждого интервала значения W описываются аффинной функцией. Более точно, для любого k 2 fa, Xi)> W(k) = ai + bik для некоторых постоянных ai, bi.