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

Садовский, Михаил Георгиевич

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

Автореферат диссертации по теме "Информационно-статистический анализ нуклеотидных последовательностей"

На правах рукописи

САДОВСКИЙ МИХАИЛ ГЕОРГИЕВИЧ

ИНФОРМАЦИОННО-СТАТИСТИЧЕСКИЙ АНАЛИЗ НУКЛЕОТИДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

03.00.02 - БИОФИЗИКА

диссертации на соискание учёной степени доктора физико-математических наук

КРАСНОЯРСК, 2004

Работа выполнена в Институте биофизики СО РАН

Официальные оппоненты:

доктор биол.наук, проф. Кратасюк ВА, Институт биофизики СО РАН, г.Красноярск доктор физ.-мат.наук, проф. Смирнова Е.В., КГТЭИ, г.Красноярск доктор физ.-мат.наук, проф. Быков В.И., КГТУ, г.Красноярск

Ведущая организация: ГУ НИИ биомедицинской химии РАМН, г.Москва

Защита диссертации состоится " 18 " июня 2004 г. в 14— в актовом зале Института биофизики СО РАН на заседании специализированного совета по защитам диссертаций Д 003.007.01 при Институте биофизики СО РАН по адресу: 660036, г.Красноярск, Академгородок. С диссертацией можно ознакомиться в библиотеке ИБФ СО РАН.

Автореферат разослан «26« . 2004 года

Учёный секретарь совета, к.ф.-м.н., ст.н.с.

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

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

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

• разработке методов выявления и определения внутренней структурированности в символьных последовательностях;

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

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

