Информационно-статистический анализ нуклеотидных последовательностей тема диссертации и автореферата по ВАК РФ 03.00.02, доктор физико-математических наук Садовский, Михаил Георгиевич

• Садовский, Михаил Георгиевич
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Садовский, Михаил Георгиевич

Введение

Глава 1. Обзор основных проблем биоинформатики и анализа символьных последовательностей

§1.1. Основные задачи в исследованиях символьных последовательностей

§ 1.2. Проблема аннотирования геномов

§1.3. Модели генетических текстов

§1.4. Построение словарей генетических текстов

§ 1.5. Распознавание структурных закономерностей в генетических текстах

§ 1.6. Методы сравнения генетических текстов

§1.7. Информация и энтропия

§1.8. Выводы Главы

Глава 2. Частотный словарь. Случай глобального восстановления.

§ 2.1. Соотношение "последовательность - конечно-частотный словарь" и проблема восстановления целого из частей

§ 2.2. Конечно-частотный словарь и проблема восстановления полной 39 последовательности

§2.3. Характеристики конечно-частотных словарей для реальных нуклеотидных последовательностей

§ 2.4. Изменение избыточности генов в результате сплайсинга

§ 2.5. О распределении наидлиннейших повторов в различных участках 76 последовательности

§ 2.6. О распределении наидлиннейших повторов в геномах некоторых 85 организмов

§ 2.7. Выводы Главы

Глава 3. Частотный словарь. Случай локального восстановления

§3.1. Задача локального восстановления. Гипотеза наиболее вероятного 98 продолжения

§ 3.2. Принцип максимума энтропии частотного словаря и восстановление частотных словарей большей толщины по заданному

§ 3.3. Локальное востановление частотных словарей и проблема выбора статистической модели генетического текста

§3.4. Информационное содержание частотных словарей

§ 3.5. Предельная энтропия, удельная энтропия и качество восстановления 112 частотных словарей

§ 3.6. Качество восстановления для некоторых реальных символьных последовательностей

§ 3.7. Отличия реальных и восстановленных частотных словарей некоторых генетических текстов

§3.8. Сравнительное исследование информационных свойств генов вирусов и генов их хозяев

§3.9. Информационная ёмкость некоторых геномов

§ 3.10. Микроинформационная структура генов и геномов

§ 3.11. Самоподобие геномов

§3.12. Выводы Главы

Глава 4. Распределение информационно значимых слов в геномах

§4.1. Поиск и выделение информационно значимых сайтов в символьных 228 последовательностях

§ 4.2. Поиск и выделение информационно значимых сайтов в некоторых биологических последовательностях

§ 4.3. Поиск и выделение информационно значимых сайтов в геномах

§ 4.4. Информационно значимые сайты функционально различных частей в 255 геномах

§ 4.5. Связь между информационно значимыми сайтами различной длины в 258 геномах

§ 4.6. О связи структуры и функции в геномах: статистическая семантика 274 геномов

§ 4.7. Выводы Главы

Глава 5. Информационные и статистические подходы к определению близости символьных последовательностей

§5.1. Сравнение символьных последовательностей по носителям их конечно-частотных словарей

§ 5.2. Сравнение генетических текстов по носителям их конечно-частотных 287 словарей

§ 5.3. Сравнение символьных последовательностей по их конечночастотным словарям

§ 5,4. Сравнение нескольких символьных последовательностей с помощью их конечно-частотных словарей

§ 5.5. Сравнение символьных последовательностей по их частотным словарям

§ 5.6. Сравнение генетических текстов по их частотным словарям

§ 5.7. Сравнение геномов по наборам их информационно значимых слов

§ 5.8. Сравнение функционально различных частей генома по наборам их информационно значимых слов

§ 5.9. Выводы Главы

Введение диссертации (часть автореферата) на тему «Информационно-статистический анализ нуклеотидных последовательностей»

Символьные последовательности являются классическим объектом математики, а также встречаются как предмет изучения во многих прикладных задачах — от теоретического программирования и теории управления до биологии и лингвистики. Изучение символьных последовательностей позволяет ответить на множество сопряжённых друг с другом вопросов из различных областей науки, смежных с чистой или прикладной математикой. Как объект прикладного исследования символьные последовательности возникают во всех областях, где рассмотриваются те или иные объекты, состоящие из большого числа одинаковых фрагментов. При этом одинаковость (подобие, тождество) может носить искусственный — до определённой степени — характер. Связано это с тем, что именно исследователь по своему усмотрению начинает рассматривать некоторые фрагменты целого — например, нуклеотиды в молекуле нуклеиновой кислоты или символы в текстах того или иного естественного языка, записанные в алфавитной системе записи — как тождественные друг другу, не отличающиеся ничем, кроме своего положения в рассматриваемом объекте — в символьной последовательности.

Биологические макромолекулы играют ключевую роль во многих процессах, протекающих в живых организмах. С момента установления Дж.Уотсоном и Ф.Криком первичной структуры нуклеиновых кислот не прекращается поток исследований, посвященных выяснению роли и места информации, содержащейся в этих молекулах. Изучение структуры, а также функциональных, химических, физико-химических и проч. свойств нуклеиновых кислот активно ведется специалистами в различных областях, и одним из важных направлений является изучение нуклеиновых кислот как символьных последовательностей. В настоящей работе предполагается исследовать лишь те свойства нуклеиновых кислот, которые определяются только взаимным расположением нуклеотидов друг относительно друга в одной изучаемой молекуле; никакие другие факторы — физико-химическое окружение, особенности состава нуклеотидов и т.п. — не рассматриваются.

Особый круг исследований составляют работы, посвященные изучению информационных свойств символьных последовательностей. Получаемые в этих исследованиях теоретические результаты оказываются весьма полезными и эвристически ценными во многих смежных и даже отдалённых областях. Однако в самих исследованиях информационных свойств символьных последовательностей существует определённое смешение таких существенно различных понятий, как собственно понятие информации и семантическое наполнение того объекта, информационные характеристики которого являются предметом изучения. Такого рода смешение приводит к возникновению новых, искусственных понятий, например, понятия ценности информации и проч.

Само понятие информации связано с изучением внешней формы представления того или иного сообщения; при этом такое сообщение должно бьггь представлено как последовательность однотипных объектов (например, букв в текстах из естественных языков, либо последовательности нулей и единиц в программах для ЭВМ и т.п.). Понятие информации в первую очередь связано с формой представления, а связь с её содержанием (смыслом) исследуется в таких задачах лишь в той мере, в какой это необходимо для прояснения свойств формы представления информации. Настоящая работа посвящена исследованию этого первого аспекта в свойствах символьных последовательностей.

Как хранение, так и реализация какой-либо информации напрямую, обусловлены тем обстоятельством, что в ходе этих процессов актуальную роль играют символьные последовательности. При этом хорошо известно, что в природе фактически нет процессов, связанных с переработкой либо реализацией той или иной информации, которые бы вовлекали всю такого рода символьную последовательность целиком: чтение и обработка файлов вычислительными машинами происходит малыми порциями (байтами) и последовательно, чтение и переработка письменной информации человеком происходит малыми порциями (словами, либо абзацами) и последовательно, чтение и переработка наследственной информации в биологических системах происходит малыми порциями (кодонами) и последовательно. Это простое обстоятельство, тем не менее, имеет важные последствия. Оно требует перехода от рассмотрения всей символьной последовательности в целом к рассмотрению набора её фрагментов.

Выделение таких фрагментов может быть сделано многими разными способами, даже в пределах одной предметной области и даже одной задачи. Конкретный способ выделения фрагментов определяется целями и задачами того или иного конкретного исследования. Одна из важнейших задач, возникающая при работе с наборами фрагментов исходной символьной последовательности — это задача восстановления полной последовательности по набору её фрагментов; например, такого рода задачи всегда возникают в исследованиях по атрибуции авторства текста, а также в задачах по гибри-дизационному секвенированию нуклеотидных последовательностей. При этом следует отметить, что сама по себе проблема восстановления целого из частей — в нашем случае это проблема восстановления последовательности по набору её фрагментов — разбивается на два отдельных вопроса. Первым является вопрос о принципиальных ограничениях на возможность восстановления всей символьной последовательности по максимально полному набору её фрагментов; вторым является вопрос о восстановлении последовательности по неполному набору фрагментов. Этот второй вопрос имеет существенное прикладное значение, поскольку в его рамках можно вести речь об анализе и изучении несвязных символьных последовательностей — иными словами, об извлечении информации из данных с пробелами. Более формально такая конструкция, с помощью которой изучаются статистические и информационные характеристики символьных последовательностей, называется частотным словарём (толщины д). Частотный словарь толщины д — это набор всех связных подпоследовательностей длины д, встречающихся в данной последовательности с указанием их частот, то есть нормированный на единицу. Частотный словарь соответствует не единственному тексту, а их ансамблю. Сам по себе частотный словарь также может быть построен по-разному: он может содержать всю доступную информацию о фрагментах (то есть, все встречающиеся фрагменты могут быть включены в частотный словарь), а может содержать лишь часть доступной информации. Разные постановки требуют использования различных частотных словарей, однако в нашей работе мы систематически будем использовать первую конструкцию — частотный словарь, содержащий все встречающиеся в последовательности фрагменты.

