Содержание к диссертации
Введение
Глава 1 . Обзор основных проблем биоинформатики и анализа символьных последовательностей 13
1.1. Основные задачи в исследованиях символьных последовательностей 13
1.2. Проблема аннотирования геномов 15
1.3. Модели генетических текстов 17
1.4. Построение словарей генетических текстов 20
1.5. Распознавание структурных закономерностей в генетических текстах 22
1.6. Методы сравнения генетических текстов 27
1.7. Информация и энтропия 32
1.8. Выводы Главы 1 37
Глава 2. Частотный словарь. Случай глобального восстановления. 38
2.1. Соотношение "последовательность - конечно-частотный словарь" и проблема восстановления целого из частей 38
2.2. Конечно-частотный словарь и проблема восстановления полной последовательности 39
2.3. Характеристики конечно-частотных словарей для реальных нуклеотидных последовательностей 41
2.4. Изменение избыточности генов в результате сплайсинга 52
2.5. О распределении наидлиннейших повторов в различных участках последовательности 76
2.6. О распределении наидлиннейших повторов в геномах некоторых организмов 85
2.7. Выводы Главы 2 97
Глава 3. Частотный словарь. Случай локального восстановления 98
3.1. Задача локального восстановления. Гипотеза наиболее вероятного продолжения 98
3.2. Принцип максимума энтропии частотного словаря и восстановление частотных словарей большей толщины по заданному 99
3.3. Локальное востановление частотных словарей и проблема выбора статистической модели генетического текста 102
3.4. Информационное содержание частотных словарей 105
3.5. Предельная энтропия, удельная энтропия и качество восстановления частотных словарей 112
3.6. Качество восстановления для некоторых реальных символьных последовательностей 116
3.7. Отличия реальных и восстановленных частотных словарей некоторых генетических текстов 119
3.8. Сравнительное исследование информационных свойств генов вирусов и генов их хозяев 139
3.9. Информационная ёмкость некоторых геномов 164
3.10. Микроинформационная структура генов и геномов 169
3.11. Самоподобие геномов 199
3.12. Выводы Главы 3 225
Глава 4. Распределение информационно значимых слов в геномах 227
4.1. Поиск и выделение информационно значимых сайтов в символьных последовательностях 228
4.2. Поиск и выделение информационно значимых сайтов в некоторых биологических последовательностях 231
4.3. Поиск и выделение информационно значимых сайтов в геномах 239
4.4. Информационно значимые сайты функционально различных частей в геномах 255
4.5. Связь между информационно значимыми сайтами различной длины в геномах 258
4.6. О связи структуры и функции в геномах: статистическая семантика геномов 274
4.7. Выводы Главы 4 278
Глава 5. Информационные и статистические подходы к определению близости символьных последовательностей 280
5.1. Сравнение символьных последовательностей по носителям их конечно-частотных словарей 282
5.2. Сравнение генетических текстов по носителям их конечно-частотных словарей 287
5.3. Сравнение символьных последовательностей по их конечно частотным словарям 290
5.4. Сравнение нескольких символьных последовательностей с помощью их конечно-частотных словарей 292
5.5. Сравнение символьных последовательностей по их частотным словарям 294
5.6. Сравнение генетических текстов по их частотным словарям 302
5.7. Сравнение геномов по наборам их информационно значимых слов 350
5.8. Сравнение функционально различных частей генома по наборам их информационно значимых слов 362
5.9. Выводы Главы 5 369
Заключение 371
Выводы 377
Список литературы 380
- Распознавание структурных закономерностей в генетических текстах
- Конечно-частотный словарь и проблема восстановления полной последовательности
- Принцип максимума энтропии частотного словаря и восстановление частотных словарей большей толщины по заданному
- Поиск и выделение информационно значимых сайтов в некоторых биологических последовательностях
Введение к работе
Символьные последовательности являются классическим объектом математики, а также встречаются как предмет изучения во многих прикладных задачах — от теоретического программирования и теории управления до биологии и лингвистики. Изучение символьных последовательностей позволяет ответить на множество сопряжённых друг с другом вопросов из различных областей науки, смежных с чистой или прикладной математикой. Как объект прикладного исследования символьные последовательности возникают во всех областях, где рассмотриваются те или иные объекты, состоящие из большого числа одинаковых фрагментов. При этом одинаковость (подобие, тождество) может носить искусственный — до определённой степени — характер. Связано это с тем, что именно исследователь по своему усмотрению начинает рассматривать некоторые фрагменты целого — например, нуклеотиды в молекуле нуклеиновой кислоты или символы в текстах того или иного естественного языка, записанные в алфавитной системе записи — как тождественные друг другу, не отличающиеся ничем, кроме своего положения в рассматриваемом объекте — в символьной последовательности.
Биологические макромолекулы играют ключевую роль во многих процессах, протекающих в живых организмах. С момента установления Дж.Уотсоном и Ф.Криком первичной структуры нуклеиновых кислот не прекращается поток исследований, посвященных выяснению роли и места информации, содержащейся в этих молекулах. Изучение структуры, а также функциональных, химических, физико-химических и проч. свойств нуклеиновых кислот активно ведется специалистами в различных областях, и одним из важных направлений является изучение нуклеиновых кислот как символьных последовательностей. В настоящей работе предполагается исследовать лишь те свойства нуклеиновых кислот, которые определяются только взаимным расположением нуклеотидов друг относительно друга в одной изучаемой молекуле; никакие другие факторы — физико-химическое окружение, особенности состава нуклеотидов и т.п. — не рассматриваются.
Особый круг исследований составляют работы, посвященные изучению информационных свойств символьных последовательностей. Получаемые в этих исследованиях теоретические результаты оказываются весьма полезными и эвристически ценными во многих смежных и даже отдалённых областях. Однако в самих исследованиях информационных свойств символьных последовательностей существует определённое
-6 смешение таких существенно различных понятий, как собственно понятие информации и семантическое наполнение того объекта, информационные характеристики которого являются предметом изучения. Такого рода смешение приводит к возникновению новых, искусственных понятий, например, понятия ценности информации и проч.
Само понятие информации связано с изучением внешней формы представления того или иного сообщения; при этом такое сообщение должно быть представлено как последовательность однотипных объектов (например, букв в текстах из естественных языков, либо последовательности нулей и единиц в программах для ЭВМ и т.п.). Понятие информации в первую очередь связано с формой представления, а связь с её содержанием (смыслом) исследуется в таких задачах лишь в той мере, в какой это необходимо для прояснения свойств формы представления информации. Настоящая работа посвящена исследованию этого первого аспекта в свойствах символьных последовательностей.
Как хранение, так и реализация какой-либо информации напрямую.обусловлены тем обстоятельством, что в ходе этих процессов актуальную роль играют символьные последовательности. При это\г хорошо известно, что в природе фактически нет процессов, связанных с переработкой либо реализацией той или иной информации, которые бы вовлекали всю такого рода символьную последовательность целиком: чтение и обработка файлов вычислительными машинами происходит малыми порциями (байтами) и последовательно, чтение и переработка письменной информации человеком происходит малыми порциями (словами, либо абзацами) и последовательно, чтение и переработка наследственной информации в биологических системах происходит малыми порциями (кодонами) и последовательно. Это простое обстоятельство, тем не менее, имеет важные последствия. Оно требует перехода от рассмотрения всей символьной последовательности в целом к рассмотрению набора её фрагментов.
Выделение таких фрагментов может быть сделано многими разными способами, даже в пределах одной предметной области и даже одной задачи. Конкретный способ выделения фрагментов определяется целями и задачами того или иного конкретного исследования. Одна из важнейших задач, возникающая при работе с наборами фрагментов исходной символьной последовательности — это задача восстановления полной последовательности по набору её фрагментов; например, такого рода задачи всегда возникают в исследованиях по атрибуции авторства текста, а также в задачах по гибри-дизационному секвенированию нуклеотидных последовательностей. При этом следует отметить, что сама по себе проблема восстановления целого из частей — в нашем слу -7 чае это проблема восстановления последовательности по набору её фрагментов — разбивается на два отдельных вопроса. Первым является вопрос о принципиальных ограничениях на возможность восстановления всей символьной последовательности по максимально полному набору её фрагментов; вторым является вопрос о восстановлении последовательности по неполному набору фрагментов. Этот второй вопрос имеет существенное прикладное значение, поскольку в его рамках можно вести речь об анализе и изучении несвязных символьных последовательностей — иными словами, об извлечении информации из данных с пробелами. Более формально такая конструкция, с помощью которой изучаются статистические и информационные характеристики символьных последовательностей, называется частотным словарём (толщины q). Частотный словарь толщины q — это набор всех связных подпоследовательностей длины q, встречающихся в данной последовательности с указанием их частот, то есть нормированный на единицу. Частотный словарь соответствует не единственному тексту, а их ансамблю. Сам по себе частотный словарь также может быть построен по-разному: он может содержать всю доступную информацию о фрагментах (то есть, все встречающиеся фрагменты могут быть включены в частотный словарь), а может содержать лишь часть доступной информации. Разные постановки требуют использования различных частотных словарей, однако в нашей работе мы систематически будем использовать первую конструкцию — частотный словарь, содержащий все встречающиеся в последовательности фрагменты.
Другая важная проблема, имеющая общую значимость для любых прикладных исследований, предметом которых являются те или иные символьные последовательности, состоит в сравнении двух (или нескольких) символьных последовательностей. Дело в том, что символьные последовательности относятся к такому классу объектов, для которых определение расстояния между ними возможно, однако оно очень "бедно": очень часто формально введённое расстояние никак не отражает близость или, наоборот, существенные различия свойств, приписываемых исследователем изучаемым символьным последовательностям. Здесь имеет смысл рассматривать меру близости двух (или нескольких) последовательностей, и для её построения информационные и статистические методы являются весьма универсальными и продуктивными.
Наконец, нельзя не сказать о том, что все или почти все результаты, полученные для символьных последовательностей, могут быть распространены на более сложные дискретные объекты — например, на цифровые (растровые) изображения; сим -8 вольные последовательности, являясь существенно более простым объектом, представляют собой своеобразный полигон для развития методов и предсказания наиболее общих результатов об информационных свойствах различных дискретных объектов.
Цель работы состоит в разработке подходов для исследования тех свойств символьных последовательностей различной природы, которые определяются только их информационными и статистическими характеристиками: проблемы локального восстановления частотных словарей большего размера по заданным, проблемы определения меры близости двух или нескольких последовательностей по их информационным характеристикам, проблемы сравнения реального частотного словаря символьной последовательности и того, который может быть построен по набору слов меньшей длины исходя из гипотезы о наиболее вероятном продолжении, а также проблемы соотношения между фрагментами символьной последовательности с высоким информационным содержанием и функциональной ролью тех регионов последовательности, которые такие фрагменты содержат (поиск и описание информационно значимых слов), а также в систематическом изучении информационных и статистических свойств нуклео-тидных последовательностей.
Научная новизна работы заключается в следующем.
1. Изучены некоторые типичные свойства нуклеотидных последовательностей, проявляющиеся в характеристиках конечно-частотных словарей. На основе этих характеристик построеное новое определение избыточности последовательностей. Показано, что функционально разные части генов эукариотических организмов различаются по этому показателю и сплайсинг генов ведёт к уменьшению их избыточности.
2. Впервые изучены некоторые типичные свойства нуклеотидных последовательностей, проявляющиеся в характеристиках восстановления частотных словарей, состоящих из слов большей длины по словарям заданной толщины (длины слов). Введено понятие информационной ёмкости частотного словаря и изучено её поведение у различных нуклеотидные последовательностей. На основе введённых характеристик исследована микроинформационная структура некоторых генов и геномов, т.е. структура, определяемая различием информационных и статистических свойств двух соседних участков символьной последовательности.
3. Впервые введено строгое определение информационно значимых сайтов нуклеотидной последовательности и развит новый метод выделения таких сайтов. Проанализированы различные семейства геномов с точки зрения выявления в них информационно значимых сайтов. Впервые для информационно значимых слов длины 3 и -9 показано существование специфических наборов, общих для семейства геномов родственных организмов; также впервые проанализирован набор информационно значимых слов длины 3 и 4, характерных для кодирующих и некодирующих областей генома. Показано, что существуют информационно значимые слова этой длины, специфичные для указанных областей.
4. Впервые для информационно значимых сайтов длины 7 и 8 нуклеотидов, характеризующихся высокой информационной значимостью всех входящих в них слов меньшей длины показана неслучайность распределения таких сайтов вдоль по геному: информационно значимые сайты длиной 7 и 8 нуклеотидов встречаются, как правило, в регуляторных областях геномов, причём наблюдается также неравновесность при распределении по регуляторным областям различной природы.
5. Развиты принципиально новые методы сравнения символьных последовательностей, не использующие идею выравнивания. Сравнение символьных последовательностей производится по их частотным либо конечно-частотным словарям, при этом в первом случае для группы сравниваемых последовательностей строится их статистический предок — искусственный частотный словарь, из которого может быть получен любой из сравниваемых, причём для этого из статистического предка потребуется удалить (либо добавить) лишь необходимый минимум информации. Сравнение символьных последовательностей с помощью конечно-частотных словарей позволяет указать меру близости последовательностей в группе, никак не упорядочивая их внутри неё.
6. Предложен новый метод сравнения символьных последовательностей на ос-. нове сравнения наборов их информационно значимых слов различной длины. Показано, что для некоторых миркоорганизмов вариабельность генома, определяемая по такому показателю близости, превосходит вариабельность, наблюдаемую при сравнении отдельных хромосом различных геномов, на основе сравнения наборов информационно значимых сайтов длины 3 и 4 введена мера внутригеномного разнообразия.
Практическая ценность работы заключается в:
1) изучении статистических свойств символьных последовательностей, соответствующих конкретным генам различных организмов;
2) развитии новых методов исследования информационной ёмкости символьных последовательностей;
3) развитии новых методов исследования информационной значимости малых фрагментов символьных последовательностей, на основе которых возможна грубая разметка не аннотированного генома;
-10 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 г., на П-ом Съезде биофизиков России, Москва, 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 E.M., Popova T.G., 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; Горбанъ А.Н., Попова Т.Г, Садовский М.Г
-11 Избыточность генетических текстов и мозаичная структура генома // Мол.биология (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; Горбань А.Н., Попова Т.Г., Садовский М.Г. Корреляционный подход к сравнению нуклеотидных последовательностей // ЖОБ (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 AM, 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; Кирсанова Е.Н., Садовский М.Г. Метод статистического сравнения объектов // "Радиоэлектроника. Информатика. Управление." № 2, 2000, стр. 71 - 82; Кирсанова Е.Н., Садовский М.Г. Об информационной значимости цифровых изображений // "Радиоэлектроника. Информатика. Управ -12 ление." № 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, № 1, 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.l 1 - 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.
Работа выполнена в лаборатории экологической биотехнологии Институт биофизики СО РАН. Результаты, полученные в ходе работы были получены при поддержке Красноярского научного фонда, гранты 1F0390, 3F0190, 4F0153, 5F0012 и 11F114C.
Глава 1. Обзор основных проблем биоинформатики и анализа символьных последовательностей
Символьные последовательности как объект исследований встречаются в различных разделах математики и естествознания. При этом основной успех в теоретических исследованиях свойств символьных последовательностей самого разного направления фактически всегда был обусловлен возникновением соответствующих прикладных задач. Одной из таких задач, имеющих различные сферы приложения, является изучение тех свойств символьных последовательностей, которые могут оказаться информативными при исследованиях их функции, либо смысла в различных биологических системах.
Изучение статистических свойств биологических макромолекул началось задолго до появления соответствующих возможностей, предоставляемых современным уровнем развития вычислительной техники [106, 107]. С момента открытия структуры молекулы ДНК с исследованием статистических свойств связывались надежды на скорую "расшифровку" всех свойств, которые кодируются нуклеотидными последовательностями. Дальнейшее развитие молекулярной биологии и смежных дисциплин показало, что эти надежды реализованы не были, по крайней мере, не полностью.
С другой стороны, развитие прикладных исследований, в первую очередь в области биотехнологии, привело к тому, что статистический анализ биологических макромолекул (нуклеотидных и аминокислотных последовательностей) развился в специфическую область исследований, наиболее важными в которой с точки зрения нашей работы стали исследования, посвященные проблеме организации быстрого поиска аналогов и гомологов для различных (как правило, коротких) последовательностей. Эта сфера исследований в последнее время оформилась в область со своими школами, течениями, направлениями, и получила в науке название биоинформатики [1, 97, 129, 133, 134, 161].
Распознавание структурных закономерностей в генетических текстах
Согласно современным представлениям, геномы состоят из различных по своим статистическим и функциональным характеристикам частей. Отсюда возникает следующее направление в статистических исследованиях нуклеотидных последовательностей, а именно задача обнаружения границ этих частей и распознавания структурных закономерностей в генетических текстах.
После открытия экзон-интронной структуры ДНК и выделения в нуклеотидной последовательности кодирующих и некодирующих участков продолжаются попытки объяснить возникновение этой структуры [1, 17, 46, 58, 99, 112, 133, 134, 161] и сравнительные исследования статистических характеристик структурных элементов [9, 23, 25, 46, 73, 92, 121, 129]. В работе [181] предложен метод поиска функциональных участков ДНК, использующий представление последовательности в виде фрактальной структуры (см. также [79, 84,120]).
Для описания неоднородных генетических текстов, т.е. текстов с различными статистическими характеристиками разных частей используют, например, модель неоднородной Марковской цепи [188]. При введении неоднородной Марковской цепи генетический текст разбивается на зоны, при этом каждая зона характеризуется своими переходными вероятностями. Такой подход позволяет показать, что для ряда слов большие отклонения от ожидаемых частот встречаемости объясняются не "биологическим" смыслом, а неоднородностью генетического текста.
Для анализа неоднородных генетических текстов вводится понятие стационарных и нестационарных слов. Стационарные слова относительно равномерно расположены по всей длине текста, в то время как частота встречаемости нестационарных слов зависит от того, какая часть текста рассматривается. В работе [23] была предпринята попытка анализа зонной структуры генома фага X. При определении границ между предполагаемыми блоками необходимо определить разность /-граммного состава между окном слева от точки границы и справа от нее. Таким образом, позиция / рассматривается как потенциальная граница блока, если разность /-граммных составов в окне слева и справа от нее велика. Для снижения уровня "шума" и исключения появления случайных границ лучше использовать только стационарные /-граммы. Для определения разности /-граммных составов, например при 1 = 2 можно использовать функцию \S\ где S — множество стационарных /-грамм, dt =/?, -h\ — разность между количеством /-грамм вида / в левом и правом окне. По данному критерию строится функция г, при этом положение пиков на графике соответствует предполагаемым границам между зонами. В данном примере полученные границы хорошо согласуются с известными фактами и в ряде случаев позволяют уточнить представление о зонной структуре фага.
При анализе структуры символьной последовательности в отсутствие какой-либо априорной информации о таковой важную роль играет понятие повтора. Структура текста в этом случае характеризуется совокупность всевозможных повторов ("алфавитом" повторов), частотами встречаемости каждого из элементов этого алфавита и указанием мест вхождения в текст наиболее характерных элементов алфавита [21, 23, 74, 80,120].
Одним из методов исследования повторов является построение частотной характеристики текста [23, 41, 74, 80, 118, 119]. Частотная характеристика порядка / текста Т есть совокупность элементов Ф,(Т) = {Ф,, Ф, ,..., Ф, }, где каждый элемент Ф, 1 j mj есть пара (/-я /-грамма, частота ее встречаемости в тексте). Полный частотный спектр текста Т — совокупность частотных характеристик Ф(Т) = (Ф(Т), Ф2(Т),..., Ф, (Т), Ф/ошс+(Т)} , где /тах минимальное значение /, начиная с которого в тексте уже отсутствуют повторяющиеся /-граммы. По частотной характеристике /-го порядка может быть восстановлена характеристика (/-1)-го порядка (за исключением, может быть, частот начальной и конечной (/-1)-грамм). По частотной характеристике Ф, +1(Т) однозначно могут быть идентифицированы начальная и конечная /-граммы текста, после чего может быть восстановлен сам текст путем выявления пар /тах +1-грамм с совпадающими /тах-граммами [9, 21, 22]. Описанные выше структуры удобно использовать при вычислении энтропийных характеристик текста, для оценки по выборке переходных вероятностей в Марковских моделях, в задачах классификации. К недостаткам структур относятся, во-первых, их избыточность (не все повторы являются функционально значимыми); а во-вторых, отсутствие информации о расположении повторов в тексте.
Естественным путем к устранению первого недостатка является выделение из частотного спектра и рассмотрение только функционально значимых /-грамм. В связи с этим возникает важный, применительно к генетическим последовательностям, вопрос: какие именно /-граммы считать функционально значимыми? Одним из возможных путей решения этого вопроса является сопоставление характеристик анализируемого текста с аналогичными характеристиками случайной последовательности той же длины и с тем же алфавитом, полученной по схеме независимых испытаний. Наличие аномальных отклонений от схемы независимых испытаний возможно свидетельствует о неслучайности, т.е. функциональной значимости наблюдаемой закономерности. Таким образом, для отделения "случайных" повторов от "неслучайных" необходимо учитывать такие признаки, как длина повтора, его частота, расположение повторов в тексте (периодичности), а также возможность их расширения при условии небольших изменений в тексте последовательности. Вероятностные оценки параметров /тах для различных длин N текстов и мощностей алфавита п дают представление о том, какой длины случайные повторы могут встретиться в исследуемой последовательности. Оценка порядка величины /max (N, п) получена в [23] и [118, 119] и зависит от вероятностей рк, \ к п следующим образом:
Конечно-частотный словарь и проблема восстановления полной последовательности
Обратимся к проблеме глобальной восстанавливаемости частотных словарей символьных последовательностей. По-прежнему будем рассматривать в качестве объекта нашего исследования нуклеотидные последовательности. Всюду далее в этой главе будут рассматриваться только связные последовательности, то есть такие, которые не содержат внутри себя пробелов (пустых символов). Число символов ТУ в рассматриваемой последовательности будем называть длиной последовательности; любую связную подпоследовательность (О длины q из рассматриваемой последовательности
будем называть словом. Набор всех слов, встречающихся в исследуемой последовательности будем называть её носителем (или q -носителем, если требуется прямое ука зани на характеристику носителя). Снабдим каждое такое слово числом его копий; полученная конструкция является конечно-частотным словарём F(q) толщины q.
Общее число всех слов длины q равно Мч, где М — мощность алфавита изучаемой последовательности, то есть число различных символов, из которых состоит исследуемая последовательность. Понятно, что по мере роста длины слов в носителе общее число возможных слов нарастает экспоненциально, и в тексте встречаются далеко не все возможные слова. Отметим также, что общее число всех слов длины q в последовательности длины N с учётом возможных повторов одинаковых слов составляет N-q + l.
Для любого конечно-частотного словаря толщины q переход к конечно-частотному словарю меньшей толщины всегда осуществляется однозначно: достаточно просуммировать число слов длины q, различающихся лишь первым либо последним символом. Следует отметить, что, строго говоря, конечно-частотные словари меньшей длины, просуммированные по правому концу слов и по левому их концу, различаются. Это обусловлено краевым эффектом: два крайних слова меньшей длины (располагающихся в самом начале исследуемой последовательности и в самом её конце) не могут быть учтены при суммировании по первому (и, соответственно, по последнему) символу. Тем не менее, за исключением этой ситуации, все остальные числа копий более коротких слов могут быть легко вычислены. Обратный переход далеко не всегда однозначен: действительно, может случиться так, что одно слово СО , может входить в несколько различных слов со длины q и иметь тем самым несколько различных продолжений. Существует, однако, такая длина, начиная с которой всегда возможно однозначное восстановление конечно-частотного словаря большей толщины по словарю этой (и большей, естественно) толщины; эта длина d слов была нами названа длиной обрезания, поскольку построение любого конечно-частотного словаря всегда можно оборвать на толщине d +1: все более длинные слова могут быть однозначно восстановлены по d -носителю.
Длина d определяется как такая, начиная с которой все слова в исследуемом тексте встречаются ровно один раз. Такая длина существует всегда: в наихудшем случае она совпадает с длиной всего исследуемого текста. Тот факт, что восстановление конечно-частотного словаря любой большей толщины по словарю толщины d +1 может быть осуществлено однозначно, доказывается весьма элементарно и мы не будем подробно останавливаться на этом [11 - 13, 22]. Однозначность восстановления следует из того факта, что два слова длины d +1 всегда пересекаются по слову длины единственным образом. Соответственно, у каждого слова длины d +1 всегда име ется единственное продолжение. Длину d всегда можно легко вычислить: она на один символ больше длины наибольшего повтора; алгоритмов же поиска наидлиннейшего повтора существует достаточно много и все они хорошо описаны [1,9,163].
Понятно, что значение d существенно зависит как от длины исходного изучаемого текста, так и от его структуры. Существует строгая оценка снизу для этого значения; она даётся следующим соотношением М " =N. Для генетических текстов эта оценка даёт значение Для случайных некоррелированных последовательностей из четырёхбуквенного алфавита с равными вероятностями появления символов значение для d оценивается как
Тем самым мы получаем первый критерий для сравнения различных нуклеотидных последовательностей по такой их характеристике, как длина обрезания их конечно-частотного словаря. Следует сравнивать величину d с логарифмом длины исследуемой последовательности, то есть сравнивать исследуемую последовательность со случайной некоррелированной, в которой нуклеотиды появляются с равными вероятностями.
Реальные нуклеотидные последовательности весьма сильно различаются по значениям величины d своих конечно-частотных словарей. Это отношение может считаться показателем избыточности исследуемой последовательности; следует отметить, что стандартные определения избыточности [59] отличаются от указанного. Значение г не является, строго говоря, показателем избыточности; оно лишь сравнивает критическую толщину d реального конечно-частотного словаря с критической толщиной d словаря, построенного для модельного текста — случайной некоррелированной последовательности с равными вероятностями появления символов в ней.
С точки зрения изучения биологических свойств различных реальных нуклеотидных последовательностей представляется интересным сравнить различные участки реальной нуклеотидной последовательности, либо разные последовательности, принадлежащие различным организмам по такому показателю, как d . Поскольку реальные последовательности зачастую существенно различаются по длине, сравнивать их следует по величине г. Тем более имеет смысл вести сравнение по этой величине различных участков одной и той же последовательности. Сложность при сравнении различных участков одной и той же последовательности заключается в самом определении такого рода участков. В реальных последовательностях можно выделять участки различными способами и на основе различных принципов. Один из вариантов — это структура, задаваемая триплетами. Другой возможный вариант выделения сравниваемых участков — это интроны и экзоны [171]. Возможны и другие варианты, например, определяемые эпигенетической структурой [46, 54].
В Таблице II. 1 приведены результаты определения значения величины d и отношения г = d /log2 N некоторых реальных нуклеотидных последовательностей. Таблица II.2 содержит результаты определения длины обрезания и значения г для семейства генов человека, Таблица Н.З — аналогичные данные для генов вирусов человека. Следует отметить, что вирусы представляют собой своего рода молекулярных паразитов. Это обстоятельство привело к тому, что многие вирусные генетические системы считаются хорошими моделями генетических систем их хозяев; по всей видимости, с точки зрения функциональной близости такой взгляд вполне закономерен. Другое дело — статистические характеристики вирусных последовательностей и последовательностей их хозяев. Ожидалось, что функциональная близость порождает и близость в структурах, в том числе и в такой структуре, как взаимное расположение нуклеотидов. Наши результаты показали, что это не так: гены вирусов человека обладают меньшей удельной длиной обрезания, чем гены их хозяев — человека. Приведённые выше Таблицы П.2 и П.З иллюстрируют это обстоятельство. Все последовательности в указанных таблицах взяты из EMBL-банка, а в качестве названий приведены их идентификаторы (в Таблицах II.2 и Н.З).
Принцип максимума энтропии частотного словаря и восстановление частотных словарей большей толщины по заданному
Высказывание любой гипотезы о конкретном виде продолжения того или иного слова вносит априорное, внешнее знание в тот частотный словарь (большей толщины), который будет построен по частотному словарю заданной толщины [108, 159, 183]. Напротив, предполагая, что мы будем рассматривать лишь наиболее вероятные продолжения, можно избежать такого влияния. Принцип наиболее вероятного продолжения слова означает, что среди всех возможных частотных словарей большей толщи ны, которые порождают частотный словарь заданной толщины W{q) следует выбирать такой, энтропия которого была бы максимальна. Рассмотрим для начала задачу построения частотного словаря на единицу большей толщины, чем заданный. Итак, для заданного частотного словаря W{q) мы имеем набор словарей yV(q +1)}, среди которых нам надо выбрать один. Будем выбирать среди них такой, в котором слова имели бы наиболее вероятные продолжения. Это означает, что такой словарь будет наименее определён и, соответственно, его энтропия S максимальна среди всех остальных частотных словарей этой толщины, порождающих при переходе "вниз" (к словам меньшей длины) заданный частотный словарь. Напомним, что энтропия S частотного словаря W(q) является выпуклой функцией и достигает максимума, когда все частоты fa слов в этом словаре равны; здесь индекс СО перечисляет слова в частотном словаре. Для того, чтобы построить восстановленный частотный словарь W (q + ї) на единицу большей длины необходимо найти такие частоты слов в этом восстановленном словаре /ш,, чтобы они, во-первых, порождали частотный словарь толщины q, причёл» как при суммировании по первому, так и по последнему символу, а во-вторых, доставляли максимум энтропии Значения для fUj п могут быть найдены методом неопределённых множителей Ла гранжа. В явном виде значения для частот fjU и , выраженные через частоты f(0 исходного частотного словаря толщины q выражаются следующим образом: Выражения (3.4) и (3.7) полностью аналогичны хорошо известному в статистической физике приближению Криквуда [4, 10, 131]. Если для задач статистической физики выражения (3.4 — 3.7) являются приближением, то в нашем случае они являются точным решением. Обусловлено это тем, что в отличие от задач статистической физики, в нашем случае отсутствует взаимодействие через третью частицу — все "частицы" (слова) в нашем случае взаимодействуют (пересекаются) непосредственно, никак не пересекаясь с какими-либо ещё словами.
Данное соотношение не является признаком того, что рассматриваемая последовательность порождена Марковским процессом. При выводе этого выражения для восстановленных частот никаких предположений о свойствах последовательности не делалось. Нуклеотидная последовательность могла бы рассматриваться как реализация Марковской цепи лишь в том случае, когда соотношение вида (3.4) было бы справедливым для всех словарей бесконечно возрастающей толщины, определённых на ансамбле бесконечных же последовательностей. В нашем случае оно означает лишь, что Марковская цепь является тем модельным объектом, для которого всегда выполняется принцип наиболее вероятного продолжения. Одной из важных задач биоинформатики является поиск и выбор наиболее подходящей модели для того или иного реального генетического текста. Смысл такого рода выбора модели прозрачен и ясен — если исследователю удастся подобрать подходящую модель для генетического текста, то резко возрастут возможности для содержательного предсказания свойств таких текстов, с одной стороны, а с другой — можно будет вести речь об определении упорядоченности в генетическом тексте, определении его смысла и проч. Не обсуждая здесь проблему определения порядка в символьной последовательности, остановимся на проблеме выбора наиболее точной модели для генетического текста. Под моделью генетического текста понимается искусственная символьная последовательность, соответствующая реальному геному (геному, фрагменту генома и проч.) и являющаяся (конечной) реализацией того или иного случайного процесса.
Выбор типа процесса, подбор параметров какого-нибудь конкретного случайного процесса и составляет, собственно, задачу выбора модели генетического текста. Традиционно, генетические тексты моделируются случайными процессами двух типов: Бернуллиевским и Марковским процессами. Весьма обширный фактический материал [40, 67, ПО, 153, 175] показывает, что Бернуллиевские случайные процессы очень плохо моделируют реальные генетические тексты; наблюдаемые здесь исключения из этого правила весьма редки. Марковские процессы, напротив, достаточно хорошо моделируют реальные генетические тексты, и точность описания, понимаемая, например, как близость семейства случайных реализаций того или иного Марковского процесса реальному генетическому тексту, который моделируется этим Марковским процессом возрастает с увеличением порядка процесса. Одна из содержательных задач здесь — выбор порядка Марковского процесса, который бы наиболее точно описывал реальную генетическую последовательность [90, 91, 93, 94, 99, 151]. Обсудим эту проблему подробнее. Как показано в Главе 2, существует такая критическая толщина d частотно-конечного словаря, которая позволяет однозначно восстановить частотно-конечный словарь любой большей толщины, вплоть до всего исходного текста. Это означает, что Марковский процесс порядка d +1 абсолютно точно моделирует заданный (конечный) генетический текст, поскольку все переходные вероятности в этом процессе равны 1. Тем самым, возникает содержательный вопрос о выборе такого, сравнительно низкого, порядка для моделирующего Марковского процесса, который бы с одной стороны достаточно точно описывал исходный генетический текст, а с другой — имел возможно более низкий порядок, что интерпретируется как низкая сложность исходного генетического текста, например. Не существует естественных ограничений на порядок Марковского процесса, которым следует описывать тот или иной генетический текст. Ограничивать рост порядка такого случайного процесса приходится исходя из каких-либо иных соображений, дополнительных к собственно проблеме выбора модели, порождающей данный генетический текст. Укажем некоторые такие соображения, которые могут ограничивать рост порядка Марковского процесса, моделирующего тот или иной генетический текст.
Поиск и выделение информационно значимых сайтов в некоторых биологических последовательностях
Проиллюстрируем метод нахождения информационно значимого слова на примере нескольких реальных генетических текстов. В работе [115] предложена классификация последовательностей 16SPHK методом динамических ядер по их частотным словарям (толщины 1, 2, 3 и 4), а также по преобразованным частотным словарям; общее число последовательностей составило 1730 [105]. Построение классификации этих последовательностей по преобразованным частотным словарям позволило выделить сайты (слова) с наибольшей информационной значимостью для указанных последовательностей. В Таблице IV. 1 приведены информационные значимые триплеты для группы последовательностей 16SPHK, принадлежащих семейству Firmicutes, роду Actinomycetes. Подчеркнём, что эти информационно значимые триплеты получены не для какой-то одной нуклеотидной последовательности, а для группы последовательностей (общей численностью 978 последовательностей); данное обстоятельство делает эту группу информационно значимых триплетов даже более интересной, чем если бы они были получены для отдельной последовательности.
Весьма интересным фактом, с точки зрения анализа связи структуры и функции, кодируемой нуклеотидными последовательностями является отсутствие среди информационно значимых триплетов сигнальных: триплетов инициации ATG и GTG, а также стоп-кодона TGG. Среди информационно значимых триплетов имеются два стоп-кодона — TAG, реальная частота которого меньше ожидаемой и ТАА, реальная частота которого превышает ожидаемую. По всей видимости, это обстоятельство носит неслучайный характер.
Сравнение данных Таблицы IV. 1 с данными по частоте встречаемости кодонов показывает существенные корреляции между информационной значимостью того или иного триплета и частотой его встречаемости в геноме [100]. Непосредственное сравнение ожидаемой (и реальной) частот для триплетов с частотами кодонов, определяемых по геномам едва ли может считаться корректным — для этих последних подсчи тываются частоты кодонов, то есть таких слов длины 3, которые определяются не для любого положения окна считывания, а только для некоторых.
Наиболее часто встречающийся стоп-кодон (TGC) не попал в число информа-. ционно значимых, в то время, как два других в неё попали. Едва ли можно считать случайным то обстоятельство, что стоп-кодон, имеющий самую малую реальную частоту (TAG) имеет повышенную ожидаемую, в то время, как стоп-кодон, обладающей весьма заметной реальной частотой (ТАА) обладает пониженную ожидаемую. Низкие абсолютные цифры встречаемости этих всех кодонов не должны вводить в заблуждение: дело в том, что в реальных генетических текстах эти кодоны встречаются весьма редко — только в конце последовательности, кодирующей тот или иной белок; мы, в свою очередь, исследуем распределение частот не кодонов, а триплетов (встречающихся в произвольном месте исходной нуклеотидной последовательности).
Сравним поведение частоты вхождений кодонов в группе синонимичных тем, которые совпадают с информационно значимыми триплетами. Триплету ТТТ синонимичен лишь один триплет — ТТС, при этом его частота появления в геноме Bacillus subtilis в два раза ниже, чем для информационно значимого. Триплету ТСТ синонимичны ещё три триплета: ТСС, ТСА и TCG. При этом частота вхождения триплета ТСА (также информационно значимого, однако с повышенной ожидаемой частотой) сопос тавима с частотой вхождения триплета ТСТ, для которого реальная частота превышает ожидаемую, и частоты каждого из этих кодонов примерно вдвое превышают частоты синонимичных им двух других кодонов. Во многом похожая картина наблюдается для синонимичных триплетов, кодирующих пролин.
Обращает внимание то обстоятельство, что оба кодона, кодирующих тирозин, являются информационно значимыми; по крайней мере, такое их качество коррелирует с тем фактом, что тирозин является весьма специфической аминокислотой в белках [38]. Это же наблюдение справедливо и для двух триплетов, кодирующих аспарагино вую кислоту. Установление полной связи между реальными и ожидаемыми частотами появления кодонов требует однако дополнительных исследований.
В Таблице IV.2 приведены информационно значимые сайты (длины 4) для той же группы последовательностей 16SPHK. Указанные сайты в этой таблице в левом столбце упорядочены по убыванию значений отношения реальной и ожидаемой частот, а в правом — по возрастанию, т.е. таким образом, чтобы сами сайты в том и в другом столбцах были упорядочены по мере убывания их информационной значимости. Следует также подчеркнуть, что свойство информационной ценности, определяемое для того или иного слова длины 4 фактически никак не связано с его собственной частотой в реальном частотном словаре толщины 4. Точнее, эта связь носит весьма сложный. Опосредованный и нелокальный характер. Нелокальность здесь следует понимать как то обстоятельство, что свойство быть информационно значимым сайтом существенно зависит и от других слов, распределённых в целом по последовательности.