• изучении закономерностей в распределении информационно значимых сайтов малой длины вдоль по геному и выявление связи этого распределения с функциональной ролью различных фрагментов ДНК. [ рд^ НАЦИОНАЛ

библиотека ":

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

1. Изучены некоторые типичные свойства нуклеотидных последовательностей, не известные ранее, и проявляющиеся в характеристиках восстановления частотных словарей, содержащих слова большей длины, по словарям заданной толщины.

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

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

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

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

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

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

3. развитии новых методов определения подобия геномов, основанных на сравнении наборов информационно значимых триплетов и информационно значимых 4-плетов;

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

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

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

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

Работа выполнена в лаборатории экологической биотехнологии Института биофизики СО РАН. Результаты, полученные в ходе работы были получены при под-

держке Красноярского научного фонда, гранты Ш0390, 3F0190, 4F0153, 5F0012 и 1Ш14С.

Структура работы. Работа состоит из шести разделов и включает в себя Введение и пять Глав, а также список цитированной литературы (193 источника) и Выводы. Работа содержит 57 рисунков и 104 таблицы. В работе исследовано более 250 различных геномов и более 2000 генов.

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

Глава 2 посвящена изучению проблемы восстановления конечно-частотного словаря. В этой главе представлены результаты изучения условий однозначного восстановления конечно-частотного словаря. Рассмотрим связную (не содержащую пробелов) последовательность из некоторого конечного алфавита П длиной N символов. Совокупность всех слов (связных подпоследовательностей длиной q символов) вместе с числом копий этих последних называется конечно-частотным словарём (толщины д). Центральной проблемой всей работы является проблема изучения переходов от словарей толщины д к словарям иной (большей либо меньшей толщины):

т > и'2 + щ +-+•■• *—> ж,.! <—IV,.

Переход справа налево всегда однозначен; обратный переход как правило — нет. В настоящей главе рассмотрен случай однозначного восстановления и те свойства биологических макромолекул, которые определяются условиями однозначного восстановления конечно-частотного словаря. Однозначное восстановление конечно-частотного словаря возможно, начиная с определённой толщины Эта величина на два символа больше длины наибольшего повтора. На основе этой характеристики можно ввести новую меру избыточности нуклеотидной последовательности, отличающуюся от традиционного определения: — длина рассматриваемой последовательности. Установлено, что различные элементы генов — интроны и экзоны — различаются по величине г: гяятрои > гакзои у эукариотов, и сплайсинг как правило ведёт к её уменьшению. Для генов вирусов такая закономерность выполняется гораздо реже и г возрастает в результате сплайсинга. Проведено также сравнительное исследование геномов вирусов и прокариот и семейства генов, выде-

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

Рисунок 1 показывает два распределения генов по значениям избыточности г: для последовательностей зрелых мРНК генов человека и для аналогичных последовательностей генов вирусов человека. Видно, что два эти распределения заметно отличаются. Для группы генов человека определялась избыточность г до сплайсинга и после. Средняя по группе генов избыточность г до сплайсинга составляла г = 1,6643, а после — г = 1,1861. Аналогичные результаты для группы генов Са-зависимых белков таковы: соответственно. Напротив,

для генов вирусов человека наблюдалось противоположное изменение избыточности: г = 1,1451 до сплайсинга и г = 1,15153 — после него. Избыточность г полных геномов заметно отличается от средней избыточности генов, входящих в геном. Для исследованных 15 геномов хлоропластов средняя избыточность геномов составила а среднее значение избыточности генов в них составило

Глава 3 посвящена изучению проблемы восстановления частотного словаря. Неединственность продолжения словаря порождает проблему его восстановления. В качестве продолжения слов из частотного словаря возникает семейство словарей, и необходим критерий выбора того или иного словаря из этого ансамбля. Таким крите-

Рис. 2: Средняя информационная емкость 175 геномов митохондрий. Показаны стандартные отклонения

рием является принцип максимума энтропии восстановленного частотного словаря

позволяющий явно вычислить частоты /,,„„ восстановленного словаря толщины q по частотам реального толщины q — 1:

либо

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

случай ничего нового не даёт (однако соответствующий аналог (1) отличается от формулы вероятностей переходов в Марковской цепи).

Сравнение частот восстановленного словаря и реального одной и той же толщины позволяет вычислить информационную ёмкость реального словаря. Она определяется как условная энтропия реального частотного словаря И', относительно восстановленного до той же толщины:

где индекс w' перечисляет слова из восстановленного частотного словаря, Д/ — частоты слов в нём, а /ы — частоты из реального частотного словаря толщины q. Очевидно, что для некоторых слов из восстановленного словаря = 0, то есть этих слов нет в реальном словаре, они есть только в восстановленном. Величина (3) тем самым определена всегда. Для символьных цепочек, восстановленных по частотному словарю толщины q — 1 выражение (3) принимает вид ^ — = 25,-i — - либо 25i - 5г для случая q = 2.

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

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

(3)

0,30 ОД!

ОДО 0,15 0,10 0,05

0,00 11 ''' 1 м .......... 111111 I ■ I I т I ...................................................

§ 8 I I I I | I I I I I I I I

Рис. 3: Сканирование генома фага А для д = 3 (Ь = 1000, * = 60). Чёрной линией (нижняя) показана микроинформационная структура генома, серой с маркерами (верхняя) — самоподобие.

считывания Ь.

Ещё одним способом выделения и описания структурированности генома, основанной на его информационных и статистических характеристиках, является изучение его самоподобия. Самоподобие — это подобие того или иного фрагмента генома целому. Самоподобие определяется близостью частотного словаря изучаемого участка к частотному словарю всего генома; её естественной характеристикой является условная энтропия (3), где вместо восстановленного частотного словаря рассматривается частотный словарь всей последовательности. Такое сравнение позволяет строить профили самоподобия последовательности (например, генома). Очевидно, что для профиля самоподобия (3) определено всегда, поскольку носитель частотного словаря сравниваемого участка всегда вложен в носитель словаря исходной последовательности. На Рисунке 3 представлены профили микроинформационной структуры и самоподобия генома фага А (номер доступа 102459 в БМБЬ-банке). Хорошо видно, что эти два способа выделения информационной структуры дают разные результаты.

Глава 4 посвящена изучению множества информационно значимых слов, встречающихся в геномах. Изучение восстановленных частотных словарей позволяет вы-

делить слова, которые в наибольшей степени отличают реальный и восстановленный словари — информационно значимые слова (ИЗС); именно они дают наибольший вклад в значение (3). С другой стороны, результаты сканирования геномов, изложенные в Главе 3, позволяют предполагать, что такого рода слова будут распределены вдоль по геному неслучайно (см.Рисунок 3). Пусть — частота слова в реальном частотном словаре текста, a fu — частота этого слова в восстановленном частотном словаре. Зафиксируем величину а > 1; тогда ИЗС — это слова, для которых не выполняется неравенство

Число ИСЗ в рассматриваемой последовательности зависит от а и от длины слов q, для которых ищутся ИЗС. Состав информационно значимых слов малой длины (д = позволяет сравнивать между собой последовательности, принадлежащие разным видам, либо сравнивать между собой фрагменты одной последовательности (например, кодирующие и некодирующие участки). Такое сравнение изучается в Главе 5.

Настоящая глава посвящена исследованию соотношения между ИЗС различной длины. ИЗС не обладают свойством монотонности: слова длины к могут входить, а могут и не входить в ИЗС длины к + 1; более того, даже если вложение наблюдается, заранее нельзя гарантировать, что у двух ИЗС будет совпадать порядок соотношения реальной и ожидаемой частот. Пусть, тем не менее, цепочка ИЗС

для некоторого q существует. Цепочку вида (5) будем называть восходящей (соответственно, нисходящей), если fUj > а • fU) для каждого j = 2, 3, ... , д (если для каждого соответственно). Самое короткое слово в (5)

будем называть корнем, самое длинное — вершиной. Объединение всех цепочек вида (5), начинающихся из одного корня, будем называть пирамидой (восходящей либо нисходящей, соответственно). Очевидно, что могут существовать пирамиды, не являющиеся ни восходящими, ни нисходящими. На Рисунке 4 показана нисходящая пирамида для бактериального генома Borrelia burgdorferi.

Особенный интерес представляет изучение распределения информационно значимых слов вдоль по генетическому тексту. Исследовалось распределение ИЗС, являющихся вершинами порядка 8 восходящих и нисходящих пирамид, вдоль по геномам для нескольких организмов (бактерий E.coli и B.subtilis, дрожжей Scbizosac-cbaromycespombe, митохондриальных геномов и геномов хлоропластов). Для всех этих генетических систем было установлена неслучайность и неравномерность распределения ИЗС вдаль по геномам. Такие ИЗС встречаются с повышенной частотой

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

Например, для генома вершины нисходящей пирамиды с основанием TAG встречаются в нём фактически по одному разу, в то время, как всего две вершины нисходящей пирамиды с основанием АСА встречаются в 39 копиях (вершина AATCACAG) и в 17 копиях (вершина ATCACAGA). Первое из этих слов 30 раз встречается в участках генома, кодирующих различные гены, 7 раз — в некодиру-ющих областях, и по разу в промоторной и регуляторной областях. Второе слово 13 раз встречается в областях, кодирующих различные гены, 3 раза — в некодирующих областях и один раз — в промоторной области. Две вершины нисходящей пирамиды с основанием TGT встречаются в большом числе копий. Слово CCTGTGAT встречается в 35 копиях, а слово CTGTGATT встречается в 40 копиях. Из этих двух слов первое встречается в 30 областях, кодирующих различные гены, 5 раз — в не-

кодирующих областях. Второе слово встречается 27 раз в областях, кодирующих различные гены и 13 раз — в некодирующих областях.

Для генома B.subtilis вершина CGATAGCA нисходящей пирамиды с корнем TAG встречается в геноме в 24 копиях. При этом оно 2 раза попадает в некоди-рующую область, однако оба раза находится на расстоянии приблизительно в 200 нуклоотидов от кодирующей области, а 22 раза — в кодирующие области. Обращает на себя внимание тот факт, что это слово ни разу не попало в регуляторную область генома.

Обратимся ещё раз к Рисунку 4. На нём видны две вершины длиной q = & нукле-отидов и восемь вершин длиной нуклеотидов. Вершина встреча-

ется в геноме в единственном экземпляре и начинается в позиции 499525. Это слово расположено в первой сотне нуклеотидов гена BB048S, кодирующего белок L22 рибосомы (rplV), а слово TCCTCGAT встречается в двух позициях: в точке 652124 оно входит в начало гена кодирующего фактор репарации в ходе транскрипции

(mfd), а в позиции 9Ю680 это слово попадает в некодируюшую область генома. Все терминальные семёрки этой пирамиды встречаются ровно по одному разу и попадают в следующие области: слово ACCGAGT встречается в 725386 позиции и входит в ген кодирующий синтетазу (слово вхо-

дит приблизительно за 70 нуклеотидов до конца гена); слово встреча-

ется в 256937 позиции и входит в ген ВВ0251, кодирующий лейцил-тРНК синтетазу (leuS) (слово входит приблизительно за 500 нуклеотидов после начала гена); слово CCCGAGG встречается в 186580 позиции и включено в ген BB0J8S, фактически в самое его начало, функция неизвестна; слово CCCGAGT встречается в 725710 позиции и входит в ген ВВ0685, кодирующий 3-гидрокси-З-метилгдютарил-СоА ре-дуктазу (mvaA) (слово входит приблизительно за 40 нуклеотидов до конца гена); слово CCGAGGC встречается в 428244 позиции и включено в ген кодирую-

щий аденилаткиназу (adk) (слово включено приблизительно через 100 нуклеотидов от начала гена); слово CCGAGTG встречается в 482209 позиции и расположено в некодирующей области генома за 15 нуклеотидов до начала гена транспортной РНК tRNA-Ser-З; слово GCCCGAG входит в 444717 позиции, в самом начале гена 16S РНК, слово GCCTCGA входит в 722589 позиции, включено в ген ВВ0681, кодирующий метил-связывающий белок хемотаксиса и расположено при-

близительно в районе 1500-го нуклеотида этого гена.

Изучение распределения ИЗС вдоль по геномам позволяет точно и строго сформулировать задачу выявления связи между структурой и функцией нуклеотидной последовательности. Пусть выделен набор {w} информационно значимых слов. Для каждого такого слова построим функции распределения

вероятности того, что данное слово находится на расстоянии в р нуклеотидов слева (Д+) от какого-либо функционального элемента генома, принадлежащего к-ому семантически значимому классу С«, и слева (Д^)- Эти функции соответствуют двум возможным направлениям в поиске соответствия структуры и функции: в сторону З'-конца и в сторону 5'-конца нуклеотидной последовательности от слова

соответственно. Зафиксируем этот класс и построим аналогичные функции для всего набора ИЗС (й)}. Затем построим функции

= (7)

>=1

отличающиеся направлением от ИЗС к ближайшему элементу класса С« Здесь функция является весовой функцией и описывает некоторые

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

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

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

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

быстро падает с ростом длины выравниваемых участков, и на число сравниваемых последовательностей — несмотря на то, что увеличение числа выравниваемых последовательностей улучшает его, содержательным пределом для выравнивания является сравнение сотен последовательностей. Развитые в работе методы сравнения свободны от этих двух недостатков. Пусть требуется сравнить к последовательностей; составим их копсчно-частотные словари и F<¡ÍK Тогда для сравнения двух символьных последовательностей вычислим величину

где сагс1{Х} означает мощность множества (число слов в нашем случае), а вирр — носитель конечно-частотного (или частотного) словаря. Фактически величина (8) определяет отношение числа общих слов в двух словарях к общему числу слов в них. Мерой близости двух сравниваемых символьных последовательностей на длине слов д будет величина

--ЧйТ«—

(9)

Функция (9) обладает следующими свойствами: 0 < 1>(д) < 1, при этом Ь (д) = 0 в том и только в том случае, когда в сравниваемых последовательностях нет ни одного общего символа; в случае совпадающих последовательностей Ь (д) стремится к 1 при возрастании д; наконец, если две последовательности не совпадают между собой, но при этом содержат обшие слова, то Ь (д) имеет максимум при некотором значении 1 и стремится к 0 по мере роста д. Длина £*, для которой (9) достигает максимума может быть интерпретирована как радиус корреляции двух символьных последовательностей. Формула (9) может быть легко обобщена на случай сравнения нескольких последовательностей. Для этого необходимо составить конечно-частотные словари для всех рассматриваемых последовательностей ... ,а вели-

чину (8) в формуле (9) заменить на

Для сравнения последовательностей по частотным словарям 7 = 1,2к построим из них гибридный словарь той же толщины. Его частоты — среднее арифметическое частот соответствующих слов в сравниваемых словарях:

Мера близости словарей задаётся значением условной энтропии каждого частотного словаря вычисленного относительно гибридного И^^:

Такой выбор меры близости (11) при определении (10) гибридного словаря обеспечи-

сЬ)

вает минимум суммы всех значении условной энтропии о , определяемый внутри сравниваемой группы:

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

ваемых словарей, вычисленных относительно гибридного существует простая связь:

Таблица 1 содержит результаты сравнения последовательностей методом гибридного словаря. В этой таблице представлены результаты сравнения последовательностей из группы 0818121 (место хранения — БМБЬ-банк). Эта группа последовательностей была выровнена, а результаты выравнивания — депонированы в БМБЬ-банке. В таблице представлены последовательности 128 рибосомальных РНК 17 таксонов. В Таблице 1 все последовательности упорядочены по тому выравниванию, которое депонировано в БМБЬ-банке. Опорная последовательность, относительно которой выравнивались все остальные — самая первая в таблице. Хорошо видно, что сами по себе результаты сравнения заметно отличаются на различных длинах слов q. Кроме того, очевидно, что первая в группе последовательность (опорная для выравнивания) не является самой близкой к гибридному словарю. Такого рода близость заранее требовать нельзя, но можно ожидать, что референтная последовательность будет максимальна близка к общему статистическому предку. Хорошо видно, что на длине слов 9 = 1 наиболее близкой к гибридному словарю является последовательность М95110, а на длине 9 = 2 М86498; на длине слов д = 3 и q = б наиболее близкими к гибридному словарю оказываются последовательности М86498 и У00654, соответственно. На этой длине слов опорная последовательность становится 13 и 16, соответственно.

Таблица 1: Результаты сравнения последовательностей методом гибридного словаря для группы DS18121

еШу 9=1 ? = 2 9 = 3 9 = 4 9 = 5 9 = 6

М95109 0,0036 0,0089 0,0305 0,1163 0,4335 1,0483

М95108 0,0019 0,0118 0,0302 0,1086 0,4028 0,9596

М86496 0,0015 0,0038 0,0076 0,0247 0,1009 0,3524

М95110 0,0009 0,0074 0,0288 0,1223 0,4456 0,9800

Х61145 0,0093 0,0202 0,0343 0,0635 0,1318 0,2085

У00654 0,0073 0,0165 0,0295 0,0565 0,1146 0,1878

Л01394 0,0083 0,0193 0,0342 0,0624 0,1220 0,1979

М55541 0,0012 0,0029 0,0071 0,0250 ОДОЮ 0,3503

М86498 0,0011 0,0026 0,0064 0,0218 0,0915 0,3332

М86499 0,0027 0,0064 0,0125 0,0316 0,1117 0,3649

М86501 0,0020 0,0049 0,0094 0,0270 0,1035 0,3515

У00622 0,0242 0,0656 0,1403 0,2983 0,7342 1,4654

М86497 0,0011 0,0029 0,0067 0,0243 0,1019 0,3527

М86495 0,0012 0,0028 0,0067 0,0246 0,0968 0,3518

М86500 0,0012 0,0029 0,0076 0,0227 0,0942 0,3524

Х14848 0,0101 0,0229 0,0406 0,0754 0,1468 0,2465

М86493 0,0018 0,0039 0,0077 0,0256 0,1044 0,3607

Наконец, третий метод сравнения опирается на определение информационно значимых слов (4). Пусть для двух сравниваемых последовательностей выделены наборы информационно значимых слов некоторой фиксированной длины {й^1'} и {£¡5^}. Каждому слову из частотного словаря присваивается значение <т, а = равное + 1,-1 или 0, в зависимости от его информационного значения р,р — }ш/}и- <г — 1> если р > а, а = —1, если р < а'1, и,наконец, а — 0 во всех остальных случаях. Мера подобия двух последовательностей тогда определяется формулой

где ¿(а, Ь) — символ Кронекера, а С — мощность носителя словарей. Необходимо подчеркнуть, что с помощью величины (13) можно сравнивать лишь частотные словари, носители которых совпадают. Здесь ц = 0 означает, что у двух сравниваемых последовательностей нет ни одного общего слова с одним и тем же значением информационной ценности о(ш), а ц = 1 означает, что все слова имеют одинаковое значение информационной ценности в сравниваемых последовательностях; очевидно, что

»¿•SP!» 1 * fjr

1 1 nl< ° :j . Jxj* o0

11 wl \ ULI ч i

W •••• « 'Ее и ; й ■г- N Г. / d t

• I/o: ö

b 11 M i i 11 11 11111 1111 i 111 i i > i i ■ i 1111 11 i 11 11 1111 i i i ■

Л ^ Vi »o N > к

Ч N > К

*« Оч

3 » »

N" Ч N*

«г -i -c < -i -i -J 4 < 4 «i 4 4 < 4 -? 4 4 4 -f " ■ " -Chlamidia —о—Brucella meläensis - • o- Leptospira Interrogans —Brucella suis

Рис. 5: Подобие между двумя хромосомами четырех бактериальных геномов

Этот метод сравнения также может быть легко обобщён на случай нескольких последовательностей. По-прежнему, для каждой из сравниваемых последовательностей строится частотный словарь, в котором каждому слову присваивается значение а € {+1,-1,0},в зависимости от того, попадает ли оно в разряд информационно значимых (при заданном уровне информационной значимости а). Формула (13) для этого случая будет такой:

(14)

/.({*'>}, (т«}.... {**>})=£• £

1<1<]<к

где Л — нормировочный множитель. В случае совпадения мощности С носителей сравниваемых словарей Л = С-(С + 1)/2. Необходимо подчеркнуть, что с помощью величины (14) можно по-прежнему сравнивать лишь частотные словари, носители которых совпадают; обобщение на случай несовпадающих носителей также возможно. На Рисунке 5 показаны четыре бактериальных генома, состоящие из пары хромосом; на этом рисунке представлены значения близости между хромосомами одного генома на длине слов 4. Близость определялась по величине (13). По горизонтальной оси отложены значения порога информационной значимости а, для которых эта близость определялась. На Рисунке 6 показаны результаты сравнения. кодирующих и некодирующих областей генома (для двух хромосом), определённые на длине слов 3. На этом рисунке по-прежнему по горизонтали отложены значения порога информационной значимости о и близость также определялась по (13).

0,95 0,85 0,75 0,65

0,55 -г—I—1—I—I—I—I—1—I—I—1—I—I—г—г-т—I—г—)—I—I—) 'I I—т—I—г—>—I—I—1—I—I—I—I—I

С> О, С> О, ^ ~ -- ->„ <4 гч с^ гч ел г» ^

Рис. 6: Подобие между кодирующими и некодирующими областями генома B.subtilis, чёрные метки — q = 3, белые — q = 4.

Сравнение 16 бактериальных геномов (18 последовательностей, 2 генома состоят из двух хромосом) по наборам ИЗС длины 3 выявило отсутствие корреляции между различными видами (и даже между хромосомами одного генома). Напротив, сравнение таких геномов по наборам ИЗС длины 4 выявило сильную корреляцию между близкородственными геномами, а также между геномами бактерий с одинаковой физиологией — например, в целом корреляция выше внутри группы грам-положительных, либо грам-отрицательных бактерий, чем между ними. Для наборов геномов аденовирусов (16 видов), бактериофагов (11 видов), хлоропластов (15 видов) наблюдается удовлетворительная корреляция как на длине слов 3, так и на длине слов 4. Отсутствие корреляции по наборам ИЗС на длине 3 между бактериальными геномами может быть объяснено весьма плотной упаковкой наследственной информации в бактериальных геномах - по-видимому, различные группы генов обладают структурой частотных словарей и эти структуры интерферируют друг с другом, нивелируя эффект выделения общего набора информационно значимых триплетов. Напротив, эукариотические геномы несут имеют довольно протяжённые участки некодирующих областей, которые позволяют избежать интерференции.

Выводы, выносимые на защиту.

1. Введено новое определение избыточности нуклеотидной последовательности.

Показано, что этот показатель различается для функционально различных

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

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

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

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

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

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

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

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

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

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

Основные результаты работы опубликованы в:

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

2. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. Сравнительная избыточность генов различных организмов и их вирусов // Генетика, 1993. Т.29, № 9, с.1413-1419.

3. 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. V.27, № 2, p. 1-13.

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

5. Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: new method to compare two genes // Modelling, Measurement & Control, ser. C, AMSE Press, 1994. V.45, № 4, p.27-36.

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

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

8. 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, AMSE Press, 1995. V.48, № 4, p.17-22.

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

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

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

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

13. Бугаенко Н.Н., Горбань А.Н., Садовский М.Г. Метод максимума энтропии для восстановления частотных словарей и определения информационной ёмкости нуклеотидных последовательностей // Вычислительный центр СО РАН в г. Красноярске, Красноярск, 1997. - Деп. в ВИНИТИ 09.04.97, № 1878-В97.

14. 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.

15. 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 the 1" Int. Conf. on Bioinformatics of Genome Regulation and Structure, Novosibirsk, Aug., 24 - 27,1998; vol.11., p.314-317.

16. Bugaenko N.N., Gorban A.N., Sadovsky M.G. Maximum entropy principle and measurement of information content of genetic texts // Proc. of the lat Int. Conf. on Bioinformatics of Genome Regulation and Structure, Novosibirsk, Aug., 24 -27, 1998; vol.11., p.283-286.

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

18. Sadovsky M.G. Comparison of Symbol Sequences: No Editing, No Alignment // Open Systems & Information Dynamics, 2002. V.9, M 1, p.131-159.

19. Sadovsky M.G. Information capacity of symbol sequences // Open Systems & Information Dynamics, 2002. V.9, № 1, p.160-171.

20. Sadovsky M.G. Comparison of real frequencies of strings vs. the expected ones reveals the information capacity of macromoleculae // Journal of Biological Physics, 2003. V.29, № 1, p.23-38.

21. Sadovsky M.G. The method of comparison of nucleotide sequences based on the minimum entropy principle // Bulletine of Mathematical Biology, 2003. V.65, № 2, p.309-322.

22. Мамонова М.А.. Садовский М.Г. Информационная ценность различных триплетов некоторых генетических систем // Журнал общей биологии, 2003. Т.64, № 5, с.421-433.

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

24. 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 Networks: v.11 - Smart Engineering System Design, N.-Y.: ASME Press, 2001, p.657-663.

25. Макарова М.А., Садовский М.Г. Информационный подход к проблеме связи структуры и функции биологических макромолекул // Доклады АН, 2004. Т.396, № 2, — в печати

Подписано в печать "20 "ду^^лА 2004 г. Формат 60 х 86/16 Усл.печ.л. 1,5. Тираж 100 экз. Отпечатано на ризографе ИВМ СО РАН 660036, Красноярск, Академгородок

f-élOI

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

Введение

Глава 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. Введено новое определение избыточности нуклеотидной последовательности. Показано, что этот показатель различается для функционально различных частей гена, а сплайсинг приводит к уменьшению этого показателя у эукариотических организмов. Для генов прокариот, а также для генов вирусов этот показатель существенно более вариативен, а сплайсинг не всегда приводит к уменьшению избыточности.

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

Информация о работе

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

Диссертация

Информационно-статистический анализ нуклеотидных последовательностей - тема диссертации по биологии, скачайте бесплатно

Автореферат

Похожие работы