Другая важная проблема, имеющая общую значимость для любых прикладных исследований, предметом которых являются те или иные символьные последовательности, состоит в сравнении двух (или нескольких) символьных последовательностей. Дело в том, что символьные последовательности относятся к такому классу объектов, для которых определение расстояния между ними возможно, однако оно очень "бедно": очень часто формально введённое расстояние никак не отражает близость или, наоборот, существенные различия свойств, приписываемых исследователем изучаемым символьным последовательностям. Здесь имеет смысл рассматривать меру близости двух (или нескольких) последовательностей, и для её построения информационные и статистические методы являются весьма универсальными и продуктивными.

Наконец, нельзя не сказать о том, что все или почти все результаты, полученные для символьных последовательностей, могут быть распространены на более сложные дискретные объекты — например, на цифровые (растровые) изображения; символьные последовательности, являясь существенно более простым объектом, представляют собой своеобразный полигон для развития методов и предсказания наиболее общих результатов об информационных свойствах различных дискретных объектов.

Цель работы состоит в разработке подходов для исследования тех свойств символьных последовательностей различной природы, которые определяются только их информационными и статистическими характеристиками: проблемы локального восстановления частотных словарей большего размера по заданным, проблемы определения меры близости двух или нескольких последовательностей по их информационным характеристикам, проблемы сравнения реального частотного словаря символьной последовательности и того, который может быть построен по набору слов меньшей длины исходя из гипотезы о наиболее вероятном продолжении, а также проблемы соотношения между фрагментами символьной последовательности с высоким информационным содержанием и функциональной ролью тех регионов последовательности, которые такие фрагменты содержат (поиск и описание информационно значимых слов), а также в систематическом изучении информационных и статистических свойств нуклео-тидных последовательностей.

Научная новизна работы заключается в следующем.

1. Изучены некоторые типичные свойства нуклеотидных последовательностей, проявляющиеся в характеристиках конечно-частотных словарей. На основе этих характеристик построеное новое определение избыточности последовательностей. Показано, что функционально разные части генов эукариотических организмов различаются по этому показателю и сплайсинг генов ведёт к уменьшению их избыточности.

2. Впервые изучены некоторые типичные свойства нуклеотидных последовательностей, проявляющиеся в характеристиках восстановления частотных словарей, состоящих из слов большей длины по словарям заданной толщины (длины слов). Введено понятие информационной ёмкости частотного словаря и изучено её поведение у различных нуклеотидные последовательностей. На основе введённых характеристик исследована микроинформационная структура некоторых генов и геномов, т.е. структура, определяемая различием информационных и статистических свойств двух соседних участков символьной последовательности.

3. Впервые введено строгое определение информационно значимых сайтов нуклеотидной последовательности и развит новый метод выделения таких сайтов. Проанализированы различные семейства геномов с точки зрения выявления в них информационно значимых сайтов. Впервые для информационно значимых слов длины 3 и 4 показано существование специфических наборов, общих для семейства геномов родственных организмов; также впервые проанализирован набор информационно значимых слов длины 3 и 4, характерных для кодирующих и некодирующих областей генома. Показано, что существуют информационно значимые слова этой длины, специфичные для указанных областей.

4. Впервые для информационно значимых сайтов длины 7 и 8 нуклеотидов, характеризующихся высокой информационной значимостью всех входящих в них слов меньшей длины показана неслучайность распределения таких сайтов вдоль по геному: информационно значимые сайты длиной 7 и 8 нуклеотидов встречаются, как правило, в регуляторных областях геномов, причём наблюдается также неравновесность при распределении по регуляторным областям различной природы.

5. Развиты принципиально новые методы сравнения символьных последовательностей, не использующие идею выравнивания. Сравнение символьных последовательностей производится пр их частотным либо конечно-частотным словарям, при этом в первом случае для группы сравниваемых последовательностей строится их статистический предок — искусственный частотный словарь, из которого может быть получен любой из сравниваемых, причём для этого из статистического предка потребуется удалить (либо добавить) лишь необходимый минимум информации. Сравнение символьных последовательностей с помощью конечно-частотных словарей позволяет указать меру близости последовательностей в группе, никак не упорядочивая их внутри неё.

6. Предложен новый метод сравнения символьных последовательностей на основе сравнения наборов их информационно значимых слов различной длины. Показано, что для некоторых миркоорганизмов вариабельность генома, определяемая по такому показателю близости, превосходит вариабельность, наблюдаемую при сравнении отдельных хромосом различных геномов, на основе сравнения наборов информационно значимых сайтов длины 3 и 4 введена мера внутригеномного разнообразия.

Практическая ценность работы заключается в:

1) изучении статистических свойств символьных последовательностей, соответствующих конкретным генам различных организмов;

2) развитии новых методов исследования информационной ёмкости символьных последовательностей;

3) развитии новых методов исследования информационной значимости малых фрагментов символьных последовательностей, на основе которых возможна грубая разметка не аннотированного генома;

4) развитии новых методов сравнения символьных последовательностей различной природы, не опирающихся на идею редакционного расстояния.

Структура работы. Работа состоит из Введения, пяти глав и заключения, содержит 57 рисунков и 104 таблицы. Список литературы содержит 193 наименования.

Апробация работы. Основные результаты работы докладывались на 3-ей Международной конференции "Математика, компьютер, образование", Дубна, 29 янв. - 3 фев. 1996 г., на Сибирском конгрессе по прикладной математике, Новосибирск, 22 - 26 июня 1996 г., на 5-ой Всероссийской конференции "Нейроинформатика и её приложения", Красноярск, 22 - 25 сентября 1997 г., на 5-ой Международной конференции "Математика, компьютер, образование". Дубна, 29-31 янв. 1998 г., на 1-ой Международной конференции по Биоинформатике в Геномной Регуляции и Структуре генома, Новосибирск, 24 - 27 августа 1998 г., на 3-ем Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98), Новосибирск, 24 - 26 июня 1998 г., на 6-ой Международной конференции "Математика, компьютер, образование" Пущино, 3 — 8 января 1999 г., на II-ом Съезде биофизиков России, Москва, 23 —27 авг.1999 г., на 9-ой Всероссийской конференции "Нейроинформатика и её приложения", Красноярск, 5-7 октября 2001 г., на I Всероссийской ФАМ-конференции, Красноярск, 1 - 3 марта 2002 г., на 10-ой Всероссийской конференции "Нейроинформатика и её приложения", Красноярск, 4-6 октября 2002 г., на 5 Международной конференции (5th International Conference on Molecular Structural Biology), Вена, 4-7 сентября 2003 г.

Результаты работы также докладывались на семинарах в Институте биофизики СО РАН, Институте вычислительного моделирования СО РАН, Вычислительном Центре РАН (г.Москва), Институте молекулярной биологии РАН (г.Москва), Институте теоретических проблем биологии РАН (г.Пущино), биологическом факультете МГУ (г.Москва), на семинаре в ГУ НИИ Биомедицинской химии им. В.Н. Ореховича РАМН (г.Москва).

Публикации по теме работы. Основные результаты работы опубликованы в: Горбанъ А.Н., Мирнее Е.М., Попова Т.Г., Садовский М.Г. Новый подход к изучению статистических свойств генетических последовательностей // Биофизика, (1993), т.38, № 5, с.762 - 767; Горбанъ А.Н., Мирнее Е.М., Попова Т.Г., Садовский М.Г. Сравнительная избыточность генов различных организмов и их вирусов // Генетика (1993), т.29, 9, с. 1413 - 1419; Mirkes Е.М., Popova T.G., Sadovsky M.G. Investigating Statistical Properties of Genetic Texts: A New Approach // Advances in Modelling & Analysis, ser. В, AMSE Press, (1993) vol.27, № 2, p.l - 13; Горбанъ A.H., Попова Т.Г., Садовский М.Г.

