Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок
Ключевые слова и синонимы
Выравнивание нескольких строк; глобальная задача выравнивания нескольких строк
Постановка задачи
Множественное выравнивание последовательностей является важной задачей вычислительной биологии. Она применяется в таких областях, как поиск высококонсервативных субрегионов в заданном наборе биологических последовательностей и вывод истории эволюции набора таксонов на основе связанных с ними биологических последовательностей (см., например, [6]). Был предложен ряд мер для оценки качества множественного выравнивания, однако до выхода работы Гасфилда ни для одной из этих мер не было известно эффективных методов вычисления оптимального выравнивания. В работе Гасфилда [ ] приведены два вычислительно эффективных алгоритма аппроксимации множественного выравнивания для двух мер с коэффициентом аппроксимации менее 2. Для одной из мер также получен рандомизированный алгоритм, который работает значительно быстрее и с высокой вероятностью выдает множественное выравнивание с малыми границами ошибки. В данной работе впервые были представлены аппроксимационные алгоритмы (с гарантированными границами ошибок) для этой задачи.
Нотация и определения
Пусть X и Y – две строки алфавита S. Парное выравнивание A строк X и Y отображает X, Y на строки X0, Y0, которые могут содержать пробелы обозначаемые '_', таким образом, что выполняется следующее: (1) jX0j = jY0j = I; (2) удаление пробелов из X0 и Y0 превращает их в X и Y, соответственно. Оценка выравнивания определяется как d(X0 ; Y0) = £?=i s(X0(i); Y0(i)), где X0(i) (и Y0(i)) обозначает i-й символ в X0 (и Y0), а s(a; b) при a; b 2 S [ '_0 – схема оценки на основе расстояния, удовлетворяющая следующим предположениям. 1. s('_0;‘_0) = 0; 2. неравенство треугольника: для любых трех символов, x, y, z выполняется соотношение s(x;z) < s(x;y) + s(y;z)). Обозначим за / = X1 ; X 2... ; Xk множество k > 2 строк алфавита £. Множественное выравнивание A этих k строк отображает Xi, Xi,... , Xk на X[, X'2,... Xk, которые могут содержать пробелы таким образом, что выполняется следующее: (1) \X[ \ = jX2 0 j = ■ ■ = jX0k j = I; (2) удаление пробелов из элемента Xi' превращает его в Xi для всех 1 < i < k. Множественное выравнивание A может быть представлено в виде матрицы k x I.
Мера «Сумма пар» (SP)
Оценка множественного выравнивания A, обозначаемая SP(A), определяется как сумма оценок парных выравниваний, индуцированных A, т. е. Pi<j d{X\, Xp =.
Задача № 1. Множественное выравнивание последовательностей с минимальным значением оценки SP
Дано: набор из k строк, схема оценки s.
Требуется: найти множественное выравнивание A этих k строк с минимальной оценкой SP(A).
Мера «Выравнивание деревьев» (TA)
В данном случае множественное выравнивание выводится из эволюционного дерева. Пусть задан набор / из k строк, /' 2 /-. Эволюционное дерево Tx/ для набора / представляет собой дерево с не менее чем k узлами, в котором существует соответствие один-к-одному между узлами дерева и строками в /'. Пусть Xu 0 /' – строка для узла u. Оценка Tx/, обозначаемая TA(TX/), определяется как ~Y^,e= 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).
Задача № 2. Множественное выравнивание последовательностей с минимальным значением оценки ТА
Дано: набор из k строк, схема оценки s.
Требуется: найти эволюционное дерево Tx для этих k строк с минимальной оценкой TA(T).
Основные результаты
Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что:
Метод центральной звезды стремится получить такое выравнивание, которое согласуется с оптимальным парным выравниванием центральной строки со всеми остальными строками. Граница выводится на основе неравенства треугольника оценочной функции. Временная сложность данного метода составляет O(k2t2), где I2 – время решения задачи парного выравнивания методом динамического программирования, а k2 – время поиска центральной строки Xc, дающей минимальное значение
Теорема 2. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен рандомизированный алгоритм, который позволяет получить выравнивание A, такое, что щ -2+ 7~[ с вероятностью не менее 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-трудной для всех двухсимвольных или больших алфавитов при любой метрике. Разработка эффективных аппроксимационных алгоритмов с хорошими границами для любой из этих мер весьма желательна.
Экспериментальные результаты
В работе приводятся два эксперимента, показывающие, что границы ошибки в теоремах 1 и 2 для меры SP в наихудшем случае являются пессимистичными по сравнению с типичной ситуацией, возникающей на практике.
