Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 13 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Множественное выравнивание строк; глобальная задача выравнивания нескольких строк | |||
== Постановка задачи == | == Постановка задачи == | ||
Множественное выравнивание последовательностей является важной задачей вычислительной биологии. Она применяется в таких областях, как поиск высококонсервативных субрегионов в заданном наборе биологических последовательностей и вывод истории эволюции набора таксонов на основе связанных с ними биологических последовательностей (см., например, [6]). Был предложен ряд мер для оценки качества множественного выравнивания, однако до выхода работы Гасфилда ни для одной из этих мер не было известно эффективных методов вычисления оптимального выравнивания. В работе Гасфилда [5] приведены два вычислительно эффективных алгоритма | Множественное выравнивание последовательностей является важной задачей вычислительной биологии. Она применяется в таких областях, как поиск высококонсервативных субрегионов в заданном наборе биологических последовательностей и вывод истории эволюции набора таксонов на основе связанных с ними биологических последовательностей (см., например, [6]). Был предложен ряд мер для оценки качества множественного выравнивания, однако до выхода упомянутой работы Гасфилда ни для одной из этих мер не было известно эффективных методов вычисления оптимального выравнивания. В работе Гасфилда [5] приведены два вычислительно эффективных аппроксимационных алгоритма множественного выравнивания для двух мер с коэффициентом аппроксимации менее 2. Для одной из мер также получен рандомизированный алгоритм, который работает значительно быстрее и с высокой вероятностью выдает множественное выравнивание с малыми границами ошибки. В данной работе впервые были представлены аппроксимационные алгоритмы (с гарантированными границами ошибок) для этой задачи. | ||
'''Нотация и определения''' | '''Нотация и определения''' | ||
Пусть X и Y – две строки алфавита <math>\Sigma</math>. Парное выравнивание | Пусть 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(' | |||
1. s('_', '_') = 0; | |||
2. неравенство треугольника: для любых трех символов, x, y, z выполняется соотношение | 2. неравенство треугольника: для любых трех символов, x, y, z выполняется соотношение | ||
s(x | s(x, z) <math>\le</math> s(x, y) + s(y, z). | ||
Обозначим за | |||
Обозначим за <math>\chi = X_1, X_2, ..., X_k</math> множество k > 2 строк алфавита <math>\Sigma</math>. ''Множественное выравнивание'' A этих k строк отображает <math>X_1, X_2, ..., X_k</math> на <math> = X'_1, X'_2, ..., X'_k</math>, которые могут содержать пробелы таким образом, что выполняется следующее: | |||
(1) <math>|X'_1| = |X'_2| = |X'_k| = \ell</math>; | |||
(2) удаление пробелов из элемента <math>X'_i</math> превращает его в <math>X_i</math> для всех <math>1 \le i \le k</math>. Множественное выравнивание A может быть представлено в виде матрицы <math>k \times \ell</math>. | |||
'''Мера «Сумма пар» (SP)''' | '''Мера «Сумма пар» (SP)''' | ||
Оценка множественного выравнивания A, обозначаемая SP(A), определяется как сумма оценок парных выравниваний, индуцированных A, т. е. | Оценка множественного выравнивания A, обозначаемая SP(A), определяется как сумма оценок парных выравниваний, индуцированных A, т. е. <math>\sum_{i < j} d(X'_i, X'_j) = \sum_{i < j} \sum^{\ell}_{p = 1} s(X'_i[p], X'_j[p])</math>, где <math>1 \le i \le j \le k</math>. | ||
Задача № 1. Множественное выравнивание последовательностей с минимальным значением оценки SP | '''Задача № 1'''. Множественное выравнивание последовательностей с минимальным значением оценки SP | ||
Дано: набор из k строк, схема оценки s. | '''Дано''': набор из k строк, схема оценки s. | ||
Требуется: найти множественное выравнивание A этих k строк с минимальной оценкой SP(A). | '''Требуется''': найти множественное выравнивание A этих k строк с минимальной оценкой SP(A). | ||
''' Мера «Выравнивание деревьев» (TA)''' | ''' Мера «Выравнивание деревьев» (TA)''' | ||
В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор / из 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>. | ||
Задача № 2. Множественное выравнивание последовательностей с минимальным значением оценки ТА | '''Задача № 2'''. Множественное выравнивание последовательностей с минимальным значением оценки ТА | ||
Дано: набор из k строк, схема оценки s. | '''Дано''': набор из k строк, схема оценки s. | ||
Требуется: найти эволюционное дерево | '''Требуется''': найти эволюционное дерево T для этих k строк с минимальной оценкой TA(T). | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что | '''Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le \frac {2 (k - 1)}{k} = 2 - \frac{2}{k}.</math>''' | ||
Метод центральной звезды стремится получить такое выравнивание, которое согласуется с оптимальным парным выравниванием центральной строки со всеми остальными строками. Граница выводится на основе неравенства треугольника оценочной функции. Временная сложность данного метода составляет O( | Метод центральной звезды стремится получить такое выравнивание, которое согласуется с оптимальным парным выравниванием центральной строки со всеми остальными строками. Граница выводится на основе неравенства треугольника оценочной функции. Временная сложность данного метода составляет <math>O(k^2 \ell^2)</math>, где <math>\ell^2</math> – время решения задачи парного выравнивания методом динамического программирования, а <math>k^2</math> – время поиска центральной строки <math>X_c</math>, дающей минимальное значение <math>\sum_{i \ne c} D(X_c, X_i).</math> | ||
'''Теорема 2. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен рандомизированный алгоритм, который позволяет получить выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le 2 + \frac{1}{r - 1}</math> с вероятностью не менее <math>1 - \Big( \frac{r - 1}{r} \Big)^p</math> для любых <math>r > 1</math> и <math>p \ge 1.</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. Предложен аппроксимационный алгоритм, позволяющий получить эволюционное дерево T, такое, что <math>\frac{TA(T)}{TA(T^*)} \le \frac{2 (k - 1)}{k} = 2 - \frac{2}{k}.</math>''' | |||
В ходе работы алгоритма сначала вычисляются все <math>\binom{k}{2}</math> оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку <math>X_i</math>, а вес каждого ребра <math>(X_i, X_j)</math> равен <math>D(X_i, X_j)</math>. Этот шаг определяет общую временную сложность <math>O(k^2 \ell^2)</math>. Затем для этого графа вычисляется минимальное остовное дерево. Множественное выравнивание должно быть согласовано с оптимальными парными выравниваниями, представленными ребрами этого минимального остовного дерева. | |||
== Применение == | == Применение == | ||
| Строка 62: | Строка 69: | ||
В последнее время множественное выравнивание последовательностей используется также для выявления некодирующих РНК (нкРНК) [3]. При этом типе множественного выравнивания мы выравниваем не только базовые последовательности, но и вторичные структуры РНК (см. гл. 16 в [ ] для краткого ознакомления со вторичной структурой РНК). Исследователи считают, что нкРНК, принадлежащие к одному семейству, должны содержать общие компоненты, обеспечивающие сходную вторичную структуру. Множественное выравнивание способно помочь найти и идентифицировать эти общие компоненты. | В последнее время множественное выравнивание последовательностей используется также для выявления некодирующих РНК (нкРНК) [3]. При этом типе множественного выравнивания мы выравниваем не только базовые последовательности, но и вторичные структуры РНК (см. гл. 16 в [10] для краткого ознакомления со вторичной структурой РНК). Исследователи считают, что нкРНК, принадлежащие к одному семейству, должны содержать общие компоненты, обеспечивающие сходную вторичную структуру. Множественное выравнивание способно помочь найти и идентифицировать эти общие компоненты. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается нерешенным ряд задач, связанных с работой Гасфилда. Для меры 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. | ||
Другим интересным направлением, связанным с этой задачей, является задача множественного выравнивания последовательностей с ограничениями [9], в которой требуется, чтобы множественное выравнивание содержало определенные выровненные символы относительно заданной последовательности с ограничениями. Наиболее известным результатом [ ] является аппроксимационный алгоритм (также следующий методу центральной звезды), который позволяет получить выравнивание с коэффициентом аппроксимации 2 - 2/k для k строк. | Другим интересным направлением, связанным с этой задачей, является задача множественного выравнивания последовательностей с ограничениями [9], в которой требуется, чтобы множественное выравнивание содержало определенные выровненные символы относительно заданной последовательности с ограничениями. Наиболее известным результатом [2] является аппроксимационный алгоритм (также следующий методу центральной звезды), который позволяет получить выравнивание с коэффициентом аппроксимации 2 - 2/k для k строк. | ||
Что касается сложности, то Ван и Цзян [11] первыми доказали NP-трудность задачи с мерой SP при неметрической мере расстояния над алфавитом из 4 символов. Недавно в работе [4] было доказано, что задача множественного выравнивания с мерой SP, выравниванием по методу звезды и мерой TA является NP-трудной для всех двухсимвольных или больших алфавитов при любой метрике. Разработка эффективных аппроксимационных алгоритмов с хорошими границами для любой из этих мер весьма желательна. | Что касается сложности, то Ван и Цзян [11] первыми доказали NP-трудность задачи с мерой SP при ''неметрической'' мере расстояния над алфавитом из 4 символов. Недавно в работе [4] было доказано, что задача множественного выравнивания с мерой SP, выравниванием по методу звезды и мерой TA является NP-трудной для всех двухсимвольных или больших алфавитов при ''любой метрике''. Разработка эффективных аппроксимационных алгоритмов с хорошими границами для любой из этих мер весьма желательна. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
| Строка 77: | Строка 84: | ||
В экспериментах использовалась следующая схема оценки: s(a | В экспериментах использовалась следующая схема оценки: s(a, b) = 0, если a = b; s(a, b) = 1, если либо a, либо b – пробел; в противном случае s(a, b) = 2. Поскольку было показано, что вычисление оптимального множественного выравнивания с минимальной оценкой SP является NP-трудной задачей, авторы оценивают эффективность своих алгоритмов, используя нижнюю границу <math>\sum_{i < j} D(X_i, X_j)</math> (напомним, что <math>D(X_i, X_j)</math> – это оценка оптимального парного выравнивания <math>X_i</math> и <math>X_j</math>). Было выровнено 19 сходных аминокислотных последовательностей со средней длиной 60 гомеобоксов от разных видов. Отношение оценок, полученных при выравнивании методом центральной звезды, к нижней границе составляет всего 1,018, что далеко от наихудшей границы ошибки, указанной в Теореме 1. Также было проведено выравнивание 10 не очень похожих последовательностей вблизи гомеобоксов, для которых отношение оценок выравнивания к нижней границе составило 1,162. Результаты также показывают, что выравнивание, полученное с помощью рандомизированного алгоритма, обычно не слишком далеко от нижней границы. | ||
== См. также == | == См. также == | ||
| Строка 104: | Строка 111: | ||
11. Wang, L. Jiang, T.: On the complexity of multiple sequence alignment. J. Comp. Biol. 1,337-48 (1994) | 11. Wang, L. Jiang, T.: On the complexity of multiple sequence alignment. J. Comp. Biol. 1,337-48 (1994) | ||
[[Категория: Совместное определение связанных терминов]] | |||
Текущая версия от 12:03, 7 декабря 2024
Ключевые слова и синонимы
Множественное выравнивание строк; глобальная задача выравнивания нескольких строк
Постановка задачи
Множественное выравнивание последовательностей является важной задачей вычислительной биологии. Она применяется в таких областях, как поиск высококонсервативных субрегионов в заданном наборе биологических последовательностей и вывод истории эволюции набора таксонов на основе связанных с ними биологических последовательностей (см., например, [6]). Был предложен ряд мер для оценки качества множественного выравнивания, однако до выхода упомянутой работы Гасфилда ни для одной из этих мер не было известно эффективных методов вычисления оптимального выравнивания. В работе Гасфилда [5] приведены два вычислительно эффективных аппроксимационных алгоритма множественного выравнивания для двух мер с коэффициентом аппроксимации менее 2. Для одной из мер также получен рандомизированный алгоритм, который работает значительно быстрее и с высокой вероятностью выдает множественное выравнивание с малыми границами ошибки. В данной работе впервые были представлены аппроксимационные алгоритмы (с гарантированными границами ошибок) для этой задачи.
Нотация и определения
Пусть X и Y – две строки алфавита [math]\displaystyle{ \Sigma }[/math]. Парное выравнивание строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы, обозначаемые '_', таким образом, что выполняется следующее: (1) |X'| = |Y'| = [math]\displaystyle{ \ell }[/math]; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно. Оценка выравнивания определяется как [math]\displaystyle{ d(X', Y') = \sum_{i = 1}^{\ell} s(X'(i), Y'(i)) }[/math], где X'(i) (и Y'(i)) обозначает i-й символ в X' (и Y'), а s(a, b), где [math]\displaystyle{ a, b \in \Sigma \cup }[/math]'_', – схема оценки на основе расстояния, удовлетворяющая следующим предположениям:
1. s('_', '_') = 0;
2. неравенство треугольника: для любых трех символов, x, y, z выполняется соотношение s(x, z) [math]\displaystyle{ \le }[/math] s(x, y) + s(y, z).
Обозначим за [math]\displaystyle{ \chi = X_1, X_2, ..., X_k }[/math] множество k > 2 строк алфавита [math]\displaystyle{ \Sigma }[/math]. Множественное выравнивание A этих k строк отображает [math]\displaystyle{ X_1, X_2, ..., X_k }[/math] на [math]\displaystyle{ = X'_1, X'_2, ..., X'_k }[/math], которые могут содержать пробелы таким образом, что выполняется следующее:
(1) [math]\displaystyle{ |X'_1| = |X'_2| = |X'_k| = \ell }[/math];
(2) удаление пробелов из элемента [math]\displaystyle{ X'_i }[/math] превращает его в [math]\displaystyle{ X_i }[/math] для всех [math]\displaystyle{ 1 \le i \le k }[/math]. Множественное выравнивание A может быть представлено в виде матрицы [math]\displaystyle{ k \times \ell }[/math].
Мера «Сумма пар» (SP)
Оценка множественного выравнивания A, обозначаемая SP(A), определяется как сумма оценок парных выравниваний, индуцированных A, т. е. [math]\displaystyle{ \sum_{i \lt j} d(X'_i, X'_j) = \sum_{i \lt j} \sum^{\ell}_{p = 1} s(X'_i[p], X'_j[p]) }[/math], где [math]\displaystyle{ 1 \le i \le j \le k }[/math].
Задача № 1. Множественное выравнивание последовательностей с минимальным значением оценки SP
Дано: набор из k строк, схема оценки s.
Требуется: найти множественное выравнивание A этих k строк с минимальной оценкой SP(A).
Мера «Выравнивание деревьев» (TA)
В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор [math]\displaystyle{ \chi }[/math] из k строк, положим [math]\displaystyle{ \chi' \supseteq \chi }[/math]. Эволюционное дерево [math]\displaystyle{ T{\chi'} }[/math] для набора [math]\displaystyle{ \chi }[/math] представляет собой дерево с не менее чем k узлами, причем существует взаимно-однозначное соответствие между узлами дерева и строками в [math]\displaystyle{ \chi' }[/math]. Пусть [math]\displaystyle{ X'_u \in \chi' }[/math] – строка для узла u. Оценка [math]\displaystyle{ T_{\chi'} }[/math], обозначаемая [math]\displaystyle{ TA(T_{\chi'}) }[/math], определяется как [math]\displaystyle{ \sum_{e = (u, v)} D(X'_u, X'_v) }[/math], где e – ребро в [math]\displaystyle{ T_{\chi'} }[/math], а [math]\displaystyle{ D(X'_u, X'_v) }[/math] обозначает оценку оптимального парного выравнивания для [math]\displaystyle{ X'_u }[/math] и [math]\displaystyle{ X'_v }[/math]. Аналогичным образом, множественное выравнивание [math]\displaystyle{ \chi }[/math] согласно мере TA также может быть представлено матрицей [math]\displaystyle{ | \chi'| \times \ell }[/math], где [math]\displaystyle{ | \chi' | \ge k }[/math], с оценкой, определяемой как [math]\displaystyle{ \sum_{e = (u, v)} d(X'_u, X'_v) }[/math] (e – ребро в [math]\displaystyle{ T_{\chi'} }[/math]), аналогично множественному выравниванию по мере SP, где оценка является суммированием оценок выравнивания всех пар строк. В рамках меры TA, исходя из того, что всегда можно построить матрицу [math]\displaystyle{ | \chi'| \times \ell }[/math] такую, что [math]\displaystyle{ d(X'_u, X'_v) = D(X'_u, X'_v) }[/math] для всех e = (u, v) в [math]\displaystyle{ T_{\chi'} }[/math], а нас обычно интересует нахождение множественного выравнивания с минимальным значением TA, в определении [math]\displaystyle{ TA(T_{\chi'}) }[/math] вместо [math]\displaystyle{ d(X'_u, X'_v) }[/math] используется [math]\displaystyle{ D(X'_u, X'_v) }[/math].
Задача № 2. Множественное выравнивание последовательностей с минимальным значением оценки ТА
Дано: набор из k строк, схема оценки s.
Требуется: найти эволюционное дерево T для этих k строк с минимальной оценкой TA(T).
Основные результаты
Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что [math]\displaystyle{ \frac{SP(A)}{SP(A^*)} \le \frac {2 (k - 1)}{k} = 2 - \frac{2}{k}. }[/math]
Метод центральной звезды стремится получить такое выравнивание, которое согласуется с оптимальным парным выравниванием центральной строки со всеми остальными строками. Граница выводится на основе неравенства треугольника оценочной функции. Временная сложность данного метода составляет [math]\displaystyle{ O(k^2 \ell^2) }[/math], где [math]\displaystyle{ \ell^2 }[/math] – время решения задачи парного выравнивания методом динамического программирования, а [math]\displaystyle{ k^2 }[/math] – время поиска центральной строки [math]\displaystyle{ X_c }[/math], дающей минимальное значение [math]\displaystyle{ \sum_{i \ne c} D(X_c, X_i). }[/math]
Теорема 2. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен рандомизированный алгоритм, который позволяет получить выравнивание A, такое, что [math]\displaystyle{ \frac{SP(A)}{SP(A^*)} \le 2 + \frac{1}{r - 1} }[/math] с вероятностью не менее [math]\displaystyle{ 1 - \Big( \frac{r - 1}{r} \Big)^p }[/math] для любых [math]\displaystyle{ r \gt 1 }[/math] и [math]\displaystyle{ p \ge 1. }[/math]
Вместо того чтобы вычислять [math]\displaystyle{ \binom{k}{2} }[/math] оптимальных парных выравниваний для поиска наилучшей центральной строки, рандомизированный алгоритм рассматривает только p случайно выбранных строк в качестве кандидатов на наилучшую центральную строку, поэтому для работы этого метода необходимо вычислить только (k - 1)p оптимальных парных выравниваний за время [math]\displaystyle{ O(kp \ell^2) }[/math], где [math]\displaystyle{ 1 \le p \le k }[/math].
Теорема 3. Пусть T* - оптимальное эволюционное дерево из заданных k строк с минимальной оценкой TA. Предложен аппроксимационный алгоритм, позволяющий получить эволюционное дерево T, такое, что [math]\displaystyle{ \frac{TA(T)}{TA(T^*)} \le \frac{2 (k - 1)}{k} = 2 - \frac{2}{k}. }[/math]
В ходе работы алгоритма сначала вычисляются все [math]\displaystyle{ \binom{k}{2} }[/math] оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку [math]\displaystyle{ X_i }[/math], а вес каждого ребра [math]\displaystyle{ (X_i, X_j) }[/math] равен [math]\displaystyle{ D(X_i, X_j) }[/math]. Этот шаг определяет общую временную сложность [math]\displaystyle{ O(k^2 \ell^2) }[/math]. Затем для этого графа вычисляется минимальное остовное дерево. Множественное выравнивание должно быть согласовано с оптимальными парными выравниваниями, представленными ребрами этого минимального остовного дерева.
Применение
Множественное выравнивание последовательностей является фундаментальной задачей вычислительной биологии. В частности, оно полезно для выявления тех общих структур, которые могут быть слабо представлены в последовательности и в силу этого не могут быть легко выявлены при парном выравнивании. Такие общие структуры могут нести важную информацию об их эволюционной истории, критически важных консервативных мотивах, общей трехмерной молекулярной структуре, а также биологических функциях.
В последнее время множественное выравнивание последовательностей используется также для выявления некодирующих РНК (нкРНК) [3]. При этом типе множественного выравнивания мы выравниваем не только базовые последовательности, но и вторичные структуры РНК (см. гл. 16 в [10] для краткого ознакомления со вторичной структурой РНК). Исследователи считают, что нкРНК, принадлежащие к одному семейству, должны содержать общие компоненты, обеспечивающие сходную вторичную структуру. Множественное выравнивание способно помочь найти и идентифицировать эти общие компоненты.
Открытые вопросы
Остается нерешенным ряд задач, связанных с работой Гасфилда. Для меры SP метод центральной звезды может быть расширен до метода q-звезды (q > 2) с коэффициентом аппроксимации 2 - q/k ([1, 7], раздел 7.5 работы [8]). Существует ли аппроксимационный алгоритм с лучшим коэффициентом аппроксимации или с меньшей временной сложностью, пока неизвестно. Для меры TA наилучшим результатом на сегодняшний день является коэффициент аппроксимации из теоремы 3.
Другим интересным направлением, связанным с этой задачей, является задача множественного выравнивания последовательностей с ограничениями [9], в которой требуется, чтобы множественное выравнивание содержало определенные выровненные символы относительно заданной последовательности с ограничениями. Наиболее известным результатом [2] является аппроксимационный алгоритм (также следующий методу центральной звезды), который позволяет получить выравнивание с коэффициентом аппроксимации 2 - 2/k для k строк.
Что касается сложности, то Ван и Цзян [11] первыми доказали NP-трудность задачи с мерой SP при неметрической мере расстояния над алфавитом из 4 символов. Недавно в работе [4] было доказано, что задача множественного выравнивания с мерой SP, выравниванием по методу звезды и мерой TA является NP-трудной для всех двухсимвольных или больших алфавитов при любой метрике. Разработка эффективных аппроксимационных алгоритмов с хорошими границами для любой из этих мер весьма желательна.
Экспериментальные результаты
В работе приводятся два эксперимента, показывающие, что границы ошибки в теоремах 1 и 2 для меры SP в наихудшем случае являются пессимистичными по сравнению с типичной ситуацией, возникающей на практике.
В экспериментах использовалась следующая схема оценки: s(a, b) = 0, если a = b; s(a, b) = 1, если либо a, либо b – пробел; в противном случае s(a, b) = 2. Поскольку было показано, что вычисление оптимального множественного выравнивания с минимальной оценкой SP является NP-трудной задачей, авторы оценивают эффективность своих алгоритмов, используя нижнюю границу [math]\displaystyle{ \sum_{i \lt j} D(X_i, X_j) }[/math] (напомним, что [math]\displaystyle{ D(X_i, X_j) }[/math] – это оценка оптимального парного выравнивания [math]\displaystyle{ X_i }[/math] и [math]\displaystyle{ X_j }[/math]). Было выровнено 19 сходных аминокислотных последовательностей со средней длиной 60 гомеобоксов от разных видов. Отношение оценок, полученных при выравнивании методом центральной звезды, к нижней границе составляет всего 1,018, что далеко от наихудшей границы ошибки, указанной в Теореме 1. Также было проведено выравнивание 10 не очень похожих последовательностей вблизи гомеобоксов, для которых отношение оценок выравнивания к нижней границе составило 1,162. Результаты также показывают, что выравнивание, полученное с помощью рандомизированного алгоритма, обычно не слишком далеко от нижней границы.
См. также
Литература
1. Bafna, V., Lawler, E.L., Pevzner, P.A.: Approximation algorithms for multiple sequence alignment. Theor. Comput. Sci. 182, 233-244(1997)
2. Francis, Y.L., Chin, N.L.H., Lam, T.W., Prudence, W.H.W.: Efficient constrained multiple sequence alignment with performance guarantee. J. Bioinform. Comput. Biol. 3(1), 1 -18 (2005)
3. Dalli, D., Wilm, A., Mainz, I., Stegar, G.: STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time. Bioinformatics 22(13), 1593-1599 (2006)
4. Elias, I.: Setting the intractability of multiple alignment. In: Proc. of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), 2003, pp. 352-363
5. Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol. 55(1), 141-154(1993)
6. Pevsner, J.: Bioinformatics and functional genomics. Wiley, New York (2003)
7. Pevzner, P.A.: Multiple alignment, communication cost, and graph matching. SIAM J. Appl. Math. 52,1763-1779 (1992)
8. Pevzner, P.A.: Computational molecular biology: an algorithmic approach. MIT Press, Cambridge, MA (2000)
9. Tang, C.Y., Lu,C.L., Chang, M.D.T.,Tsai,Y.T., Sun,Y.J.,Chao, K.M., Chang, J.M., Chiou, Y.H., Wu, C.M., Chang, H.T., Chou, W.I.: Constrained multiple sequence alignment tool development and its application to RNase family alignment. In: Proc. of the First IEEE Computer Society Bioinformatics Conference (CSB 2002), 2002, pp. 127-137
10. Tompa, M.: Lecture notes. Department of Computer Science & Engineering, University of Washington. http://www.cs.washington.edu/education/courses/527/00wi/. (2000)
11. Wang, L. Jiang, T.: On the complexity of multiple sequence alignment. J. Comp. Biol. 1,337-48 (1994)