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

В последнее время множественное выравнивание последовательностей используется также для выявления некодирующих РНК (нкРНК) [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. Результаты также показывают, что выравнивание, полученное с помощью рандомизированного алгоритма, обычно не слишком далеко от нижней границы.