4446
правок
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 8: | Строка 8: | ||
'''Нотация и определения''' | '''Нотация и определения''' | ||
Пусть X и Y – две строки алфавита <math>\Sigma</math>. ''Парное выравнивание'' строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы обозначаемые '_', таким образом, что выполняется следующее: (1) |X'| = |Y'| = <math>\ell</math>; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно. Оценка выравнивания определяется как <math>d(X', Y') = \sum_{i = 1}^{\ell} s(X'(i), Y'(i))</math>, где X'(i) (и Y'(i)) обозначает i-й символ в X' (и Y'), а s(a, b) | Пусть X и Y – две строки алфавита <math>\Sigma</math>. ''Парное выравнивание'' строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы, обозначаемые '_', таким образом, что выполняется следующее: (1) |X'| = |Y'| = <math>\ell</math>; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно. Оценка выравнивания определяется как <math>d(X', Y') = \sum_{i = 1}^{\ell} s(X'(i), Y'(i))</math>, где X'(i) (и Y'(i)) обозначает i-й символ в X' (и Y'), а s(a, b), где <math>a, b \in \Sigma \cup</math>'_', – схема оценки на основе расстояния, удовлетворяющая следующим предположениям: | ||
1. s('_', '_') = 0; | 1. s('_', '_') = 0; | ||
Строка 37: | Строка 37: | ||
''' Мера «Выравнивание деревьев» (TA)''' | ''' Мера «Выравнивание деревьев» (TA)''' | ||
В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <math>\chi</math> из k строк, <math>\chi' \supseteq \chi</math>. Эволюционное дерево <math>T{\chi'}</math> для набора <math>\chi</math> представляет собой дерево с не менее чем k узлами, | В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <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>. | ||
Строка 48: | Строка 48: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le \ | '''Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le \frac {2 (k - 1)}{k} = 2 - \frac{2}{k}.</math>''' | ||
Строка 57: | Строка 57: | ||
Вместо того чтобы вычислять <math>\binom{k}{2}</math> | Вместо того чтобы вычислять <math>\binom{k}{2}</math> оптимальных парных выравниваний для поиска наилучшей центральной строки, рандомизированный алгоритм рассматривает только p случайно выбранных строк в качестве кандидатов на наилучшую центральную строку, поэтому для работы этого метода необходимо вычислить только (k - 1)p оптимальных парных выравниваний за время <math>O(kp \ell^2)</math>, где <math>1 \le p \le k</math>. | ||
'''Теорема 3. Пусть T* - оптимальное эволюционное дерево из заданных k строк с минимальной оценкой TA. Предложен алгоритм | '''Теорема 3. Пусть T* - оптимальное эволюционное дерево из заданных k строк с минимальной оценкой TA. Предложен аппроксимационный алгоритм, позволяющий получить эволюционное дерево T, такое, что <math>\frac{TA(T)}{TA(T^*)} \le \frac{2 (k - 1)}{k} = 2 - \frac{2}{k}.</math>''' | ||
Строка 72: | Строка 72: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается нерешенным ряд задач, связанных с работой Гасфилда. Для меры SP метод центральной звезды может быть расширен до метода q-звезды (q > 2) с коэффициентом аппроксимации 2 - q/k ([1, 7], раздел 7.5 работы [8]). Существует ли алгоритм | Остается нерешенным ряд задач, связанных с работой Гасфилда. Для меры SP метод центральной звезды может быть расширен до метода q-звезды (q > 2) с коэффициентом аппроксимации 2 - q/k ([1, 7], раздел 7.5 работы [8]). Существует ли аппроксимационный алгоритм с лучшим коэффициентом аппроксимации или с меньшей временной сложностью, пока неизвестно. Для меры TA наилучшим результатом на сегодняшний день является коэффициент аппроксимации из теоремы 3. | ||
правок