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

В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <math>\chi</math> из k строк, <math>\chi' \supseteq \chi</math>. Эволюционное дерево 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).