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

В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <math>\chi</math> из k строк, <math>\chi' \supseteq \chi</math>. Эволюционное дерево <math>T{\chi'}</math> для набора <math>\chi</math> представляет собой дерево с не менее чем k узлами, в котором существует соответствие один-к-одному между узлами дерева и строками в <math>\chi'</math>. Пусть <math>X'_u \in \chi'</math> – строка для узла u. Оценка <math>T_{\chi'}</math>, обозначаемая <math>TA(T_{\chi'})</math>, определяется как <math>\sum_{e = (u, v)} D(X'_u, X'_v)</math>, где e – ребро в <math>T_{\chi'}</math>, а <math>D(X'_u, X'_v)</math> обозначает оценку оптимального парного выравнивания для <math>X'_u</math> и <math>X'_v</math>. Аналогичным образом, множественное выравнивание <math>\chi</math> согласно мере TA также может быть представлено матрицей <math>| \chi'| \times \ell</math>, где <math>| \chi' | \ge k</math>, с оценкой, определяемой как <math>\sum_{e = (u, v)} d(X'_u, X'_v)</math> (e – ребро в <math>T_{\chi'}</math>), аналогично множественному выравниванию по мере SP, где оценка является суммированием оценок выравнивания всех пар строк. В рамках меры TA, исходя из того, что всегда можно построить матрицу |/'| x I такую, что d(X0u;Xv0) = D(Xu0;Xv0) для всех e = (u; v) в T%r, а нас обычно интересует нахождение множественного выравнивания с минимальным значением TA, в определении TA{TX<) вместо d(X0u;Xv0) используется D(Xu0;Xv0).

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

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

Требуется: найти эволюционное дерево Tx для этих k строк с минимальной оценкой TA(T).