Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями

Пусть X и Y – две строки алфавита <math>\Sigma</math>. ''Парное выравнивание'' строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы обозначаемые '_', таким образом, что выполняется следующее: (1) |X'| = |Y'| = <math>\ell</math>; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно. Оценка выравнивания определяется как <math>d(X', Y') = \sum_{i = 1}^{\ell} s(X'(i), Y'(i))</math>, где X'(i) (и Y'(i)) обозначает i-й символ в X' (и Y'), а s(a, b) при <math>a, b \in \Sigma \cup</math>'_' – схема оценки на основе расстояния, удовлетворяющая следующим предположениям.