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

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

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

Один из таких путей связан с идеями 1-граммного разложения. Алгоритм поиска гомологий по банку последовательностей, основанный на использовании 1-граммногс разложения, мало отличается от уже описанного в п.2 - тестируемая последовательность раскладывается по 1-граммам и затем проверяется встречаются ли те или иные 1-граммы в банке последовательностей. Однако такое применение этого метода требует известной осторожности. Дело в том, что неудачное задание ранга 1-грамм может привести либо к очень большому уровню шума, либо к пропуску существенной гомологии. И если при поиске гомологий между двумя последовательностями умеренного размера такого рода ошибка не страшна, поскольку можно очень быстро повторить расчет с другими параметрами (потери времени составят секунды), то при анализе банка последовательностей за такие ошибки приходится платить часами счета. Кроме того, выбор слишком вы-
сокого ранга 1-грамм требует большой памяти для размещения разложения. Обычно при применении методов 1- граммного разложения используют ранг 1=13 для нуклеотидных последовательностей и 1=4 для аминокислотных последовательностей.
Метод 1-граммного разложения для задачи поиска по банку последовательностей имеет существенный недостаток - он ищет только строгие гомологии без каких бы то ни было дефектов. Однако есть возможность несколько смягчить зту строгость. Для этого надо изменить определение гомологии или, иными словами, начать решать другую задачу. Теперь под гомологией будем понимать существование р совпадающих 1-грамм, расстояние между которыми не превышает к букв, где га,1,к - параметры гомологии. Например, две последовательности рис.1.15 гомологичны в смысле параметров га=3, 1=4, к=4, поскольку они имеют три пары гомологичных
четверок, разнесенных не более чем на 4 буквы. Такой подход позволяет
TCACC--TGATTCATCAAGGG Р и с. 1.15. Фрагменты, гомоло-
***** **** ***** гичные в смысле разнесенных 1-
CTACCTCAGATT----CAAGGC грамм
применять методы 1-граммного разложения для поиска гомологий с ограниченными вставками и заменами - лишь бы сохранились га гомологичных 1-грамм. На практике можно применять различные наборы параметров, при зтом будут решаться, вообще говоря, разные задачи и возможно получение разных результатов. При реализации этого алгоритма (Кондратов, Ройтберг, частное сообщение) для каждой цепочки гомологичных 1-грамм приписывается вес, который вычисляется как сумма весов 1-грамм минус штрафы за спейсеры, пропорциональные их размерам. При выборе параметров следует иметь в виду, что увеличение параметров га и к приводит к увеличению времени счета, кроме того, увеличение параметра к повышает уровень шума. Применение методов 1-граммного разложения для поиска гомологий позволяет находить достаточно короткие гомологии с относительно небольшим количеством дефектов. При поиске же протяженных гомологий с большим количеством дефектов такой подход не применим.
Вилбур и Липман (Wilbur, Lipraan, 1983) предложили следующий метод поиска гомологий по банку последовательностей. Представим себе точечную матрицу гомологий, построенную для тестируемой последовательности и банка последовательностей (рис.1.16) при параметрах фильтрации: длина окна 1, число ошибок 0. Для построения такой матрицы применим метод
1-граммного разложения. Как известно, гомологии без делеций и вставок отвечают на зтой матрице диагоналям, достаточно заполненных точками. Чтобы оценить значимость той или иной диагонали, достаточно подсчитать на ней количество точек. Если это число использовать в качестве критерия гомологии, то будут потеряны гомологии, содержащие делеции и
вставки. Поэтому в качестве значимости диагонали можно использовать суммарное количество точек на нескольких смежных диагоналях (на рисунке им отвечают числа, записанные под матрицей гомологии). Однако не все точки на смежных диагоналях соответствуют выравниванию. Чтобы учесть это обстоятельство, при суммировании учитываются только те точки на матрице гомологии, которые могут быть объединены в выравнивание. В результате получаем набор чисел, показанный над матрицей гомологии. Трудоемкость этого алгоритма можно оценить величиной p^N/N^, где р -вероятность совпадения букв; N, - длина тестируемой последовательности; N2 - размер банка последовательностей.
Рис. 1.16. Иллюстрация метода Вилбура - Липмана
По верхней границе отмечены веса диагоналей
Алгоритмы Кондрашова - Ройтберга и Вилбура - Липмана идейно близки между собой, но решают, вообще говоря, разные задачи. Первый ориентирован на поиск коротких локальных гомологий (длиной не менее р’(1+к-1)), а второй - на поиск протяженных гомологичных участков. Так, например, появление короткой строгой гомологии (например, совпадения 15 нуклеотидов) будет обнаружено методом Кондрашова - Ройтберга, но будет пропущено при применении алгоритма Вилбура - Липмана, в то время как для группы из 20 совпадающих пентануклеотидов будет противоположная ситуация.
Статистический метод поиска гомологий. При решении многих математических задач используют необходимые условия. Например, при поиске максимума или минимума функции ищут точки, где производная этой функции обращается в ноль - эти точки имеют шанс быть максимальными или минимальными точками функции. Использование необходимых условий не приводит прямо к решению задачи, но значительно суживает круг поиска. Было бы хорошо, если бы удалось сформулировать такие необходимые условия гомологии биологических текстов, которые легко проверяются и при этом служат хорошим фильтром, отбрасывающим заведомо негомологичные пары. Эти условия должны позволять взглянуть на последовательность "в целом". Примером такого рода необходимых условий является близость буквенного (нуклеотидного или аминокислотного) состава последовательностей. Буквенный состав последовательности является характеристикой последовательности как целого, легко вычисляется, и если буквенные составы сильно различаются, то последовательности заведомо негомологичны. Но, к сожалению, такое простое условие является плохим фильтром -
Предыдущая << 1 .. 9 10 11 12 13 14 < 15 > 16 17 18 19 20 21 .. 119 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed