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

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