Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
Как стало ясно из первой главы, задачу выравнивания двух последе вательностей можно считать в основном решенной. Этого нельзя пок-i сказать о задаче выравнивания большего числа последовательностей. Предложено немало алгоритмов для решения проблемы множественного выравнивания, но ни один из них нельзя признать достаточно эффективным. Существуют в основном три подхода: первый представляет собой
обобщение алгоритма Нидльмана - Вунша (Needleman, Wunsch, 1970) на случай трех и более последовательностей; основная идея другого метода заключается в поиске общих участков в выравниваемых последовательностях с их дальнейшим упорядочиванием; в третьем случае множес твенное выравнивание сводится к построению консенсуса, с которь.ч.' производится попарное выравнивание всех последовательностей. Все этг подходы практически используются в разных случаях. Оптимальным можно считать выравнивание, полученное при помощи алгоритма Нидльмана Вунша, но он требует колоссального объема памяти и очень много машинного времени. Алгоритмы второго типа не дают гарантии оптимальности выравнивания, но достаточно быстры и являются сейчас самыму популярными при работе с большим числом последовательностей. И, наконец, методы построения консенсусов представляются наиболее общи?/ решением проблемы. Именно в этих алгоритмах отчетливо видна связ; между одновременным выравниванием нескольких последовательностей распознаванием функциональных сайтов.
Динамическое программирование. Алгоритм Нидльмана - Вунша вырав нивания двух последовательностей "от границы до границы" был применен Мурата (Murata et al., 1985) для выравнивания трех белковых последовательностей. Такое обобщение совсем не изменило сути алгоритма. Практическая реализация этого алгоритма требует большого объема па-
пяти, пропорционального N3, где N - среднее геометрическое m,n и р. Время счета тоже пропорционально N3. Сравнение трех белков с N=100 требует 1МБ памяти и 80 с счета на компьютере VAX-11/780. Из-за огромных требований к памяти и быстродействию компьютеров практически невозможно использовать этот алгоритм для четырех и большего числа последовательностей. Поэтому были предложены эвристические алгоритмы, значительно экономящие машинное время и память, но не гарантирующие построение оптимального в матричном смысле выравнивания.
Джонсон и Дулиттл (Johnson, Doolittle, 1986) предложили сканировать последовательности окном ширины w и динамически выравнивать между собой лишь небольшие фрагменты в окнах. Объем требуемой памяти теперь не зависит от длины последовательностей и определяется параметром w. Время счета линейно зависит от длины и экспоненциально от числа последовательностей. Алгоритм был проверен на трех, четырех, и пяти белковых последовательностях длиной - 200 аминокислот и занял соответственно 55 с, 18 и 263 мин счета на компьютере VAX-11/780. Когда последовательности очень похожи, преимущества этого метода не вызывают сомнений. Однако, если они различаются довольно сильно и для выравнивания необходимо делать протяженные вставки, трудно ожидать удовлетворительных результатов.
Быстрое выравнивание. В одной из своих работ, посвященных проблеме множественного выравнивания, признанный специалист в области компьютерной генетики М.С.Уотерман (Waterman, 1986) отметил, что для практического использования при выравнивании более трех последовательностей годится только лишь метод Собела - Мартинеца (Sobel, Martinez, 1986). В зтой же статье он приводит еще один практический алгоритм. Но сначала познакомимся с идеями Собела и Мартинеца.
Алгоритм основан на предварительном поиске общих сегментов с последующим их упорядочиванием так, чтобы максимизировать некоторую функцию или вес выравнивания. Под сегментом будем понимать подпоследовательность из нуклеотидов. Назовем общим сегментом или регионом сегмент, встречающийся во всех выравниваемых последовательностях. Пусть, например, сегмент ACCTG встретился в позиции 12 первой последовательности и в позициях 45 и 100 второй последовательности. В этом случае мы имеем дело с двумя общими сегментами, порожденными ACCTG. Один соответствует паре позиций (12,45), а другой - (12,100). Если к тому же ACCTG присутствует в позициях 20 и 50 третьей последовательности, мы получим уже четыре общих сегмента, соответствующих тройкам позиций (12,45,20), (12,45,50), (12,100,20) и (12,100,50).
Очевидно, что число общих сегментов растет с увеличением суммарной длины последовательностей. Соответственно возрастает и вычислительная сложность алгоритма. Этот комбинаторный взрыв можно предотвратить, если увеличить минимальную длину общего сегмента, т.е. ис-
кать только крупные регионы. Поиск регионов осуществляется описанным в первой главе методом (Martinez, 1983).
Далее, будем считать, что регион X предшествует региону Y, если все позиции X меньше соответствующих позиций Y по крайней мере ка длину региона X. Выравнивание мы теперь заменяем набором упорядоченных регионов и нашей целью становится отыскание оптимального набора регионов Х,,Х2,..., такого, что Х,<Х2<... Критерием оптимальности (весом выравнивания) может служить, например, сумма длин регионов, определяющих выравнивание: чем она больше, тем лучше данное