Избыточность генетических текстов и мозаичная структура генома // Мол.биология (1994) т.28, № 2, с.313 - 322; Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: new method to compare two genes // Modelling, Measurement & Control, ser. C, (1994) AMSE Press, vol.45, № 4, p.27 - 36; Popova T.G., Sadovsky M.G. The new measure of relationship between two symbolic sequences // Advances in Modelling & Analysis, ser. A, (1994) AMSE Press, vol.22, № 2, p. 13 - 17; Горбань A.H., Попова Т.Г., Садовский М.Г. Корреляционный подход к сравнению нуклеотидных последовательностей // ЖОБ (1994), т.55, № 4/5, с.420 - 430; Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: local redundancy displays a new structure of genes // Advances in Modelling & Analysis, ser. C, (1995) AMSE Press, vol.48, № 4, p. 17 - 22; Попова Т.Г., Садовский М.Г. Избыточность генов уменьшается в результате сплайсинга // Мол.биология (1995) т.29, № 3, с.500 - 506; Попова Т.Г., Садовский М.Г. Интроны отличаются от экзонов по своей избыточности // Генетика (1995) т.31, № 10, с.1365 -1369; Бугаенко Н.Н., Горбань А.Н., Садовский М.Г. Об определении информационного содержания нуклеотидных последовательностей // Мол.биология (1996) т.30, № 3, с.529 - 541; Горбань А.Н., Попова Т.Г., Садовский М.Г. Гены вирусов человека менее избыточны, чем гены человека // Генетика (1996) т.32, № 2, с.281 - 294; Бугаенко Н.Н., Горбань А.Н., Садовский М.Г. Метод максимума энтропии для восстановления частотных словарей и определения информационной ёмкости нуклеотидных последовательностей // Вычислительный центр СО РАН в г. Красноярске, Красноярск, 1997. - Деп. в ВИНИТИ 09.04.97, № 1878-В97; Bugaenko N.N., Gorban A.N., Sadovsky M.G. Maximum entropy method in analysis of genetic text and measurement of its information content // Open Systems & Information Dynamics, 1998, v.5, № 3, pp.265 -278; Gorban A.N., Popova T.G., Sadovsky M.G. Automatic classification of nucleotide sequences and its relation to natural taxonomy and protein function // Proc. of 1st Int. Conf. on Bioinformatics of Genome Regulation and Structure, Novosibirsk, Aug., 24 - 27, 1998; vol.11., p.314 - 317; Bugaenko N.N., Gorban A.N., Sadovsky M.G. Maximum entropy principle and measurement of information content of genetic texts // Proc. of 1st Int. Conf. on Bioinformatics of Genome Regulation and Structure, Novosibirsk, Aug., 24 - 27, 1998; vol.11., p.283 - 286; Kirsanova E.N., Sadovsky M.G. Entropy approach to a comparison of images // Open Systems & Information Dynamics, 2001, v.8, № 1, pp.183 - 199; Кирсанова E.H., Садовский М.Г. Метод статистического сравнения объектов // "Радиоэлектроника. Информатика. Управление." № 2, 2000, стр. 71 - 82; Кирсанова Е.Н., Садовский М.Г. Об информационной значимости цифровых изображений // "Радиоэлектроника. Информатика. Управление." № 2, 2001, стр. 88 - 95; Садовский М.Г. Об информационной ёмкости символьных последовательностей // "Радиоэлектроника. Информатика. Управление." № 1, 2002, стр. 82 - 86; Sadovsky M.G. Comparison of Symbol Sequences: No Editing, No Alignment // Open Systems & Information Dynamics, 2002, v.9, № I, pp.19 - 36; Sadovsky M.G. Information capacity of symbol sequences // Open Systems & Information Dynamics, 2002, v.9, № 1, pp.37 - 49, Gorban A.N., Popova T.G., Sadovsky M.G., Wunsch D.C. Information content of the frequency dictionaries, reconstruction, transformation and classification of dictionaries and genetic texts // Intelligent Engineering Systems through Artificial Neural Netwerks: v. 11 - Smart Engineering System Design, N.-Y.: ASME Press, 2001, p. 657 - 663; Садовский М.Г. К вопросу об избыточности геномов вирусов и прокариот // Генетика,

2002, т. 38, № 5 с. 695 - 701; Горбань Л.Н., Попова Т.Г., Садовский М.Г. Классификация нуклеотидных последовательностей по частотным словарям обнаруживает связь между их структурой и таксономическим положением организмов // ЖОБ, 2003, т. 64, № 1, стр. 51 - 63; Sadovsky M.G. Comparison of real frequencies of strings vs. the expected ones reveals the information capacity of macromoleculae // Journal of Biological Physics,

2003, vol. 29, № 1, pp. 23 - 38; Sadovsky M.G. The method of comparison of nucleotide sequences based on the minimum entropy principle // Bulletine of Mathematical Biology, 2003, vol. 65, № 2, pp. 309 - 322; Мамонова М.Л., Садовский М.Г. Информационная ценность различных триплетов некоторых генетических систем // ЖОБ, 2003, т.64, № 5, с.421 -433.

Работа выполнена в лаборатории экологической биотехнологии Институт биофизики СО РАН. Результаты, полученные в ходе работы были получены при поддержке Красноярского научного фонда, гранты 1Р0390, ЗР0190,4Р0153, 5Р0012 и 1Ш14С.

Заключение диссертации по теме «Биофизика», Садовский, Михаил Георгиевич

Выводы

1. Введено новое определение избыточности нуклеотидной последовательности. Показано, что этот показатель различается для функционально различных частей гена, а сплайсинг приводит к уменьшению этого показателя у эукариотических организмов. Для генов прокариот, а также для генов вирусов этот показатель существенно более вариативен, а сплайсинг не всегда приводит к уменьшению избыточности.

2. Введено новое определение информационной ёмкости частотного словаря. Для всех исследованных генетических систем установлено, что информационная ёмкость изменяется немонотонно с ростом толщины словарей. Для всех исследованных генетических систем обнаружено существование одного или двух локальных минимумов информационной ёмкости для частотных словарей.

3. Введено понятие микроинформационной структуры нуклеотидной последовательности. Показано, что данная структура коррелирует с иными, выделяемыми в геномах — в первую очередь, с областями расположения кластеров генов консервативных белков, кластеров генов транспортных РНК, либо кластеров регуляторных генов.

4. Введено понятие самоподобия нуклеотидной последовательности. Показано, что данная структура также коррелирует с иными, выделяемыми в геномах — в первую очередь, с областями расположение кластеров генов консервативных белков, кластерам генов транспортных РНК, либо кластерам регуляторных генов, однако как правило не совпадает с микроинформационной структурой.

5. Введено понятие информационно значимого слова в частотном словаре — такого слова, у которого реальная частота существенно отличается от ожидаемой. Показано, что такие слова длины 6 и выше распределены вдоль по геному неслучайно, а как правило встречаются в окрестности начала регуляторных генов. На основе введённого понятия сформулирована строгая постановка проблемы выявления связи между структурой и функцией нуклеотидной последовательности, сводящаяся к построению функции распределения вероятности обнаружения того или иного функционально значимого (семантически нагруженного) фрагмента нуклеотидной последовательности в окрестности фиксированной ширины вокруг точки вхождения в геном информационно значимых слов.

6. Изучено поведение последовательностей информационно значимых слов возрастающей длины, вложенных друг в друга, определяющих информационно значимые сайты. Эти сайты распределяются вдоль по геному не случайно, а тяготеют к определённым его участкам. Наиболее высока частота встречаемости таких сайтов в генах транспортных РНК, а также в регуляторных участках малой длины (промотерах).

7. Развиты новые методы сравнения символьных последовательностей по частотным словарям, не использующие идею выравнивания. Эти методы позволяют сравнивать произвольное число последовательностей произвольной длины и не требует введения системы штрафных функций и выбора референтного образца.

8. Построен новый метод определения различия между последовательностями на основе сравнения наборов информационно значимых слов. Показано, что для геномов бактерий, состоящих из двух хромосом, различие на длине слов 3 существенно больше аналогичного на длине слов 4.

9. Исследовано распределение информационно значимых слов длины 3 и 4 в наборе геномов фагов и вирусов. Среди этих слов выделяются такие, которые встречаются во всех геномах, и такие, которые специфичны только для одного генома (либо малой подгруппы геномов). Число информационно значимых слов длины 3 и 4, общих для группы сравниваемых геномов, падает с ростом различий в таксономическом положении носителей этих геномов.

10. Изучение наборов информационно значимых слов длины 3 и 4 отдельно для кодирующих и некодирующих областей геномов различных организмов выявляет в них группу слов высокой информационной значимости, специфичную для каждой из областей. Кроме того, для каждого из геномов выделяются слова высокой и21формаци-онной значимости, не специфичные для кодирующих либо некодирующих областей. Такие слова могут рассматриваться как инварианты.

Заключение

Анализ статистических и информационных свойств нуклеотидных последовательностей имеет как фундаментальное, так и прикладное значение. Основная научная ценность такого анализа — возможность выявления различных свойств нуклеиновых кислот, определяющихся взаимным расположением нуклеотидов в них, причём упомянутые свойства определяются только порядком следования нуклеотидов и никак не зависят от иной, дополнительной информации, не содержащейся в нуклеотидной последовательности и непосредственно. Ключевым вопросом в исследованиях статистических и информационных свойств нуклеотидных последовательностей является проблема соотношения целого и частей: что именно можно сказать о последовательности в целом, располагая лишь информацией о составе её отдельных, сравнительно коротких, фрагментов? • .

Основным инструментом исследований в этом направлении является частотный словарь рассматриваемой нуклеотидной последовательности. Частотный словарь — это набор всех слов (связных фрагментов фиксированной длины), встречающихся в изучаемой последовательности вместе с указанием их частот. Тогда вопрос о соотношении части и целого может быть сформулирован как вопрос о переходе от словарей фиксированной толщины к словарям большей толщины. Толщина словаря — это длина слов, которые он содержит. При этом можно ставить вопрос о построении словаря такой толщины, которая бы совпадала с длиной исходной последовательности и, тем самым, считать вопрос о переходе от частей к целому разрешённым. В такой постановке возможны два ответа: по словарю заданной толщины восстановление всей последовательности возможно однозначно и по словарю заданной толщины однозначное восстановление всей последовательности невозможно, а возможно лишь восстановление ансамбля последовательностей (т.е. словаря, где последовательностей много, и каждая встречается один или несколько раз).

Вопрос об однозначном и полном восстановлении всей последовательности по её частотному словарю имеет конструктивное решение. Критическая длина слов, которая позволяет провести такое восстановление, является новой мерой избыточности символьной последовательности. Собственно избыточность здесь понимается как возможность однозначно и точно восстановить всю последовательность по набору её фрагментов указанной длины. Оказывается, что все гены обладают примерно одинаковым значением избыточности, определяемой таким образом, а вот структурные элементы отдельных генов — экзоны и интроны — различной: у интронов она выше, чем у экзонов, для генов эукариотических организмов. Данная картина в поведении избыточности для экзонов и интронов весьма типична, хотя для генов вирусов, а также для генов прокариотических организмов в ней часто наблюдаются нарушения.

В случае неоднозначности восстановления частотных словарей большей толщины по словарям заданной толщины возникает не единственный словарь, а семейство частотных словарей. Выбор того словаря из семейства, который можно считать восстановленным, требует явного указания правила выбора. Наиболее традиционным в молекулярной биологии и биоинформатике путём является правило выбора восстановленного словаря, основывающееся на той или иной гипотезе о структуре исходного текста; наиболее популярной является гипотеза о том, что исходный текст представим Марковской цепью некоторого порядка.

В нашей работе использован другой подход, основанный не на гипотезах о свойствах исходной нуклеотидной последовательности, а на гипотезе о наиболее вероятном продолжении слов в заданном словаре. Восстановленным (либо продолженным) следует считать такой частотный словарь, который содержит наиболее вероятные продолжения слов заданной длины. Такой словарь обладает максимальным значением энтропии среди всех остальных, порождаемых исходным. Этот экстремальный принцип восходит к методу инвариантных многообразий, первоначально развитому для задачи анализа уравнения Больцмана. Частоты восстановленного словаря могут быть вычислены явным образом по частотам исходного словаря. Получающаяся формула совпадает с формулой переходных вероятностей Марковского процесса, для случая продолжения частотного словаря на один нуклеотид; в случае продолжения на несколько символов формула имеет некоторые отличия. В теории уравнения Больцмана такое решение известно, как приближение Кирквуда. В нашем случае оно является точным решением, но совершенно не свидетельствует о марковости исходной нуклеотидной последовательности. Оно означает, что Марковская модель является лишь той самой моделью исходного генетического текста, которая реализует принцип наиболее вероятного продолжения.

Сравнение реального частотного словаря некоторой фиксированной толщины и того, который может быть построен в силу принципа максимума энтропии по более тонкому позволяет ответить на вопрос об информационной ёмкости генома (точнее, его частотного словаря). Информационная ёмкость — это способность частотного словаря содержать в себе достаточное число плохо предсказываемых слов. Возможны различные подходы к сравнению реального и восстановленного частотных словарей; в настоящей работе использован способ, основанный на вычислении условной энтропии реального частотного словаря относительно восстановленного до той же толщины, по другому реальному, меньшей толщины.

Указанный способ позволяет также сравнивать статистические и информационные свойства отдельного фрагмента длиной в несколько сотен или тысяч нукпеоти-дов и аналогичные свойства всего генома. Как показано в настоящей работе, все геномы обладают весьма сложными профилями статистических и информационных свойств, определяемых для выделенных фрагментов различной длины, относительно всего генома.

Информационную ёмкость генома (и рост значений условной энтропии, соответственно) определяют те слова, для которых реальная частота в наибольшей степени отличается от наиболее ожидаемой. Ожидаемая частота оценивается по частотам слов меньшей длины с помощью принципа наиболее вероятного продолжения. Такие слова были названы нами информационно значимыми. В работе исследовано поведение наборов информационно значимых слов различной длины. Вообще, свойство быть информационно значимым не является монотонным: информационно значимое слово данной длины может входить, а может и не входить в информационно значимое слово длиной на один нуклеотид больше, а затем опять входить или не входить, и так далее. В работе изучен специальный случай, когда в информационно значимые слова длины 8 включались информационно значимые слова всех меньших длин, последовательно: информационно значимые слова длины 8 содержали в себе информационно значимые слова длины 7, те, в свою очередь — информационно значимые слова длины 6, и так далее, до информационно значимых слов длины 3. Такие цепочки были названы восходящими или нисходящими пирамидами, в зависимости от того, какая именно частота превышала другую — реальная ожидаемую (восходящие пирамиды), или ожидаемая — реальную (нисходящие пирамиды). Могут также существовать для генома и пирамиды, не являющиеся пи восходящими, ни нисходящими.

Пирамиды представляют собой графы, в которых вершины соответствуют информационно значимым словам возрастающей длины, а рёбра — вложению одного слова в другое, на один нуклеотид длиннее предыдущего. Для различных геномов и для различных значений порога информационной значимости возникают различные пирамиды. Самое короткое слово в пирамиде называется его корнем, самое длинное — вершиной. В работе исследовались восходящие и нисходящие пирамиды некоторых геномов. Такие пирамиды отображают близость и подобие в информационных свойствах геномов, по которым они строятся. Исследования геномов бактерий, состоящих из двух хромосом, показали, что различия в пирамидах, наблюдаемые в пределах одного генома, часто оказываются сопоставимыми с различиями, наблюдаемыми между геномами различных видов (и даже таксонов более высокого ранга).

Информационные профили геномов, выделяемые сравнением частотных словарей, построенных по фрагментам фиксированной длины со словарями, построенными по всему геному, позволяют утверждать, что информационно значимые слова распределяются вдоль по геномам неслучайно и неравномерно. Центральным местом в исследованиях, представленных в настоящей работе, является вопрос о распределении информационно значимых слов вдоль по геному. Точнее, исследовалось распределение вершин восходящих и нисходящих пирамид вдоль по геному. Было установлено, что такие вершины распределены вдоль по геному весьма неслучайно и неравномерно. Они тяготеют к определённым фрагментам генома. Во-первых, они тяготеют к кластерам генов, кодирующих различные транспортные РНК (для геномов митохондрий), кодирующих различные Б РНК (для геномов хлоропластов и митохондрий), к регуляторным областям (промоторам) — для геномов бактерий. Кроме того, было установлено, что наблюдается повышенная частота появления вершин таких пирамид в некоторой вполне фиксированной окрестности (обычно окрестность имеет порядок 200 нуклеотидов) границы кодирующих и некодирующих областей для бактериальных геномов.

Сделанное наблюдение позволяет дать точную формулировку проблеме поиска связи между структурой и функцией нуклеотидной последовательности. Если под структурой понимать пирамиды, а под функцией — классы эквивалентности различных функционально нагруженных элементов генома, то тогда проблема поиска связи между структурой и функцией нуклеотидной последовательности формулируется следующим образом. Решением проблемы является построение функции распределения вероятности обнаружения какого-либо функционально нагруженного элемента генома, принадлежащего одному классу, в зависимости от расстояния до вершины пирамиды от этого элемента. Такая функция может учитывать наличие как крупно масштабной структурированности, так и близкого порядка в геномах.

Ответом на вопрос о соответствии структуры и функциональной роли того или иного фрагмента генома в собственном смысле является суперпозиция всех таких функций распределения, построенная для каждой точки вхождения одного и того же информационно значимого слова. Структурой является набор всех информационно значимых слов заданной длины, которые тем или иным образом соотносятся с элементами функционально нагруженных участков генома (это могут быть идентичные гены, либо различные гены, но отнесённые исследователем к одному и тому же классу). Суперпозиция всех функций распределения вероятностей обнаружения функционально нагруженного участка из одного класса и является решением задачи выявления связи между структурой и функцией нуклеотидной последовательности.

Основную проблему в выявлении связи структуры и функции составляет понимание того, что такое функция. В нуклеотидных последовательностях выделяют достаточно обширный набор функционально различных элементов. При этом роль таких элементов в процессах реализации наследственной информации может достаточно сильно различаться. В первом (и, быть может, самом важном) приближении нуклео-тидную последовательность можно считать состоящей из фрагментов двух типов — кодирующей и некодирующей частей. Кодирующие участки, в свою очередь, могут быть разделены на экзоны и интроны, а в некодирующих также могут выделяться свои структурные элементы, в отношении которых можно подозревать некоторую функциональную нагруженность.

Отдельную важную проблему молекулярной биологии, биофизики и биоинформатики составляет задача сравнения символьных последовательностей. Традиционно используемый метод выравнивания не свободен от ряда ограничений, делающих его непригодным для сравнения столь длинных последовательностей, как полный геном. Изучение частотных словарей позволяет решить проблему сравнения. Сравнение собственно последовательностей заменяется сравнением их частотных словарей. Частотные словари сравниваются не непосредственно, а через промежуточный объект — гибридный частотный словарь. Частоты слов в гибридном словаре являются средними арифметическими частот слов в сравниваемой группе. Такой выбор частот гибридного словаря обеспечивает минимум суммы условных энтропий каждого из сравниваемых словарей относительно гибридного. Сам гибридный словарь может не соответствовать никакой реальной последовательности, однако является общим статистическим предком группы сравниваемых словарей — из него можно породить, добавив или удалив абсолютно необходимый минимум информации, любой частотный словарь из сравниваемой группы. Собственно мерой сравнения является значение условной энтропии того или иного частотного словаря из сравниваемой группы, вычисленное относительно гибридного частотного словаря. Развитый метод сравнения позволяет сравнивать любое число последовательностей любой длины, и не требуется выбора опорной последовательности. Кроме того, сравниваемые последовательности могут сколь угодно сильно различаться по своей длине.

Сравнение конечных словарей (т.е. словарей, содержащих слова и числа копий, в которых они представлены в последовательности) также позволяет провести информативное сравнение последовательностей. Для этого подсчитывается мощность объединения двух (или нескольких) конечных словарей и мощность пересечения двух (или нескольких) конечных словарей. Отношение этих мощностей представляет собой весовую функцию, по которой можно построить меру близости двух (или нескольких) конечных словарей. Данная мера изменяется в пределах от 0 до 1; нулевое значение соответствует полностью непересекающимся словарям, в то время, как единичное значение — полностью совпадающим словарям.

Изучение наборов коротких информационно значимых слов (длиной 3 и 4 нук-леотида) также позволяет сравнивать нуклеотидные последовательности. Сравнение производится с помощью специальной функции, которая учитывает число совпадающих информационно значимых триплетов (или 4—плетов), т.е. таких, у которых реальная и ожидаемая частоты имеют одинаковый порядок отношения, число несовпадающих информационно значимых триплетов (или 4-плетов), т.е. таких, у которых реальная и ожидаемая частоты имеют разный порядок отношения, и число тех триплетов (или 4-плетов), которые не являются информационно значимыми. Понятно, что результаты сравнения зависят от величины порога информационной значимости. Данная мера скорее характеризует разнообразие пары сравниваемых последовательностей, чем их близость; в качестве результата сравнения естественно рассматривать не близость (или подобие) двух последовательностей при фиксированной величине порога информационной значимости, а кривые, соответствующие разным значениям порога. Указанный метод может быть легко обобщен на случай сравнения не пары, а нескольких последовательностей одновременно.

Список литературы диссертационного исследования доктор физико-математических наук Садовский, Михаил Георгиевич, 2004 год

1. Александров A.A., Александров В.В., Бородовскнй Ю.М. и др. Компьютерный анализ генетических текстов. // М.: Наука, 1990. 264 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов // М.: Мир, 1979. 462 с.

3. Балеску Р. Равновесная и неравновесная статистическая механика. // М.: Мир, 1976. Т.1,2.

4. Бугаенко H.H., Горбань А.Н., Карлин И.В. Универсальное разложение трехчастич-ной функции распределения //Теор. и матем. физика, 1990, т. 28, с.430-441.

5. Бугаенко H.H., Горбань А.Н., Садовский М.Г. Об определении информационного содержания нуклеотидных последовательностей // Мол.биология, 1996, т.30, № 3, с.529 541.

6. Вернослов С.Е., Кондратов A.C., Ройтберг М.А., Шабалипа С.А., Юрьева О.В., На-зипова H.H. Программный комплес "Самсон" для анализа первичной структуры биополимеров // Молекулярная биология, 1989, т.24, № 2, с.524 529.

7. Вирусология в 3-х тт. // М.: Мир, 1989.

8. Гельфанд М.С. Компьютерный анализ последовательностей ДНК // Мол.биология, 1998, т.32, № 1, с. 103- 120.

9. Горбань А.Н. Обход равновесия // Новосибирск: Наука, Сибирское отд., 1984. 386 с.

10. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. Новый подход к изучению статистических свойств генетических последовательностей // Биофизика, 1993, т.38, № 5, с.762 767.

11. Горбань А.Н., Попова Т.Г., Садовский М.Г. Гены вирусов человека менее избыточны, чем гены человека // Генетика, 1996, т.32, № 2, с.281 294.

12. Горбань А.Н., Попова Т.Г., Садовский М.Г. Избыточность генетических текстов и мозаичная структура генома // Мол.биология, 1994, т.28, № 2, с.313 — 322.

13. Горбань А.Н., Попова Т.Г., Садовский М.Г. К проблеме классификации нуклеотидных последовательностей // II Съезд биофизиков России, Москва, 23 27 авг.1999 г., сб. тез., стр. 945 - 946.

14. Горбань А.Н., Попова Т.Г., Садовский М.Г. Классификация нуклеотидных последовательностей по частотным словарям обнаруживает связь между их структурой и таксономическим положением организмов //ЖОБ, 2003, т. 64, № 1, с.51 63.

15. Горбань А.Н., Попова Т.Г., Садовский М.Г. Корреляционный подход к сравнению нуклеотидных последовательностей //ЖОБ, 1994, т.55, № 4/5, с.420 430.

16. Гросберг А.Ю., Рабин И., Хавлин Ш., Нир А. Самоподобие в структуре ДНК: зачем нужны интроны? // Биофизика, 1993, т.38, вып. 1, с.75 83.

17. Гуляев В.К. Кристаллографическая модель для точного задания координат атомов в кристаллах // ДАН, 2001, т.381, № 3, с.325 328.

18. Гуляев В.К., Садовский М.Г. Геном как апериодический одномерный кристалл // Материалы 9-го Всерос.семинара "Нейроинформатика и её приложения", Красноярск, 2001. с.50 -51.

19. Гусев В.Д. Механизмы обнаружения структурных закономерностей в символьных последовательностях // Проблемы обработки информации (Выч. системы, вып. 100). Новосибирск: ИМ СО АН СССР, 1983. с.47 66.

20. Гусев В.Д. Сложностью профили символьных последовательностей // Методы обработки символьных последовательностей и сигналов (Выч. системы, вып. 132). Новосибирск: ИМ СО АН СССР, 1989. с.35 63.

21. Гусев В.Д. Характеристики символьных последовательностей // Проблемы обработки информации (Выч. системы, вып. 88). Новосибирск: ИМ СО АН СССР, 1981. с.11 -34.

22. Гусев В.Д., Немытикова Л.А. Анализ серий в генетических текстах // Обработка сигналов и распознавание образов (Выч. системы, вып. 141). Новосибирск: ИМ СО АН СССР, 1991. с.46-76.

23. Добеши И. Десять лекций по вейвлетам. Москва-Ижевск, РХД. 463 с.

24. Жуков В.А., Устюжинов В.Г., Чермашенцев В.Б. Опыт применения идей распознавания образов в задачах конструирования вырусных препаратов // Обработка сигналов и распознавание образов (Выч. системы, вып. 141). Новосибирск: ИМ СО АН СССР, 1991. с.89 -96.

25. Зубков A.M., Михайлов В.Г Предельные распределения случайных величин, связанных с длинными повторениями в последовательности независимых испытаний // Теор.вер.и её применение, 1974, t.XIX, № 1, с. 173 181.

26. Кирсанова E.H., Садовский М.Г. Информационный подход к анализу цифровых изображений // "Радиоэлектроника. Информатика. Управление.", 2001, № 2, с.88 95.

27. Кирсанова E.H., Садовский М.Г. Метод статистического сравнения объектов // "Радиоэлектроника. Информатика. Управление.", 2000, № 2, с.71 82.

28. Кирсанова E.H., Садовский М.Г. Статистический метод сравнения изображений // 6 Всерос.конференция "Нейроинформатика и её приложения", Красноярск 2-4 октября 1998 г. с.82 83.

29. Козлов К.Н., Мясникова Е.М., Самсонова М.Г., Рейнитц Д., Косман Д. Метод пространственной регистрации картин экспрессии генов сегментации у мушки дрозофилы с использованием вейвлетного разложения // Вычислит.технологии, 2000, т.5, №2,с.112-127.

30. Козлов H.H. Об одном способе записи генетической информации // ДАН, 1994, т.337, № 2, с.158 161.

31. Колмогоров А.Н. К логическим основаниям теории информации и теории вероятностей // Проблемы передачи информации, 1969, т.5, № 3, с.З 7.

32. Колмогоров А.Н. Комбинаторные основания теории информации и исчисления вероятностей//УМН, 1983, т.38, вып.4, с.27-36.

33. Колмогоров А.Н. Три подхода к определению понятия "количество информации" // Проблемы передачи информации, 1965, T.I, № 1, с.З II.

34. Королёв C.B., Соловьёв В.В., Туманян В.Г. Новый метод поиска функциональных участков ДНК с использованием фрактального представления нуклеотидных текстов // Биофизика, 1992, т.37, вып.5, с.837- 847.

35. Левенштейн В.И. О совершенных кодах в метрике выпадений и вставок // Дискрета.математика, 1991, т.З, № 1, с.З -20.

36. Левин Л.А., Звонкин A.K. Сложность задания конечных объектов и развитие идей информации и случайности на основе теории алгоритмов. // УМН, 1970, т.256, с.83 124.

37. Ленинджер А. Биохимия // М.: Мир, 1989, 741 с.

38. Лихошвай В.А., Матушкин Ю.Г. Компьютерная модель для анализа эфолюционно-го дрейфа синонимичных кодонов вдоль мРНК // Вычислит, технологии, 2000, т.5, №2, с.57 63.

39. Математические методы для анализа последовательностей ДНК Под ред. М.С.Уо-термена // М.: Мир, 1999, 349 с.

40. Немытикова Л.А. Использование серийных характеристик для исследования эффекта кластеризации элементов в ДНК-молекулах // Методы анализа данных (Вычислит. системы, вып. 150) Новосибирск: ИМ СО РАН, 1994, с. 147 163.

41. Немытикова Л.А. Методы сравнения символьных последовательностей // Методы обработки символьных последовательностей и сигналов (Выч. системы, вып. 132). Новосибирск: ИМ СО АН СССР, 1989. с.З 34.

42. Попова Т.Г., Садовский М.Г. Избыточность генов уменьшается в результате сплайсинга // Мол.биология, 1995, т.29, № 3, с.500 506.

43. Попова Т.Г., Садовский М.Г. Интроны отличаются от экзонов по своей избыточности//Генетика, 1995, т.31, № 10, с.1365 1369.

44. Ратнер В.А. Генетический язык: грамматика, семантика, эволюционное положение // Генетика, 1993, т.29, с.709 719.

45. Ратнер В.А. Молекулярно-генетические системы управления. // Новосибирск: Наука, 1975. —472 с.

46. Садовский М.Г. К вопросу об избыточности геномов вирусов и прокариот // Генетика, 2002, т. 38, № 5 с. 695 701.

47. Садовский М.Г. Сравнение нуклеотидных и аминокислотных последовательностей по их частотным словарям // 5 Межд.конференция "Математика, компьютер, образование". Дубна, 29-31 янв. 1998. Сб.тезисов. с. 178.

48. Садовский М.Г., Хопёрская E.H. О статистике решёток: мозаики и энтропия // 5 Межд.конференция "Математика, компьютер, образование". Дубна, 29-31 янв. 1998. Сб.тезисов. с.215.

49. Селедцов И.А., Вульф Ю.И., Макарова К.С. Множественное выравнивание последовательностей биополимеров, основанное на поиске статистически значимых общих участков // Мол.биология, 1995, т.29, № 5, с. 1023 1039.

50. Уотсон Дж., Крик Ф. Молекулярная биология гена // М.: Мир, 1990. 783 с.

51. Чупахина О.М. Сложностный анализ генетических текстов. // Автореф. . канд. техн.наук, Новосибирск, НИОХ, 1993, 18 с.

52. Чураев Р.Н. О хранении, кодировании, передаче и переработке наследственной информации живых системах // Вычислит.технологии, 2000, т.5, № 2, с.100 111.

53. Чураев Р.Н. Прикладные аспекты концепции эпигенов // ЖОБ, 1982, т.43, вып. 1, с.82-87.

54. Чураев Р.Н., Ратнер В.А. Моделирование оперонных систем на языке теории автоматов // Генетика, 1973, т.9, № 2, с. 173 174.

55. Шлегель Г. Общая микробиология. // М.: Мир, 1987, 566 с.

56. Шредингер Э. Что такое жизнь. С точки зрения физика. // М.: Физматгиз, 1948,235 с.

57. Юшманов С.В. Восстановление биологической эволюции. Построение филогенетических деревьев // Мат.вопросы кибернетики. Вып.З. М.: Наука, 1991. с.51 76.

58. Яглом А.А., Яглом И.А. Вероятность и информация. // М.: Наука, 1976. — 267 с.

59. Adler P. Comments on Figure of Merit for Communication Devices // Proc. IRE, 1954, vol.42, p.l 191.

60. Aissani В., D'Onofrio G., Mouchiroud D., Gardiner K., Gauticr C., Bemardi G. The compositional properties of human genes location // J.Mol.Evol., 1991, vol.32, pp.493 503.

61. Aissani В., Bernardi G. CpG islands: Features and distribution in the genomes of vertebrates location // Gene, 1991, vol.106, pp.173 183.

62. Allegrini P., Buiatti M., Grigolini P., West B.J. Fractional Brownian motion as a nonstat-ionary process: An alternative paradigm for DNA sequences // Physical Review E, 1998, vol.57, №4, pp.4558-4567.

63. Almeida J.S., Vinga S. Universal sequence map (USM) or arbitrary discrete sequences // BMC Bioinformatics, 2002, vol.3, pp.6 12.

64. Arneodo A., Bacry E., Muzy J.F. Characterizing long-range correlations in DNA sequences from wavelet analysis // Phys.Rev.Lett., 1995, vol.74, pp.3293 3296.

65. Biol., 1990, vol.52, pp.741 772.

66. Arques D.G., Michel C.J. Periodicities in introns location // Nucl.Acids Res., 1987, vol.15, pp.7581 -7592.

67. Atlan, H. L'organisation biologique et la theorie de Information// Paris: Hermann, 1992. — 421 p.m 70. Audic S., Claverie J.-M. Self-idetification of protein-coding regions in microbial genomes

68. Proc.Natl.Acad.Sci.- USA., 1998, vol.95, pp.10026 10031.

69. Azbel M.Y. Universality in a DNA statistical structure // Phys.Rev.Lett., 1995, vol.75, pp.168- 171.

70. Bai-Lin Hao Fractals from genomes — exact solutions of a biology-inspired problem // Physica A, 2000, vol.282, pp.225 246.

71. Beckmann J.S., Brendel V., Trifonov E.N. Intervening sequences exhibit distinct vocabulary location // J.Biomol.Struct.Dynamics, 1986, vol.4, pp.391 400.

72. Bell G.I., Torney D.C. Repetitive DNA sequences: some considerations for simple sequence repeats// Comput.Chemistry, 1993, vol.17, pp.185 190.

73. Bernaola-Galvän P., Grosse I., Carpena P., Oliver J.L., Romän-Roldän R., Stanley H.E. Finding Borders between Coding and Noncoding DNA Regions by an Entropie Segmentation Method // Phys.Rev.Letters, 2000, vol.85, № 6, pp.1342 1345.

74. Blaisdcll B.E. Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eukaryotic nuclear DNA sequence protein-coding and non-coding // Mol.Evolution, 1985, vol.21, pp.278 288.

75. Bork P, Dandekar T, Diaz-Lazcoz Y, Eisenhaber F, Huynen M, Yuan Y. Predicting function: from genes to genomes and back // J.Mol.Biology, 1998, vol.283, № 4, pp.707 725.

76. Bork P. Go hunting in sequence databases but watch out for the traps location // Trends in

77. Genetics, 1996. vol. 12, pp.425 427.

78. Borovik A.S., Grosberg A.Y., Frank-Kamenetskii M.D. Fractality of DNA texts // J.Biomol.Struct.Dynamics, 1995, vol.12, pp.655 669.

79. Borstnik B., Pumpernik D., Lukman D., Ugarkovic D., Plohl M. Tandemly repeated pen-tanucleotides in DNA sequences of eucaryotes // Nucleic Acids Res., 1994, vol.22, pp.3412-3417.

80. Brendel V., Hamm G.H., Trifonov E.N Linguistics of nucleotide sequences: morphology and comparison of vocabularies location // J.Biomol.Struct. Dynamics, 1986, vol.4, pp.11 -21.

81. Bugaenko N.N., Gorban A.N., Sadovsky M.G. Maximum entropy method in analysis of genetic text and measurement of its information content // Open System & Information Dynamics, 1998, vol.5, № 3, pp.265 278.

82. Buldyrev S.V., A.L.Goldberger, S.Havlin, C.-K.Peng, H.E.Stanley, M.H.R.Stanley, M.Simons Fractal Landscapes and Molecular Evolution: Modelling the Myosin Heavy Chain Gene Family // The Biophysical Journal, 1993, vol.65, № 6, pp.2673 2679.

83. Buldyrev S.V., Goldberger A.L., Havlin S., PengC.-K., Simons M., Stanley H.E. Generalized Levy-walk model for DNA nucleotide sequences location // Phys.Review E, 1993, vol.47, pp.4514-4523.

84. Busscmaker H.J., Hao Li, Siggia E.D. Building a dictionary for genomes: Identification of presumptive regulatory sites by statistical analysis // PNAS Early Edition, www.pnas.org

85. Carrillo H., Lipman D.J. The multiple sequence alignment problem in biology // SIAM J.Appl.Math., 1988, vol.48, pp.1073 1082.

86. Cebrata S., Dudek M.R., Gierlika A., Kowalczuka M., Mackiewicza P. Effect of replication on the third base of codons // Physica A, 1999, vol.265, pp.78 84.

87. Chaitin G.L. Algorithmic information theory// Camb.Univ.Press, Cambridge, 1987, 477 p.

88. Chechetkin V.R., Turygin A.Y. Search of hidden periodicities in DNA sequences // J. Theor. Biol., 1995, vol. 175, pp.477 494.

89. Chechetkin V.R., Turygin A.Y. Study of correlation in DNA sequences // J. Theor. Biol., 1996, vol.178, pp.205-217.

90. Cho G. Doolittle R.F. Intron Distribution in Ancient Paralogs Supports Random Insertion and Not Random Loss. // J.Mol.Evolution, 1997, vol.44, p. 573.

91. Churchill G.A. Hidden Markov chains and the analysis of genome structure // Comput. Chemistry, 1992, vol.16, pp.107 115.

92. Churchill G.A. Stochastic models for heterogeneous DNA sequeces // Bull. Math. Biol., 1989, vol.51, pp.70-94.

93. Chvatal V., SankoffD. Longest common subsequences of two random sequences // J.Appl.Probability, 1975, vol.12, pp.306 315.

94. Coifman R.R., Wickerhauser M.V. Entropy-Based Algorithms for Best Basis Selection // IEEE Trans.Inform.Theory, 1992, vol.38, № 2, pp.1713 1716.

95. Computing with biological metaphors Edited by Ray Paton. // London; New York: Chapman & Hall, 1994. 452 p.

96. Deken T.G. Some limit results for largest common subsequences // Discrete Mathematics, 1979, vol.26, № 1, pp.17-31.

97. Durbin R., Eddy S.R., Krough A., Mitchison G. Biological sequence analysis: probabilistic models of protein and nucleic acids // Cambridge University Press, 1998, 462 p.

98. Duret L., Mouchiroud D. Expression pattern and, surprisingly, gene length shape codon usage in Caenorhabditi's, Drosophila, and Arabidopsis II Proc.Natl.Acad.Sci. USA, 1999, vol. 96, № 8, pp. 4482 4487.

99. Entropy, information, and evolution: new perspectives on physical and biological evol-. ution (ed. by B.H.Weber, D.J.Depew, J.D.Smith. // Cambridge, Mass.: MIT Press, 1988.487 p.

100. Eriksson K.-E., Lindgren K., Mansson B.A. Structure, context, complexity, organization: physical aspects of information and value // Singapore, N.J.: World Scientific, 1987. — 325 p.

101. Finkelstein A.V., Roytberg M.A. Computation of biopolymers: a general approach to different problems // BioSystems, 1993, vol.30, pp.33 46.

102. Frappat L., Sorba P., Sciarrino A. A crystal base for the genetic code // Physics Letters A, 1998, vol.250, pp.214-221.

103. Gatlin L.L. Information Theory and the Living System // New York: Columbia University Press, 1972.

104. Gatlin L.L. The information content of DNA//J.Theor.BioL, 1966, vol.10, pp.281 300.

105. Gelfand M.S. Computer functional analysis of nucleotide sequences: problems and approaches // Mathematical methods of the analysis of biopolymer sequences (DIMACS, vol. 8) (S.G.Gindikin, ed) (AMS, Providence RI, 1992), pp.19 61.

106. Gelfand M.S. Prediction of function in DNA sequence analysis // J.Comput.Biology, 1995, vol.2., pp.87-115.

107. Gelfand M.S., Kozhukhin C.G., Pevzner P.A. Extendable words in nucleotide sequences location //Comput.Appl. Bioscience, 1992, vol.8, pp.129 135.

108. Gelfand M.S., Roytberg M.A. A dynamic programming algorithm for prediction of the exon-intron structure H BioSystems, 1993, vol.30, pp.78 91.

109. Gilbert W., Glynias M. On the ancient nature of introns // Gene, 1993, vol.135, pp.137 -144.

110. Gorbalenya A.E. Non-canonical inteis // Nucleic. Acids Research., 1998, vol.26, № 7, pp.1741 1748.

111. Gorban A.N., Popova T.G., Sadovsky M.G. Classification of symbol sequences over thier frequency dictionaries: towards the connection between structure and natural taxonomy // Open Systems & Information Dynamics, 2000, v.7, № 1, pp.1 17.

112. Große I, Buldyrev SV, Stanley HE, Holste D, Herzel H. Average mutual information of coding and noncoding DNA. // Pac.Symp.Biocomput., 2000, pp.614 623.

113. Guibas L.J., Odlyzko A.M. Periods in strings location // J.Combin. Theory, Ser. A, 1981, vol.30, pp.19-42.

114. Gusev V.D., Kulichkov V.A., Chupakhina O.M. Genome Complexity Analysis 1: Complexity Measures and the Classification of Structural Features // Molecular Biology, 1991, vol.25, pp.669 677.

115. Hayes W.S., BorodovskyM. How to Interpret an Anonymous Bacterial Genome: Machine Learning Approach to Gene Identification // Genome Research, 1998, vol.8, pp.1154 1171.

116. Herzel H., Trifonov E.N., Weiss O., Große I. Interpreting correlations in biosequences // Physica A, 1998, vol.249, pp.449 459.

117. Hirshleifer C., Riley J.G. The analytics of uncertainty and information // Cambridge, New York: Cambridge University Press, 1992. — 502 p.

118. Huijie Yang, Fangcui Zhao, Yizhong Zhuo, Xizhen Wu, Zhuxia Li Analysis of DNAchains by means of factorial moments // Physics Letters A, 2002, vol.292, pp.349 356.

119. Jimenez-Montano M.A., Ebeling W., Pohl Th., Rapp P.E. Entropy and complexity of finite sequences as fluctuating quantities // BioSystems, 2002, vol.64, pp.23 32.

120. Jurka J., Pethiyadoga Ch. Simple repititive DNA sequences from primates: Compliation and analysis // J.Mol.Evolution, 1995, vol.40, № 2, pp.120 126.

121. Kalogeropoulos A. Automatic intron detection in nuclear DNA sequences of Sacchamromyces cerevisiae II Yeast, 1995, vol.11, pp.555 565.

122. Karlin S., Cardon L.R. Computational DNA Sequence Analysis // Ann.Rev. of Microbiology, 1994, vol.48, pp.619-654.

123. Kelley L.A., MacCallum R.M., Sternberg M.J. Enhanced genome annotation using structural profiles in the program 3D-PSSM. // J.Mol.Biology, 2000, vol.299, pp.499 520.

124. Kirkwood, J. and Boggs, E. The radial distribution function in liquids // J.Chem. Physics, 1942, vol.10, №6, p.394.

125. Kirsanova E.N., Sadovsky M.G. Entropy approach to a comparison of images // Open System & Information Dynamics, 2001, vol.8, № 2, pp.183 199.

126. Konopka A.K. Sequences and Codes: Foundamentals of Biomolecular Cryprology // In: Biocomputings: Informatics and Genome Projects (D.Smith, Ed.) Acad.Press, San Diego, p. 119-174.

127. Konopka A.K. Theoretical Molecular Biology // In: Molecular Biology and Biotechnology, (R.A.Meyers, Ed.) (1995). VCH Publishers, Weinheim, p.888 896.

128. Korotkov E.V., Korotkova M.A. Enlarged similarity of nucleic acid sequences // DNA Research, 1996, vol.3, p. 157 163.

129. Korotkov E.V., Korotkova M.A. Latent sequence periodicity of some oncogenes and DNA binding protein genes // CABIOS, 1997, vol.13, pp.37 44.

130. Krogh A., Mian I.S., Haussler D. A hidden Markov model that finds genes in E. coli DNA // Nucleic Acids Res., 1994, vol.22, pp. 4768 4778.

131. Kruskal J.B. An overview of sequence copmparison // SIAM Review, 1983, vol.25, issue 2, pp.201 -237.

132. Kullback S. Information theory and statistics //New York, Weley, 1959, 467 p.

133. Lempel A., Ziv J. On the Complexity of Finite Sequences // IEEE Trans.of Inf. Theory, 1976, vol.IT-22, issue 1, pp.75 81.

134. Mamonova M.A., Sadovsky M.G. An inner structure in genomes is revealed by the unexpectedly frequent or unexpectedly rare strings // Open System & Information Dynamics, 2003, in press.

135. Mani G.S. Correlation between coding and non-coding regions of DNA sequences // J.Theor.Biol., 1992, vol. 158, pp.429 445.

136. Mantegna R.N., Buldyrev S.V., Goldberg A.L., Havlin S., Pen C.-K., Simons M., Stanley H.E. Linguistics features of non-coding DNA sequences // Pys.Rev.Letters, 1994, vol. 73, №23, pp.3169-3172.

137. Margalef R. Information and uncertainty in living systems, a view from ecology. // Biosystems, 1996, vol.38, pp.141 146.

138. Mengeritsky G., Smith T.F. Recognition of characteristic patterns in sets of functionally equivalent DNA sequences location // Comput.Appl. Bioscience, 1987, vol.3, pp.223 -227.

139. Nature, vol.387, issue 6632S, Supplement issue.

140. Nicolas P., Bize L., Muri F., Hoebeke M., Rodolphe F., Erlich S.D., Prum В., Bessieres P. Mining Bacillus subtillis genome heterogeneity using hidden Markov models // Nucleic Acids Res., 2002, vol.30, № 6, pp.1418 1426.

141. Oiwa N.N., Glazier J.A. The fractal structure of the mitochondrial genomes // Physica A, 2002, vol.311, pp.221 -230.

142. Orlov Yu.N., Potapov V.N. Estimation of stochastic complexity of genetical texts // Вы-числ. технологии, 2000, т.5, № 2, c.5 15.

143. Ossadnik S.M., Buldyrev S.V., Goldberger A.L., Havlin S., Mantegna R.N., Peng C.K., Simons M., Stanley H.E. Correlation approach to identify coding regions in DNAv sequences.//Biophys.J., 1994, vol.67, pp.64 70.

144. Pevzner P.A. Nucleotide sequences versus Markov models location // Abstr. of Workshop on Open Problems of Computational Molecular Biology (Telluride, Colorado, June 2-8, 1991), pp.50-54.

145. Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: local redundancy displays a new structure of genes // Advances in Modelling & Analysis, ser. C, 1995, AMSE Press, vol.48, № 4, pp.17 22.

146. Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: new method to compare two genes // Modelling, Measurement & Control, ser. C, 1994, AMSE

147. Press, vol.45, №4, pp.27-36.

148. Popova T.G., Sadovsky M.G. The new measure of relationship between two symbolic sequences // Advances in Modelling & Analysis, ser. A, 1994, AMSE Press, vol.22, № 2, p.13-17.

149. Popova T.G., Mirkes E.M., Sadovsky M.G. Investigating Statistical Properties of Genetic Texts: A New Approach // Advances in Modelling & Analysis, ser. B, AMSE Press, 1993, vol.27, № 2, p.l-13.

150. Provata A. Random aggregation models for the formation and evolution of coding and non-coding DNA // Physica A, 1999, vol.264, pp.570 580.

151. Radice A.R., Bugaj B., Fitch D.H.A., Emmons S.W. Widespread occurence of the Tel transposon family: Tel-like transposons from teleost fish // Mol.Gen. Genetics, 1994, v.244, pp.606 -612.

152. Rosen R. Bionics Revisited // In: The Machine as Metaphor and Tool (Eds. H.Haken, A.Karlquist, U.Svedin) Springer-Verlag, Berlin: 1993, pp.87 100.

153. Roytberg M.A. Fast algorithm for optimal aligning of symbol sequences // Mathematical methods of the analysis of biopolymer sequences (S.Gindikin, ed.), AMS, Providence, 1992, p.103-117.

154. Roytberg M.A., Podolsky L.I., Gelfand M.S. Prediction of the exon-intron structure by the vector dynamic programming approach // International Congress on Computer Systems and Applied Mathematics CSAM'93 (St.Petersburg, Russia, July 1993), p. 163.

155. Roytberg M.A. Similarity search in two biological sequences // Proc.of the Conf. "Modeling and computer methods in molecular biology and genetics", Novosibirsk, 1990,pp.7-8.

156. Sadovsky M.G. Comparison of Symbol Sequences: No Editing, No Alignment // Open Systems & Information Dynamics, 2002, v.9, № 1, pp.19 36.

157. Sadovsky M.G. Information capacity of symbol sequences // Open Systems & Information Dynamics, 2002, v.9, № 1, pp.37 49.

158. Sadovsky M.G. The method of comparison of nucleotide sequences based on the minimum entropy principle // Bulletine of Mathematical Biology, 2003, vol.65, pp. 309 -322.

159. Sankoff D. Edit distance for genome comparison based on non-local operations: Combin. Pattern Match, 3rd Ann.Symp., Tucson, Ariz., Apr. May 1992 // Lect. Notes Comput. Sci., 1992, vol.644, pp.121 - 135.

160. Schmitt A.O., Herzel H. Estimating the entropy of DNA sequences // J.Theor. Biol., 1997, vol.188, pp.369-377.

161. Shannon C.E., Weaver W. The Mathematical Theory of Communication // Urbana, Illinois: University of Illinois Press, 1949,429 p.

162. Sharp Ph. A. Split genes and RNA splicing // Cell, 1994, vol.77, № 6. pp. 805 815.

163. Smith T.F. Genetic sequence semantic and syntactic patterns location // Computers and DNA (Bell G.I.; Marr T.G., editors), Addison-Wesley, 1990, pp.259 270.

164. Solovyev V.V., Salamov A.A., Lowrence C.B. Predicting internal exons by oligonucleotide composition and discriminant analysis of spliciable open reading frames // Nucleic Acids Res., 1994, vol.22, pp.5156 5163.

165. Ting S.J.Y. A binary model of repetitive DNA sequence location // DNA Cell. Biology, 1995, vol.14, pp.83-85.

166. Trifonov E.N. Nucleotide sequences as a language: morphological classes of words location / Classification and Related Methods of Data Analysis (H.H.Bock, Ed.) // Elsevier, 1987, pp.57-64.

167. Trifonov E.N., Brendel V. Gnomic, A Dictionary of Genetic Codes location // Balaban Publishers, Philadelphia, 1986, —421 p.

168. Turbeville J., Schulz J.R., Raff R.A. Deuleroslome phytogeny and the sister group of the chordates: evidence from molecules and morphology // Mol.Biol. Evolution, 1994, vol.11, pp.648-655.

169. Upton C., Hogg D., Perrin D., Boone M., Harris N.L. Viral genome organizer: a system for analyzing complete viral genomes. // Virus Res., 2000, vol.70, pp.55 64.

170. Usuka J., Brendel V. Gene structure prediction by spliced alignment of genomic DNA with protein sequences: increased accuracy by differential splice site scoring. // J.Mol. Biology, 2000, vol.297, pp. 1075 1085.

171. Vitushkin A.G. Theory of transmission and processing of information // Pargamon Press, N.Y., 1962,-467 p.

172. West B.J., Bickel D.R. Molecular evolution modeled as a fractal stochastic process // Physica A, 1998, vol.249, pp.544 552.

173. Wicken J.S. Evolution, thermodynamics & information: extending the Darwinianprogram // New York: Oxford University Press, 1987. — 572 p.

174. Yeramian E. The physics of DNA and the annotation of the Plasmodium falciparum ^ genome. // Gene, 2000, vol.255, № 2, pp. 151 168.

175. Yockey H.P. Information Theory and Molecular Biology // Cambridge Univ.Press, N.Y., 1992. —354 p.

176. Yoshida T., Obata N., Oosawa K. Color-coding reveals tandem repeats in the Escherichia coli genome. // J.Mol. Biology, 2000, vol.298, № 3, pp.343 349.

177. Yu Shi, Ido Kanter, David Kessler, Distributions of triplets in genetic sequences // Physica A, 1998, vol.252, pp.48 60.

178. Yarus M., Folley L.S. Sense codons are found in specific context // J.Mol. Biology, 1985,vol. 182, pp.529-540.

179. Zeigarnik A.V., Temkin O.N. A graph-theoretic model of complex reaction mechanisms: a new complexity index for reaction mechanisms // Kinetics and Catalysis, 1996, vol.37, pp.372-385.

180. Zu-Guo Yu, Vo Anh Time series model based on global structure of complete genome //H

181. Chaos, Solitons and Fractals, 2001, vol. 12, pp. 1827- 1834.

182. Zu-Guo Yua, Vo An, Ka-Sing Lau Multifractal characterisation of length sequences of coding and noncoding segments in a complete genome // Physica A, 2001, vol.301, pp.351 -361.

183. Zurek W.H. Algorithmic Information Content, Church-Turing Thesis, Physical Entropy, and Maxwell's Demon, in Complexity, Entropy and the Physics of Information, // Eds.Zurek W. II., Addison-Wesley, Redwood City, California, 1990, pp.73 89.

184. Zurek W.H. Algorithmic Randomness and Physical Entropy // Physical Review A, 1989, vol.40, pp.4731 -4751.