Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
штрафуется на 6*vd, хотя очевидно, что имеет место просто сдвиг одной последовательности относительно другой. Поэтому метод Нидльмана - Вун-ша применим только для тех случаев, когда совпадают "начала отсчетов" сравниваемых последовательностей.
Как нетрудно убедиться, трудоемкость этого алгоритма равна N,*N2, однако, если наложить ограничение на максимальное число ошибок к, то можно сократить число операций, необходимых для поиска оптимального пути до величины порядка N'k (Landau et al.,1986). Действительно, в этом случае нет необходимости вычислять функцию сходства во всех точках матрицы, а достаточно их вычислить лишь в окрестности диагонали шириной 2'к.
Можно модифицировать задачу выравнивания таким образом, чтобы не штрафовать за сдвиг последовательностей друг относительно друга. На матрице гомологий эта задача будет формулироваться так. Среди всех путей, начинающихся и кончающихся на границе матрицы гомологий, найти наилучший. Алгоритм, решающий такую задачу, очень похож на метод Нидльмана - Вунша. Отличие заключается в том, что при построении матрицы F под оптимальным значением функции сходства понимается функция сходства для наилучшего пути, ведущего из точки (i,j) на нижнюю или левую границу матрицы гомологии. Для того чтобы числа F(i,j) имели соответствующий смысл, достаточно вместо введения нулевых строки и столбца определить нижнюю строку и левый столбец: F(l,j) и F(1,1) приравниваются vm или vc в зависимости от совпадения или несовпадения соответствующих букв в выравниваемых словах. Чтобы теперь найти оптимальный путь, необходимо после построения матрицы F найти наибольшее значение функции сходства на правой и верхней границе матрицы выравнивания и восстановить оптимальный путь из найденной точки.
Первая постановка задачи выравнивания "из угла в угол" характерна для анализа сходства заведомо близких текстов, например гомологичных белков или сигналов, для которых начала и концы функционально значимы. Вторая постановка задачи "от границы до границы" встречается при сек-венировании для стыковки прочитанных фрагментов, а также при выравнивании последовательностей, когда функционально-значимые точки на них неизвестны, но предполагается отсутствие несовпадающих участков на краях. Есть еще одна постановка задачи глобального выравнивания - среди всех путей найти наилучший. Здесь не ставится никаких ограничений на положения концов путей. Такая постановка задачи типична при исследовании функциональных сигналов, сайтов рекомбинации, подборе зондов и пр.
Задачу о цоиске оптимального пути без ограничений на положение его концов также можно решать методом динамического программирования. Для этого прежде всего необходимо определить смысл чисел F(i,j). В этом случае под F(i,j) будем понимать значение функции сходства для наилучшего из путей, приводящих в точку (i,j) (он может начинаться, где
угодно левее и ниже этой точки). Если мы разобьем какой-либо путь на два участка, то цена целого пути будет равна сумме цен его частей. Поэтому понятно, что к любому пути невыгодно добавлять участки с отрицательной ценой. Отсюда следует, что на всем оптимальном пути величина F(i,j) должна быть положительной и может обращаться в 0 только вначале, поскольку в противном случае оптимальный путь будет иметь участки с отрицательной или нулевой ценой, которые выгодно отбросить. Все эти рассуждения допускают наличие на оптимальном пути внутреннего участка с отрицательной функцией сходства, например блок делеций в одной из последовательностей, который соединяет два хорошо совпадающих участка, поскольку отбрасывать можно только начало или конец пути, но не середину. Таким образом, можно модифицировать формулу (1.3) для вычисления F(i,j):
F(i,j)=max{ F(i-1,j)-vd, (1.4)
F(i,j-l)-vd,
F( i-1, j-D+Vj Jt
0 }.
Так же как и для предыдущих задач, будем параллельно с матрицей F строить карту обратных переходов. Точка (i*,j*), отвечающая наибольшему значению F*=max{F( i, j)}, определит нам конец от лмального пути, и начиная с этой точки можно пройти по карте обратных переходов до того места, где F обратится в 0 - это соответствует началу оптимального пути.
Все описанные выше варианты метода динамического программирования применимы для функции сходства вида (1.1). При использовании более общего вида функции сходства (1.2) применяется вариант Ватермана и Смита (Waterman et al., 1976) метода динамического программирования. Его трудоемкость составляет величину порядка min(N1-N22,N12*N2), что является платой за более общий вид функции сходства.
Описанные алгоритмы позволяют находить единственный оптимальный путь. Однако иногда бывает интересно посмотреть альтернативные варианты с той же ценой или с ценой, чуть меньшей. Эту задачу также позволяет решать метод динамического программирования (Waterman, 1983).
Локальное выравнивание. Описанные алгоритмы решают глобальную задачу выравнивания, т.е. ищут наилучший в том или ином смысле путь. Возможна также локальная постановка задачи выравнивания: найти все пути
