Введение к работе
Актуальность темы. По мере роста объемов банков генетической информации актуальной становится задача компьютерного анализа нуклеотидных и белковых последовательностей. Одним из важнейших этапов анализа является установление основных структурных особенностей генома, как-то: кодирующих и некодирующих участков, числа генов, их локализации, знаков пунктуации (фрагментов, отвечающих за регуляцию основных генетических процессов), неслучайных повторов, палиндромов, периодичностей и т.п. В первом приближении генетический текст можно рассматривать как последовательность независимых испытаний, при этом многие структурные особенности проявляются как статистически значимые отклонения от схемы независимых испытаний. Многообразие форм отклонения реальной последовательности от случайной приводит к необходимости создания большого числа алгоритмов, каждый из которых ориентирован на обнаружение закономерностей лишь одного типа. В связи с этим несомненный интерес вызывает использование как можно более универсальных характеристик текста, которые "аккумулируют" в себе значительное количество частных закономерностей. Одной из таких характеристик является сложность текста.
Категория сложности является предметом интенсивных исследований в различных прикладных областях. Анализ сложности генетических текстов представляет большой интерес с классификационной и эволюционной точек зрения.
Целью данной работы является введение меры сложности, ориентированной на генетические тексты, а также разработка и апробация эффективных алгоритмов и программ сложностного анализа последовательностей произвольной длины, позволяющих обнаруживать и классифицировать различные локальные и глобальные структурные закономерности в секвенируемых геномах.
Научная новизна.
Элементы новизны содержатся во всех главах работы. К ним относятся: определение меры сложности генетических текстов и сложностного профиля как универсального инструмента для обнаружения локальных структурных закономерностей (глава 1); рекуррентный алгоритм вычисления сложностного профиля с трудоемкостью существенно меньше квадратичной (глава 2 ); классифика-
ция комбинированных структурных закономерностей (глава 3 ); обнаружение зон обширной гомологии в геноме бактериофага А и формулировка в связи с этим гипотезы об "иерархической дупликации" (глава 4 ); определение интегральных сложностных характеристик генома и алгоритм выявления изоморфішх фрагментов (глава 5 ).
Практическая ценность.
Сложностной анализ может быть использован: а) для поиска всевозможных регулярностей в геноме на разных иерархических уровнях; б) для установления сложностной иерархии геномов и интерпретации ее с эволюционной точки зрения; в) для поиска потенциально возможных знаков пунктуации; г ) для выявления новых типов "комплементарности" и структурных гомологии; д ) для определения сложностных мер сходства двух последовательностей.
Многие элементы анализа носят общелингвистический характер и применимы к текстам из других языковых систем.
Реализация результатов работы.
Программа, реализующая вычисление гистограмм сложности по мере С} и применимая к текстам произвольной природы, использовалась в составе пакета прикладных программ "СИМВОЛ", разработанного в ИМ СО РАН, для классификации зашумленных двоичных последовательностей марковского типа (имеется отзыв от ЦНИИ "Комета", г. Москва).
Программа, реализующая вычисление сложностного профиля по мере Ct , передана во ВНИИ молекулярной биологии (Кольцово) и использовалась для обработки сдвиговых и дрейфовых штаммов вируса гриппа и генома вируса осповакцины (имеется отзыв от ВНИИ МБ).
Метод исследования.
В работе используется теория сложности Колмогорова, структурные методы распознавания образов, элементы теории графов, методы построения и анализа эффективных вычислительных алгоритмов, имитационное моделирование.
Публикации и апробация.
Основные результаты диссертации опубликованы в работах [1-9], докладывались на 3-м всесоюзном совещании "Теоретические исследования и банки данных по молекулярной биологии и ге-
нетике" (Новосибирск, 1988) и на международной конференции "Моделирование и компьютерные методы в молекулярной биологии и генетике" (Новосибирск, 1990), а также обсуждались на семинарах Института математики СО РАН и Института молекулярной биологии им. В.А.Энгельгардта РАН.
Структура и объем работы.