4446
правок
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями
Перейти к навигации
Перейти к поиску
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок (посмотреть исходный код)
Версия от 21:26, 4 октября 2023
, 4 октября 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
''' Мера «Выравнивание деревьев» (TA)''' | ''' Мера «Выравнивание деревьев» (TA)''' | ||
В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <math>\chi</math> из k строк, <math>\chi' \supseteq \chi</math>. Эволюционное дерево | В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <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). | ||