Научная литература
booksshare.net -> Добавить материал -> Биология -> Александров А.А. -> "Компьютерный анализ генетических текстов" -> 11

Компьютерный анализ генетических текстов - Александров А.А.

Александров А.А., Александров Н.Н., Бородовский М.Ю. Компьютерный анализ генетических текстов — М.:Наука , 1990. — 267 c.
ISBN 5-02-004691-4
Скачать (прямая ссылка): komputerniyanalizgeneticheskihtextov1990.djv
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 119 >> Следующая

Из сказанного видно, что выбор конкретной функции сходства подчинен достаточной степени субъективизма. Но, к счастью, сильно гомологичные последовательности выравниваются примерно одинаково при различных вариантах функции сходства, чего нельзя сказать о последовательностях со слабой гомологией. Поэтому утверждения о гомологии 90% говорят о действительно высокой гомологии, в то время как "гомология 40%" ничего не говорит без четкого указания параметров, которые использовались при выравнивании. Дальнейшее описание алгоритмов будем вести для простейшего вида функции сходства (1.1).
Иногда в качестве критерия качества выравнивания используют рассто яние (Sellers, 1974). В случае последовательностей под расстоянием понимают обычно минимальное число элементарных преобразований, превращающих одну последовательность в другую. Такими элементарными преобразованиями могут быть деления, вставка, замена или в более сложных случаях транспозиция элементов. Однако для решения задач выравнивания (а особенно для решения локальных задач выравнивания) более удобно использовать сходство, хотя принципиальной разницы между этими критериями нет.
Метод динамического программирования. Чтобы описать алгоритм построения оптимального выравнивания, попробуем представить себе геометрический образ выравнивания. Для этого вспомним точечную матрицу гомологии (рис.1.10). Любую линию на зтой матрице, идущую либо вверх, либо вправо, либо вправо - вверх параллельно диагонали условимся называть путем по точечной матрице гомологий. Нетрудно догадаться, что любой путь по матрице из левого нижнего в правый верхний угол отвечает некоторому выравниванию, причем движение вверх или вправо отвечает делеции в одной из последовательностей, а при движении параллельно диагонали прохождение через пустые клетки соответствуют заменам, прохождение через точки - совпадениям. Например, пути рис.1.10,а соответствует выравнивание 1.10,6. Задача оптимального выравнивания, таким образом, сводится к поиску наилучшего пути по матрице гомологии. При поиске этого пути будем одновременно строить матрицу наилучших значений функции сходства: F(i,j) - есть значение функции сходства, отвечающее оп-
тимальному пути из левого нижнего угла матрицы гомологий в точку (i,j). Если известны значения функции сходства в точках (i-l,j), (i,j-1) и (i-1,j-1) и оптимальные пути в эти точки, то можно найти значение функции сходства для наилучшего пути, ведущего из точки (1,1) в точку (i,j), и определить этот путь. Оптимальное значение функции определяется по формуле
F(i,j)=max{ F(i-l,j)-vd, (1.3)
F(i,j-l)-vd,
F(i-1,j-1)+v.j},
где Уи=Ут, если i-буква первой последовательности совпадает с j- буквой второй последовательности, и vu=-vc в противном случае. Наилучший путь к точке (i,j) определяется членом в формуле (1.3), на котором достигается максимум,- это наилучший путь к соответствующей точке ((i-1,j), (i,j-l) или (i-1,j-1)) плюс переход: в первом случае по горизонтали, во втором по вертикали, а в третьем по диагонали (рис. 1.11). Например, если максимум достигается на втором члене формулы (1.3), то оптимальный путь в точку (i,j) будет состоять из оптимального пути в точку (i,j-l) (а он нам известен!) плюс переход впра
во. На практике обычно фиксируют только эти переходы, а весь оптимальный путь восстанавливают по ним в конце работы алгоритма. Совокупность найденных переходов будем в дальнейшем называть картой обратных переходов. Для окончательного построения алгоритма осталось только определить начальное значение функции сходства в точке (1,1) и разобраться с начальной (нижней) строкой и начальным (левым) столбцом матрицы F (рис.1.12,а). Для этого добавляют слева столбец с номером 0, а снизу строку с номером 0. Значения на этих линиях определяются ценой делеции
РИс. 1.11. Переходы при построении оптимального выравнивания
рис. 1.12. Пример матрицы сходства (а), карты путей (б) и оптимального выравнивания (в), построенных методом динамического программирования (vm=l, v„=l. V-l)
крайних букв в последовательностях. На рис.1.12,а изображен пример матрицы F, а на рис.1.12,б - соответствующая карта путей при значениях параметров vm=vc=vd=l, выделенный путь отвечает оптимальному выравниванию. На рис.1.12,в приведено выравнивание, соответствующее оптимальному цути. Оптимальное значение функции сходства для этого выравнивания F(N,,NI)=0.
Индуктивные методы поиска оптимальных путей, подобные только что описанному, называются методами динамического программирования. Алгоритм динамического программирования для решения задач выравнивания впервые был предложен Нидльманом и Вуншем (Needleman, Wunsch, 1970) и его можно применять для решения широкого круга задач.
Алгоритм Нидльмана - Вунша построен таким образом, что он ищет оптимальный путь из левого нижнего угла в правый верхний. При этом выставляются штрафы за краевые вставки, например в выравнивании рис. 1.12,в за первые три и последние три нуклеотида функция сходства
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 119 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed