Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
на матрице гомологий, для которых функция сходства превышает заданную величину к удовлетворяют следующим требованиям: во-первых, найденные
пути должны быть оптимальными при фиксированных начале и конце; во-вторых, эти пути должны быть в некотором смысле максимальными - любое наращивание локально-оптимального пути может привести лишь к уменьшению функции сходства; в-третьих, эти пути должны быть непрерывными -
функция сходства фрагмента пути от начала до любой его точки должна быть положительной. Это требование означает запрет на чисто формальное объединение ничем не связанных путей. Кроме того, разумно наложить запрет на пересечение путей: если два пути пересекаются или имеют об-
щие точки, то из них выбирается тот, для которого функция сходства наибольшая. Эти требования, кроме требования максимальности, не встречались в локальной задаче поиска общего слова, поскольку в задаче об общем слове пути могут идти только параллельно диагонали.
Задачи о локальном выравнивании возникают при поиске разного рода повторов, возможных сайтов рекомбинации, анализе и поиске разного рода функциональных сайтов и т.п. Отметим, что если существует хорошее (с функцией сходства больше порогового значения) глобальное выравнивание, то оно (точнее ее существенная часть) будет найдено при решении локальной задачи выравнивания. Таким образом, задача поиска локальной гомологии в некотором смысле является самой общей задачей выравнивания.
Для поиска локального выравнивания можно применять тот же метод динамического программирования, что и для задачи поиска оптимального пути. Пусть в результате применения этого метода мы построили матрицу F и карту обратных переходов (рис.1.13,а,б). Возьмем теперь любой путь на карте переходов и построим вдоль него график изменения функции
сходства (рис.1.14). Он будет состоять из целого ряда подъемов и спа-
дов - подъемы соответствуют совпадениям букв в сравниваемых последовательностях, спады - дефектам гомологии - заменам и делециям. Выделим участок пути до наибольшего значения функции F. Он отвечает всем требованиям локальной гомологии, если только наибольшее значение функции
сходства превосходит пороговую величину. Действительно, этот участок
оптимален по самому построению, он максимален, поскольку любое его наращивание приводит лишь к уменьшению функции сходства и, наконец, он непрерывен, так как функция сходства на нем всюду положительна. Есть ли на этом пути другие участки, отвечающие требованиям локальной гомологии? Есть. Для того чтобы в этом убедиться, отбросим только что найденный участок и построим функцию сходства для оставшейся части пути, помня, что она не может быть отрицательной (на рис.1.14 она обозначена пунктирной линией ). После такого преобразования функция сходства может неоднократно обратиться в 0. К каждому фрагменту с ненулевой функцией сходства можно применить предыдущие рассуждения, т.е. найти наибольшее значение функции сходства, выделить участок от начала фрагмента до максимума функции сходства в качестве локальной гомологии, пересчитать функцию сходства, начиная от найденного максимума. Описанную процедуру нужно повторять до тех пор, пока максимальное значение функции сходства на оставшемся участке превосходит пороговое значение. Обработав таким образом все пути, построенные методом динамического программирования, можно найти все локальные гомологии. Описанный метод
является модификацией, предложенной И.И.Ветровым (частное сообщение) алгоритма Гоада и Канехисы (Goad, Kanehisa, 1982).
Описанные методы динамического программирования достаточно эффективны, требуют не больше порядка N,*N2 операций для решения задачи выравнивания, однако им присущ серьезный недостаток - они требуют для своей работы большой емкости памяти для запоминания карты обратных переходов (помнить всю матрицу F не обязательно, поскольку на каждом шаге используется только предыдущая строка этой матрицы). Так, для выравнивания двух последовательностей по 103 букв требуется память порядка одного мегабайта. Оперативная память такого размера редко встречается в персональных компьютерах, и для реализации методов динамического программирования приходится использовать внешнюю память на магнитных дисках, что приводит к заметному увеличению времени работы программы.
Т6АА6ТЛТСААбСГСЛСбвтСбетедсе*Л ТСААСТАТСААСеТСЛССвТСССТСАССАА
2 2 3 14 2 9 1 1
I I
1 5 X
1 t t
I « 2
ь >
iet х г ъ
13 1 i 4 4 г
г \ з э 1
1 see
1 14 2
9 1
г г г i
14 4 2 1
9 & э г г г
1 г 6 б э 4 ?. 1 1
1 4 7 П 1 1 9 е
1 112 6 3
1 9 14 2
