Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
г г з 1 1
t t е i 4 г
14 4 2 3 12 11
Э 4 4 2 1
Рис. 1.13. Матрица сходства (а) и карта путей (б) в задаче поиска оптимального пути (vm=l, vd=2,vc=2)
Жирной линией показан оптимальный путь; тонкие линии соответствуют перспективным путям; точечные линии - щетина"- бесперспективные пути
Рис. 1.14. Изменение Функции сходства вдоль пути
F
Чтобы обойти эту трудность, достаточно взглянуть на карту обратных переходов для задачи локальной гомологии или для задачи поиска оптимального пути (рис.1.13,б) и убедиться в том, что эта карта в основном
пуста - на ней встречаются лишь отдельные "веточки". Может быть, в этом случае нет необходимости запоминать всю карту, а лишь только ”ве-точки", отвечающие гомологиям? Это можно сделать так. При работе алгоритма динамического программирования карта обратных переходов и матрица F строятся строка за строкой. Получив очередную строку карты переходов, ее можно упаковать, выбросив пустые элементы и запомнив, где и сколько таких элементов было выброшено. Этот прием позволяет упаковать карту достаточно плотно (в 5-10 раз). В принципе карту обратных переходов можно уплотнить еще примерно в 2 раза, для чего обратим внимание на то, что все веточки обрасли "щетиной”, отвечающей переходам, не имеющим продолжения. Было бы разумно перед упаковкой и запоминанием карты эту "щетину" "сбрить", что делается достаточно просто. Максимальный размер делеции и диагонального перехода по несовпадающим позициям легко определить ld=F(:,j)/vd, lm=F(i,j)/vc. Поэтому достаточно просмотреть ld клеток матрицы гомологии по горизонтали и 1т клеток по диагонали, и если ни из сдной из них невозможно продолжение, значит эта линия - "щетина" и ее надо "сбрить", приравняв к 0 функцию сходства во всех клетках, ей принадлежащих. Этот прием применим при условии, что приоритетным при выборе максимума в формуле (1.4) является переход по диагонали.
Возможен также другой подход к проблеме запоминания карты обратных переходов - не запоминать ее всю. Для этого вспомним метод 1-граммного разложения. Пусть штрафы за делецию и за замену равны vd=vc=2, а премия за совпадение равна vm=l. Тогда ясно, что при этих условиях любая гомология начинается не менее чем с трех совпадающих букв. В этом случае можно предложить подход: методом 1-граммного разложения находим
все совпадающие тройки (назовем их затравками) - с них может начинаться гомология. Начиная с совпадающей тройки пускаем алгоритм динамического программирования. При этом просматривается только часть матрицы гомологии. В процессе построения функции сходства и карты обратных переходов запоминаются только ненулевые перспективные клетки, связанные с выбранной 1-граммой. Функция сходства F и карта обратных переходов строятся до тех пор, пока не получится пустая строка, т.е. строка, не содержащая ни одной ненулевой перспективной клетки, связанной с затравкой. После этого находим наибольшее значение функции сходства и с помощью карты обратных переходов восстанавливаем выравнивания. Полученные выравнивания запоминаем, а карту обратных переходов теперь можно забыть и использовать освободившуюся память для построения другого выравнивания. Применение этого подхода позволяет находить локальные гомологии при ограниченном ресурсе памяти. Следует, однако, иметь в виду, что описанный алгоритм не гарантирует выполнения всех условий локальной гомологии, а именно может нарушиться условие непересечения путей. Чтобы этого не произошло, следует проверить, не является ли затравка фрагментом уже найденной локальной гомологии. При наличии та-
кой проверки описанный алгоритм оказывается весьма эффективным, поскольку его использование не требует работы со всей матрицей, а просматриваются только "веточки’’, определяющие локальную гомологию. Иными словами, экономия памяти позволила сэкономить время счета, причем тем больше, чем менее "ветвисты" карты обратных переходов, а это, в свою очередь, связано с параметрами гомологии - чем выше отношение vd/vm, тем меньше ветвлений на карте, а стало быть, меньше время счета. К сожалению, строгую оценку трудоемкости этого алгоритма сделать не удается.
При описании точечных матриц гомологии говорилось о проблеме фильтрации. В качестве альтернативы описанному методу фильтрации можно использовать следующий фильтр: точка ставится в том случае, если она
принадлежит локальной гомологии (Staden, 1982). В этом случае точечная матрица гомологии выступает в качестве спссоба визуализации результатов поиска гомологи?.
1.4. ПОИСК ГОМОЛОГИЙ ПО БАНКУ ГЕНЕТИЧЕСКИХ ТЕКСТОВ
Применение метода 1-граммного разложения. Одной из наиболее интересных и в то же время наиболее трудных задач, связанных с поиском гомологий, является задача поиска гомологий по банку генетических текстов. Трудность решения подобного рода задач связана с анализом колоссальных объемов информации. Так, объем банка нуклеотидных последовательностей в настоящее время превосходит 107 букв и это число стремительно растет. Применение описанных выше квадратичных по числу операций методов требует для решения таких задач порядка 10м операций и больших объемов памяти и доступно лишь самым мощным суперкомпьютерам (Gotoh.Tagashira, 1986). С другой стороны, можно попытаться найти альтернативные методы с тем, чтобы решение таких задач стало возможным на персональных компьютерах средней мощности.
