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

В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <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, исходя из того, что всегда можно построить матрицу <math>| \chi'| \times \ell</math> такую, что <math>d(X'_u, X'_v) = D(X'_u, X'_v)</math> для всех e = (u, v) в <math>T_{\chi'}</math>, а нас обычно интересует нахождение множественного выравнивания с минимальным значением TA, в определении <math>TA(T_{\chi'})</math> вместо <math>d(X'_u, X'_v)</math> используется <math>D(X'_u, X'_v)</math>.