Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
CG
СС
TTGAAGTATCAAGGTGAGGG
которые гомологии длиной 1 могут быть фрагментами более протяженной гомологии. Например, ATATGC и CATATG являются фрагментами семичленника CATATGC. Идеи этого подхода весьма плодотворны, они будут встречаться и в дальнейшем, поэтому целесообразно дать ему название, например, алгоритм 1-граммного разложения, поскольку построение таблиц Т, и Т2 является разложением текста по 1-граммам (фрагментам длиной 1).
Хотя алгоритм 1-граммного разложения применим лишь для решения локальной задачи 1, с его помощью можно существенно ускорить решение задачи 2 и, как мы увидим ниже, задачи о выравнивании. Можно заметить, что если два фрагмента длиной 1 имеют к совпадающих букв, то эти фрагменты имеют идеально совпадающие подфрагменты длиной не менее l'=[l/(l-k+l)]. Поэтому, прежде чем решать задачу 2 с параметрами 1 и 1|, целесообразно решить задачу 1 с параметром 1' и затем вокруг найденных гомологий проверять выполнение условий задачи 2. Этот прием 1озволяет принципиально снизить трудоемкость решения задачи 2, если Только 1' достаточно велико.
Рестриктазное картирование нуклеотидных последовательностей является специальным случаем решения задачи 1. Здесь применение идей 1-грам-много разложения также позволяет значительно ускорить процесс картирования и сделать его практически не зависящим от числа рестрикционных сайтов, подлежащих картированию. Суть заключается в следующем. Все сайты рестрикции приписываются к тетрануклеотидам по первым четырем узнаваемым нуклеотидам. Например, сайт EcoR 1 GAATTC приписывается к четверке GAAT, а сайт Xho 2 (*)GATC(p приписывается к двум четверкам
- AGAT и GGAT. В результате получается таблица (рис.1.7). Обратим внимание на то, что в одной строке разложения таблицы сайтов рестрикции может оказаться больше одного сайта, и наоборот - одна рестриктаза может попасть в несколько строк таблицы. После этого просматривается последовательность. В каждой позиции определяется тетрануклеотид, связанный с ней. Далее по этому тетрануклеотиду в таблице находятся рест-риктазы, которые могут узнать эту последовательность, и их сайты узнавания сравниваются с нуклеотидной последовательностью в этой точке. Это сравнение необходимо для рестриктаз, узнающих более 4 нуклеотидов. Характерным показателем эффективности работы многих пакетов прикладных программ является время, необходимое для картирования плазмиды pBR-322 по 100 сайтам рестрикции. Большинство программ выполняют эту работу за время 1-5 мин, применение же алгоритма 1-граммного разложения позволяет проделать эту работу за несколько секунд.
АААА
АААТ
AGAT Xho 2
СААТ EcoR 1
ССАТ BamH 1
TCAGAGT*
Рис. 1.7. 1-граммное Рис. 1.8. Построение позиционного дерева разложение таблицы сайтов рестрикции
Применение метода 1-граммного разложения для аминокислотных последовательностей сопряжено с большими затратами оперативной памяти, поскольку даже для запоминания трехбуквенных комбинаций требуется 203=&000 строк таблицы разложений. Для того чтобы обойти эту трудность, прибегают к редукции алфавита, т.е. объединяют близкие по свойствам аминокислоты в группы, и в качестве букв в последовательности используют символы, обозначающие группы. Правда, применение подобного рода редукции требует затем проверки гомологий, найденных методом 1-граммного разложения, поскольку при преобразовании алфавита часть информации о последовательности теряется.
Позиционные деревья. Описанный только что метод 1-граммного разложения обладает одним существенным недостатком - ранг 1 разложения должен задаваться заранее, и при этом возможны ошибки двух типов - слишком высокий ранг приводит к потере существенных гомологий, а слишком низкий - к большому информационному шуму. Мартинец (Martinez, 1983) использовал оригинальный способ разложения по уникальным подсловам. Опишем этот способ на примере. Пусть у нас есть последовательность
S={TCAGAGT*},
где * - признак конца последовательности. Тогда строим дерево по следующему алгоритму (рис.1.8). Из корня выпускаем ветви по числу типов букв, которые встречаются в последовательности, и на концах ветвей пишем соответствующие буквы и их позиции, т.е. делаем 1-граммное разложение при 1=1. Если таких позиций оказалось несколько, то значит найденная буква не уникальна, в противном случае (как буква С в нашем примере) найденная буква является уникальным подсловом. Из неуникальных вершин выпускаем ветви по числу типов букв, которые следуют за соответствующей буквой. Так, за буквой А всегда следует буква G, поэтому из клетки А выходит одна ветвь, а из клетки G, за которой могут следовать либо А, либо Т, выходит две ветви. В вершинах второго уровня пишем списки позиций, с которых начинаются соответствующие двухбуквенные слова. Если список состоит из одного элемента, значит это двухбуквенное слово уникально, в противном случае продолжаем ветвление. В конце процесса получаем так называемое позиционное дерево. Каждый путь по нему до висячей веркины описывает уникальные подслова минимальной длины. Показано, что число операций, необходимое для построения такого дерева имеет порядок N’ln(N), где N - длина последовательности.
