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

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

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

При помощи позиционного дерева можно анализировать повторы - любой путь от корня, не доходящий до висячей вершины - отвечает повтору. Чтобы найти общие слова двух последовательностей, их объединяют в одну. Далее для объединенной последовательности строится позиционное дерево, затем на нем ищутся пути, соответствующие двум последовательностям - они отвечают гомологиям.
Метод Мартинеца более трудоемок и требует большей памяти, чем простейший метод 1-граммного разложения, однако при его помощи получать серьезные результаты о частоте встречаемости различных поделов, находить очень короткие уникальные подпоследовательности и т.п.. Аналогичные идеи разложения последовательности на уникальные подслова, но с использованием методов быстрой сортировки, высказывались также в работе Корна и др.(Korn et al., 1977).
Основные понятия. Задача выравнивания является, пожалуй, наиболее общей задачей поиска гемологии, поскольку при выравнивании мы имееь возможность учесть довольно общие виды различий текстов - замень. вставки., делении. Единственное, чего нельзя учесть при решении задач с выравнивании, так это блочных перестанонок, хотя при локальном подход-можно обнаружить и их. Чтобы конкретизировать предмет дальнейшего обсуждения, введем несколько основных понятий. Выравниванием двух текстов будем называть расстановку вставок на последовательностях. Hl рис.1.9,а приведен пример выравнивания. Очевидно, что это вырэвнивани;.-
сделано не наилучпим образом, поскольку любой здравомыслящий исследователь в начале нижнего текста сделал бы на одну вставку меньше, посл:-AAG в верхнем тексте не делал бы вставки и т.д., т.е. сделал бы выравнивание, как на рис.1.9,6. Почему же выравнивание рис.1.9,б лучше, че*. выравнивание рис.1.9,а? Во-первых, потому, что в нем больше совпадающих букв, во-вторых, в нем меньше вставок (или делеций, так как вставка в одну последовательность эквивалентна делеции в другой последовательности), в-третьих, в нем меньше замен. Чтобы при определении оптимального выравнивания учесть все три требования (побольше совпадений поменьше делений и замен), вводят так называемую функцию сходства F:
где km, кь, кс - количество совпадений, делений и замен в выравнивании; vm, vd, vc - некоторые весоЕые коэффициенты. Выравнивание считается оптимальным, если функция сходства для неге не меньше, чем длг любого другого выравнивания. Часто оптимальных выравниваний бывав" несколько, например выравнивание рис.1.9,в ничем не хуже выравниваню-рис. 1.9, б.
Т FGAACfATCAAGGTCAGGGTATGAA
б
а
ТТСААС ТА1С--ААОС- TCAQGi!АТСАА
1ТСААСГАТ--СA-AGCTCA6G6T ATGAA---
----ACTATCGCA7AGC-CA-GC----GAA1AG
— ACT — АТСД-АССТА------TG--AAT*C
а
rTGAA-GTATCAAGGTCAGGGTATGA.
* ¦* ** * ******
АГ.т ATCGCATAG-- GC - AGGGT А-«.
Рис. 1.9. Примеры выравниваний (а,б ,р)
Р и с. 1.10. Путь на точечно; матрице гомологии (а^ и сос^ ве-гствующее выравнивание (б
F=k *v -k *v -k *v
m m d d с с
(1.1
Для выбора коэффициентов vm, va, vc используют различные соображения. В частности, известно, что мутационный процесс чаше приводит к транзициям (заменам А-G, Т-С), чем к заменам другого типа, поэтому при исследовании проблем эволюции заменам типа транзиции придают меньший вес. С другой стороны, при формировании дуплексов GC-пары дают больший выигрыш в энергии, поэтому при анализе вероятностей образования дуплексов совпадениям G-G и С-С придают больший вес. При выравнивании аминокислотных последовательностей заменам придают вес в соответствии с близостью их свойств или частотой аминокислотных замен в мутационном процессе. Для этого можно использовать табл. 1.1 и 1.2. Сложнее дело обстоит с "ценой делеции" va. Для того чтобы оценить вероятность деле-ции, необходимо предварительно эти делеции обнаружить, т.е. провести выравнивание, а для этого, в свою очередь, надо задаться коэффициентом vd. Обычно полагают vJ=(2-5),vm. Если vc/v„>2, т? в оптимально?.* выравнивании никогда не будет замен, поскольку в этом случае выгоднее делегировать несовпадающие буквы кз обеих последовательностей и получить штраф 2vd, чем получить штраф vc за несовпадение.
Можно представить себе и использовать более общий вид функции сходства. Для этого заметим, что любое выравнивание можно разбить на чередующиеся блоки - совпадающих, несовпадающих и делетированных элементов. Например, на рис.1.9,в мы имеем И таких блоков: с 1-й по 4-ю позицию - блок делеций в первой последовательности, 5-9-я позиция - блок совпадений и т.д.. После такого разбиения можно определить функцию сходства как сушу функций сходства по блокам:
F=E fm(km) + E fc(kc) + E fd(kd) . (1.2)
где km, kc, kd - длины блоков совпадений, несовпадений, делеций, а fM, fc, fd - функции сходства для этих блоков соответственно. Функция сходства (1.2) может использоваться, например, при выравнивании кодирующих областей, поскольку делеции/вставки, не кратные размеру кодона, приводят к сбою рамки считывания, и за них необходимо назначать значительно большие штрафы, чем за делеции/вставки, кратные трем. При анализе блочных перестроек обычно назначают штраф за делецию, слабо зависящий от размера делеции и т.п.
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 119 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed