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

Пусть X и Y – две строки алфавита <math>\Sigma</math>. Парное выравнивание A строк 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>'_' – схема оценки на основе расстояния, удовлетворяющая следующим предположениям.

1. s('_0;‘_0) = 0;

s(x;z) < s(x;y) + s(y;z)).

Обозначим за / = X1 ; X 2... ; Xk множество k > 2 строк алфавита £. Множественное выравнивание A этих k строк отображает Xi, Xi,... , Xk на X[, X'2,... Xk, которые могут содержать пробелы таким образом, что выполняется следующее: (1) \X[ \ = jX2 0 j = ■ ■ = jX0k j = I; (2) удаление пробелов из элемента Xi' превращает его в Xi для всех 1 < i < k. Множественное выравнивание A может быть представлено в виде матрицы k x I.