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

Обозначим за <math>\Xi = X_1, X_2, ..., X_k</math> множество k > 2 строк алфавита <math>\Sigma</math>. ''Множественное выравнивание'' A этих k строк отображает <math>X_1, X_2, ..., X_k</math> на <math> = X'_1, X'_2, ..., X'_k</math>, которые могут содержать пробелы таким образом, что выполняется следующее:

Оценка множественного выравнивания A, обозначаемая SP(A), определяется как сумма оценок парных выравниваний, индуцированных A, т. е. Pi<j d{X\, Xp =.

Задача № 1. Множественное выравнивание последовательностей с минимальным значением оценки SP

Дано: набор из k строк, схема оценки s.

Требуется: найти множественное выравнивание A этих k строк с минимальной оценкой SP(A).

В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор / из k строк, /' 2 /-. Эволюционное дерево Tx/ для набора / представляет собой дерево с не менее чем k узлами, в котором существует соответствие один-к-одному между узлами дерева и строками в /'. Пусть Xu 0 /' – строка для узла u. Оценка Tx/, обозначаемая TA(TX/), определяется как ~Y^,e=<u v\ D(Xu0;Xv0), где e – ребро в Txi, а D(X0u;Xv0) обозначает оценку оптимального парного выравнивания для Xu0 и Xv0. Аналогичным образом, множественное выравнивание / согласно мере TA также может быть представлено матрицей j/'| x I, где \x'\ > k, с оценкой, определяемой как Pe=(u;v) d(Xu0;Xv0)(e – ребро в Txr), аналогично множественному выравниванию по мере SP, где оценка является суммированием оценок выравнивания всех пар строк. В рамках меры TA, исходя из того, что всегда можно построить матрицу |/'| x I такую, что d(X0u;Xv0) = D(Xu0;Xv0) для всех e = (u; v) в T%r, а нас обычно интересует нахождение множественного выравнивания с минимальным значением TA, в определении TA{TX<) вместо d(X0u;Xv0) используется D(Xu0;Xv0).