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

Выравнивание нескольких строк; глобальная задача выравнивания нескольких строк

Множественное выравнивание последовательностей является важной задачей вычислительной биологии. Она применяется в таких областях, как поиск высококонсервативных субрегионов в заданном наборе биологических последовательностей и вывод истории эволюции набора таксонов на основе связанных с ними биологических последовательностей (см., например, [6]). Был предложен ряд мер для оценки качества множественного выравнивания, однако до выхода работы Гасфилда ни для одной из этих мер не было известно эффективных методов вычисления оптимального выравнивания. В работе Гасфилда [5] приведены два вычислительно эффективных алгоритма аппроксимации множественного выравнивания для двух мер с коэффициентом аппроксимации менее 2. Для одной из мер также получен рандомизированный алгоритм, который работает значительно быстрее и с высокой вероятностью выдает множественное выравнивание с малыми границами ошибки. В данной работе впервые были представлены аппроксимационные алгоритмы (с гарантированными границами ошибок) для этой задачи.

Пусть 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>'_' – схема оценки на основе расстояния, удовлетворяющая следующим предположениям.

В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор <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>.

'''Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le \frac2 {k - 1}{k} = 2 - \frac{2}{k}.</math>'''

'''Теорема 2. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен рандомизированный алгоритм, который позволяет получить выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le 2 + \frac{1}{r - 1}</math> с вероятностью не менее 1 - (Ly-)t для любых r > 1 и p > 1.'''

Вместо того чтобы вычислять (2) оптимальные парные выравнивания для поиска наилучшей центральной строки, рандомизированный алгоритм рассматривает только p случайно выбранных строк в качестве кандидатов на наилучшую центральную строку, поэтому для работы этого метода необходимо вычислить только (k - 1)p оптимальных парных выравниваний за время O(kpl2), где 1 < p < k.

Теорема 3. Пусть T* - оптимальное эволюционное дерево из заданных k строк с минимальной оценкой TA. Предложен алгоритм аппроксимации, позволяющий получить эволюционное дерево T

В ходе работы алгоритма сначала вычисляются все Q) оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку Xi, а вес каждого ребра (Xi ; Xj) равен D(Xi ; Xj). Этот шаг определяет общую временную сложность O(k2t2). Затем для этого графа вычисляется минимальное остовное дерево. Множественное выравнивание должно быть согласовано с оптимальными парными выравниваниями, представленными ребрами этого минимального остовного дерева.

В последнее время множественное выравнивание последовательностей используется также для выявления некодирующих РНК (нкРНК) [3]. При этом типе множественного выравнивания мы выравниваем не только базовые последовательности, но и вторичные структуры РНК (см. гл. 16 в [ ] для краткого ознакомления со вторичной структурой РНК). Исследователи считают, что нкРНК, принадлежащие к одному семейству, должны содержать общие компоненты, обеспечивающие сходную вторичную структуру. Множественное выравнивание способно помочь найти и идентифицировать эти общие компоненты.

Остается нерешенным ряд задач, связанных с работой Гасфилда. Для меры SP метод центральной звезды может быть расширен до метода q-звезды (q > 2) с коэффициентом аппроксимации 2 - q/k ([1,7], раздел 7.5 работы [8]). Существует ли алгоритм аппроксимации с лучшим коэффициентом аппроксимации или с меньшей временной сложностью, пока неизвестно. Для меры TA наилучшим результатом на сегодняшний день является отношение аппроксимации в Теореме 3.

Другим интересным направлением, связанным с этой задачей, является задача множественного выравнивания последовательностей с ограничениями [9], в которой требуется, чтобы множественное выравнивание содержало определенные выровненные символы относительно заданной последовательности с ограничениями. Наиболее известным результатом [ ] является аппроксимационный алгоритм (также следующий методу центральной звезды), который позволяет получить выравнивание с коэффициентом аппроксимации 2 - 2/k для k строк.

Что касается сложности, то Ван и Цзян [11] первыми доказали NP-трудность задачи с мерой SP при неметрической мере расстояния над алфавитом из 4 символов. Недавно в работе [4] было доказано, что задача множественного выравнивания с мерой SP, выравниванием по методу звезды и мерой TA является NP-трудной для всех двухсимвольных или больших алфавитов при любой метрике. Разработка эффективных аппроксимационных алгоритмов с хорошими границами для любой из этих мер весьма желательна.

В экспериментах использовалась следующая схема оценки: s(a; b) = 0, если a = b;s(a; b) = 1, если либо a, либо b – пробел; в противном случае s(a; b) = 2. Поскольку было показано, что вычисление оптимального множественного выравнивания с минимальной оценкой SP является NP-трудной задачей, авторы оценивают эффективность своих алгоритмов, используя нижнюю границу P i < j D(Xi ; Xj) (напомним, что D(Xi;Xj) – это оценка оптимального парного выравнивания Xi и Xj). Было выровнено 19 сходных аминокислотных последовательностей со средней длиной 60 гомеобоксов от разных видов. Отношение оценок, полученных при выравнивании методом центральной звезды, к нижней границе составляет всего 1,018, что далеко от наихудшей границы ошибки, указанной в Теореме 1. Также было проведено выравнивание 10 не очень похожих последовательностей вблизи гомеобоксов, для которых отношение оценок выравнивания к нижней границе составило 1,162. Результаты также показывают, что выравнивание, полученное с помощью рандомизированного алгоритма, обычно не слишком далеко от нижней границы.