Биоалгоритмика - Журнал "Компьютерра"

24 мая 2012 года

Биоалгоритмика

Автор: Михаил Ройтберг
Опубликовано в журнале "Компьютерра" №36 от 24 сентября 2001 года

Страница 4 из 4. Вернуться на первую страницу.

Алгоритм оптимального выравнивания (набросок)

Пусть нам нужно найти оптимальное выравнивание последовательностей U=Xa и W=Yb (здесь a - последняя буква U, b - последняя буква W, последовательности X и Y - получаются соответственно из U и W отбрасыванием последней буквы. Для оптимального выравнивания возможны ровно три альтернативы:

последние буквы слов U и W сопоставлены друг другу;
последняя буква слова U удалена, последняя буква слова W - нет;
последняя буква слова W удалена, последняя буква слова U - нет.

В первом случае вес оптимального выравнивания равен

S₁ = S(X, Y)+m(a, b).

Здесь S(X, Y) - вес оптимального выравнивания последовательностей X и Y (оно уже построено ранее, т. к. пара (X, Y) рассмотрена до текущей пары (U, W)), m(a, b) - вес сопоставления символов a и b.

Во втором и третьем случае аналогично получаем формулы:

S₂ = S(X, Yb)+g,

S₃ = S(Xa, Y)+g.

Здесь g - штраф за удаление символа, S(X, Yb) и S(Xa, Y) - веса оптимальных выравниваний для пар последовательностей (X и Yb = W) и (Xa=U и Y) соответственно. Оптимальные выравнивания для этих пар последовательностей тоже построены ранее. Таким образом, чтобы найти вес S(U, W) оптимального выравнивания последовательностей U и W и само это выравнивание, достаточно найти наибольшее из чисел S₁ , S₂ , S₃. Очевидно, каждое из этих чисел можно вычислить за конечное (не зависящее от длин исходных последовательностей) время. Поэтому общее время построения оптимального выравнивания двух последовательностей пропорционально количеству промежуточных задач, т. е. произведению длин этих последовательностей.

<<Врезка 2

версия для печати другие статьи автора оставить комментарий (0)
ТАКЖЕ В РАЗДЕЛЕ 24 февраля 2009 года Не отрываясь 24 февраля 2009 года Жилец вершин 10 февраля 2009 года Гаджеты, которых нет 10 февраля 2009 года Схватка 10 февраля 2009 года Мобильный телефон 2015 года 10 февраля 2009 года Список задач		MARKETGID Загрузка...