автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка алгоритмов и программ для изучения регулярного строения последовательностей ДНК

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

г^ьщ

Шеленков Андрей Александрович

РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММ ДЛЯ ИЗУЧЕНИЯ РЕГУЛЯРНОГО СТРОЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДНК

05.13.18 - математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ

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

Москва-2008

□03450687

003450687

Работа выполнена в Центре «Биоинженерия» Российской академии наук

Научпый руководитель:

доктор биологических наук, профессор Короткое Евгений Вадимович

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

кандидат физико-математических наук Андреев Сергей Григорьевич, Институт биохимической физики РАН

доктор биологических наук Лисица Андрей Валерьевич, ГУ НИИ биомедицинской химии им. В.Н. Ореховича РАМН

Ведущая организация:

Институт биоорганической химии им. академиков М.М. Шемякина и Ю.А. Овчинникова РАН

Защита диссертации состоится «26» ноября 2008 г. в "Ь часов на заседании Диссертационного совета Д212.130.09 в Московском инженерно-физическом институте (государственном университете) по адресу: 115409, Москва, Каширское шоссе, 31, тел (495) 324-84-98, (495) 323-92-56

С диссертацией можно ознакомиться в библиотеке Московского инженерно-физического института (государственного университета)

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

Автореферат разослан « » октября 2008 г. Ученый секретарь Диссертационного совета

доктор физико-математических наук, профессор Леонов А.С

Общая характеристика работы

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

Актуальность работы

В конце XX века с появлением новых технических средств такие области науки, как молекулярная биология и генетика, вышли на совершенно новый уровень Рост объемов получаемых биологических данных, в частности, последовательностей геномов различных организмов, приобрел экспоненциальный характер. С наступлением нового века эта тенденция сохранилась. Основным носителем наследственной информации являются молекулы дезоксирибонуклеиновой кислоты (ДНК), представляющих собой двойную спираль, состоящую из двух цепочек азотистых оснований - нуклеотидов. В молекулах ДНК присутствует четыре типа нуклеотидов, обозначаемых буквами Л, Т, С и в. Объем наиболее известного банка данных последовательностей ДНК - ОепЬапк - превышает 85 млрд. нуклеотидов.

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

Одной из важнейших задач аннотации является предсказание генов - участков ДНК, кодирующих белок, а также предсказание функций, выполняемых этим белком. Однако, в геномах высокоразвитых организмов, таких как растения, насекомые и млекопитающие, доля кодирующих последовательностей в геноме составляет не более 10%. Экспериментальные исследования показали, что в некодирующих областях располагаются участки, принципиальным образом влияющие на активность генов и саму возможность их правильного функционирования К числу таких участков относятся промоторы - важнейшие регуляторные элементы. Кроме того, некодирующие области генома также содержат большое число повторяющихся последовательностей с различной длиной периода [1] Несмотря на то, что такие последовательности на первый взгляд представляются бесполезными, они также играют определенную роль в функционировании генетического аппарата, в том числе, в обеспечении эволюционной гибкости вида, то есть, его способности реагировать на изменяющиеся внешние условия [1] Кроме того, мутационное изменение общей длины микросателлитпой последовательности в некоторых случаях может быть связано с серьезными заболеваниями. В работе [2] было показано, что при наличии большого числа микросателлитов вида (САО)„ (более 22) в гене андрогенового рецептора возрастает риск возникновения рака простаты, тогда как при числе повторов менее 20 риск значительно снижается. Таким образом, изменение числа повторяющихся элементов всего на две единицы может говорить о наличии заболевания, что делает обнаружение и анализ микросателлитов важным диагностическим инструментом.

Предсказание функциональной значимости участка ДНК естественным образом предполагает выявление общих структурных свойств последовательностей, характерных для определенных элементов генома (гены, промоторы, повторы и т.д.). В качестве характеристического свойства может выступать периодичность. Для обнаружения периодичности в последовательностях ДНК было разработано большое число методов, использующих различные математические алгоритмы, такие как преобразование Фурье [3, 4], динамическое программирование [5], исследование статистических свойств распределений символов [6], информационные подходы [7] и другие алгоритмы (например, [8]). Однако у всех ранее разработанных алгоритмов есть достаточно серьезные ограничения по выявлению периодичности в пуклеотидных последовательностях.

Основным недостатком использования преобразования Фурье при поиске периодичности в символьных последовательностях является необходимость перекодировки символьной последовательности в числовую. Эту перекодировку можно рассматривать как введение разных весов для равноправных символов, что в конечном итоге может приводить к невозможности обнаружения некоторых типов периодичности при использовании преобразования Фурье [7]. Кроме того, такие методы не способны обнаруживать периодичность при наличии вставок и делеций и они не дают возможность получить матрицу или некоторую другую характеристику типа периодичности, которая могла бы использоваться в дальнейших вычислениях.

При использовании динамического программирования и некоторых других подходов серьезным ограничением для выявления периодичности является поиск идентичных совпадений символов между последовательностями при выявлении повторов. Под идентичными совпадениями понимаются совпадения вида s(i)s(i), i=l,..,h, где s(i) - символ алфавита последовательности, А - размер алфавита символьной последовательности. В случае динамического программирования поиск преимущественно идентичных повторов задается при помощи весовой матрицы совпадений символов, для нуклеотидных последовательностей - это матрица идентичности (Identity matrix) или подобные ей матрицы. В этих матрицах веса идентичных совпадений (аа, tt,cc,gg для нуклеотидной последовательности) значительно выше, чем веса всех других видов парных совпадений. Это приводит к тому, что сильно размытые повторяющиеся последовательности, которые можно обнаружить на статистически значимом уровне только при наличии в последовательности многих периодов (>2), не могут быть выявлены этими методами [7]. Образование таких последовательностей в реальной ДНК может происходить посредством множественных замен оснований, а также путем образования делеций и вставок символов.

Программы поиска тандемных повторов в геномных последовательностях, представленные в пакете EMBOSS [9], находят только те повторы, которые принадлежат к ограниченному множеству возможных типов периодичности (некоторые микросателлиты). Некоторые алгоритмы демонстрируют сильную чувствительность к наличию вставок и делеций, таким образом, они могут обнаруживать только повторы, подчиняющиеся очень строгим правилам [8, 10].

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

Поиск периодичности в промоторах является намного более сложной задачей, чем поиск микросателлитов. На данный момент не выявлено теоретических или экспериментальных предпосылок к тому, что промоторы обладают периодической структурой. Таким образом, исследование последовательностей промоторов в основном сводится к выявлению некоторого «сигнала» (консервативного участка, определенного нуклеотидного состава и т.п.), который позволил бы разделить участки ДНК с неизвестной функцией на гипотетические промоторные последовательности и участки, наличие промоторов в которых маловероятно.

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

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

Цель и задачи исследования

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

Методы исследования

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

Основными задачами диссертационной работы являются:

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

2. Выявление сильно размытой периодичности с использованием полученных классов методом модифицированного профильного анализа (МПА) в различных геномах; выявление функциональной значимости обнаруженной периодичности

3. Создание базы данных по потенциальным мини- и микросателлитным последовательностям ДНК на основе результатов поиска скрытой периодичности в геномах различных организмов.

4. Разработка Интернет-сервера для поиска скрытой периодичности, реализующего метод МПА.

5. Разработка и программная реализация алгоритма выявления регулярности последовательностей ДНК, основанного на использовании критерия серий.

6. Применение разработанного алгоритма для выявления регулярности в последовательностях промоторов из различных геномов.

Научная новизна работы:

1. Разработан новый алгоритм классификации скрытой периодичности в

последовательностях ДНК

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

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

4. Разработан веб-сервер для поиска скрытой периодичности, реализующий новый алгоритм выявления скрытой периодичности.

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

Достоверность результатов работы подтверждена проведенными исследованиями нуклеотидных последовательностей из банков данных Genbank и EPD и сравнением с экспериментальными данными.

Апробация работы

Основные результаты и положения диссертации докладывались и обсуждались на международных конференциях «Биология - наука XXI века», Пущино, в 2004 (17-21 мая) и 2005 (18-22 апреля) гг., Bioinformatics of genome régulation and structure (Новосибирск, 25-30 июля 2004 г.), I и II международной конференции «Математическая биология и биоинформатика» (Пущино, 9-15 октября 2006 г. и 7-13 сентября 2008 г.), российско-французском научном симпозиуме по аннотации бактериальных геномов (Тулуза, Франция, 5-6 октября 2006), на международной школе-конференции молодых ученых «Системная биология и биоинженерия» (Звенигород, 28 ноября - 2 декабря 2005 г.), а также на ежегодных конкурсах-конференциях аспирантов и сотрудников Центра «Биоинженерия» РАН в 2004-2008 годах.

Основные результаты диссертации опубликованы в 12 работах: 4 статьях в рецензируемых отечественных и зарубежных научных журналах, 7 сборниках материалов научных конференций и 1 монографии (в период с 2004 по 2008 тт.)

Практическая значимость работы

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

На защиту выносятся:

1. Алгоритм эффективной классификации скрытой периодичности в последовательностях оснований нуклеиновых кислот.

2 Алюритм поиска сильно размытой периодичности в условиях наличия вставок и делеций символов с использованием классов периодичности.

3. База данных по потенциальным мини- и микросателлитным последовательностям

ДНК.

4. Веб-сервер для выявления скрытой периодичности.

5. Алгоритм выявления регулярности последовательностей ДНК.

6. Результаты поиска регулярных последовательностей в геномах различных организмов.

Структура н объем диссертации

Диссертация состоит из введения, трех глав, заключения и списка литературы из 114 наименований. Общий объем диссертации составляет 108 страниц; диссертация содержит 21 рисунок и 13 таблиц.

Краткое содержание работы

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

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

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

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

6

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

В разделе 1.4 приведены сведения по общедоступным базам данных тандемных повторов и микросателлитных последовательностей. Указаны методы, использованные при создании баз данных, а также адреса в сети Интернет, по которым эти базы доступны в настоящее время.

В разделе 1.5 рассмотрены веб-сайты поиска периодичности в последовательностях ДНК. Указаны используемые при их создании методы и кратко рассмотрены их достоинства и недостатки.

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

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

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

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

В разделе 2.1 приведено описание алгоритма поиска регулярных последовательностей, применявшегося в работе для анализа промоторов.

Назовем «регулярными последовательностями» такие последовательности ДНК, которые имеют близкое или одинаковое количество нуклеотидов в каждом периоде при одинаковом распределении нуклеотидов по длине каждого периода. Под периодами длины п понимаются расположенные друг за другом фрагменты ДНК одинаковой длины Пусть нам дана последовательность ЗЧзд ..¡ь, которая содержит символы из алфавита 0={а,1,с,§}. Периоды в ней можно получить, если последовательность ДНК разбить на чередующиеся друг за другом фрагменты длины п. Вначале символ F ставится на нулевую позицию и на ¿+/ позицию последовательности 5. Затем отсчитывается и нуклеотидов, начиная с первой позиции последовательности 5, после чего ставится еще один символ Р, и так до конца последовательности В результате получаем последовательность .S-F.Sj.S2. ¡^¡„+¡¡„^2...

ИпР.....¡¿Р. Затем формируется последовательность категорий посредством замены символа

на ноль, а других символов - на единицу, и подсчитывается число серий. Под серией понимается последовательность символов одного типа, ограниченная символами другого типа, либо началом или концом последовательности. Например, последовательность 000111 содержит две серии, как и последовательность 01.

Если число нуклеотидов в каждом периоде (последовательности между символами Р) будет одинаковым или близким для каждого типа нуклеотидов, и одновременно с этим нуклеотиды будут наблюдаться примерно в одних и тех же позициях каждого периода, то будем говорить о том, что последовательность 5 обладает регулярностью. Фактически, наличие регулярности означает, что распределение некоторого нуклеотида по последовательности такое же, как и распределение символа /•". Для определения количественной меры регулярности последовательности ДНК используется критерий серий.

Пример расчета числа серий приведен на рис. 1, где последовательность ДНК разбивается на периоды длиной 3 при помощи символа Р.

A. Последовательность аа^с^^Лассс^сааааас

12345678 Номера периодов FaatFcctFtttFctaFcccFttcFaaaFaacF ДНК последовательность 011 0 0 0 1 0 0111011 0 последовательность категорий 0110001001110110 - Э серий

Б. Периодическая последовательность а1;са1:са1;са1са1:са1:са1;са1:с

12345678 Номера периодов

Га1:сЕа1:сГаСсРаСсЕа1сГаСсГа1:сЕа1:сГ ДНК последовательность 01 01 01 01 01 01 01 01 0 последовательность категорий 01010101010101010 - 17 серий

B. Периодическая последовательность с делецией нуклеотида с в третьем периоде а!са1са1а1;са1ха(:са(:са1:са

12345678 Номера периодов Еа1сРаИсРа1аЕ1;саР1:саГ1:саГ):саГ1:саГ ДНК последовательность

01 01 01 10 10 10 10 10 10 последовательность категорий 010101101010101010 - 17 серий

Рис. 1. Применение критерия серий для определения неслучайности распределения аденина (а) по периодам длиной три основания Изучаемая последовательность разбивается на отдельные периоды посредством вставки буквы ^через каждые три основания, начиная с нулевой позиции последовательности. На периодической последовательности (Б) число серий будет всегда больше или равно, чем число серий па непериодической последовательности (А). Это позволяет использовать число серий как меру периодичности, слабо чувствительную к делециям и вставкам нуклеотидов. Это продемонстрировано на рисунке (В), где произведена делеция с в 9-й позиции периодической последовательности Видно, что число серий не изменилось при этом и осталось равным 17.

Для введения количественной меры создадим четыре последовательности категорий K(i) из последовательности S' Последовательность категорий K{i), j=1,2,3,4, создается из последовательности 5' путем замены F на 0 и символа q(i) на 1, остальные символы последовательности 5" при этом игнорируются. Здесь q(i) - символ алфавита Q. Для каждой из введенных последовательностей категорий рассчитывалось число серий m(i). Для определения статистической значимости полученного числа проводилось имитационное моделирование методом Монте-Карло. Для этого выполнялось случайное перемешивание символов исходной последовательности S, после чего для вновь полученной последовательности строилась S' и определялось число серий m(i), ¡-1,2,3,4. В результате применения метода Монте-Карло было получено N значений для числа серий m(i) для случайных последовательностей. После этого для полученного множества значений для каждого символа рассчитывалось среднее значение pr(i) и стандартное отклонение аг(0 Тогда формула расчета статистической значимости Z(i) числа серий m(i) будет иметь вид:

= (!) ffr(')

Выше было рассмотрено применение критерия серий для поиска регулярности одного нуклеотида в изучаемой последовательности. Однако, для проведения более полного сравнительного анализа последовательностей необходимо иметь возможность оценить регулярность по всем четырем символам одновременно. Для этого сначала производится вычисление статистики Z (формула (1)) для каждого из нуклеотидов в отдельности. Обозначим результаты для a, t, с и g как Z„, Z,, Zc и Zg, соответственно. Все указанные величины имеют распределение, близкое к нормальному (это было показано в результате проведения численного моделирования для случайных последовательностей) Воспользуемся свойством стандартного нормального распределения, чтобы получить новую суммарную величину, также распределенную нормально. Получаем:

Z„ +Z, + Z„ +Z„ Z +Z, +Z, +Z„

Z„„ = —--г1-- = —-1-i-- -ЩО'Л) (2)

V4 2

В результате сначала проводился расчет величины 2 для каждого из нуклеотидов по формуле (1), а затем рассчитывалось объединенное значение 2чт по формуле (2).

Поиск регулярности в пуклеотидной последовательности проводился следующим образом. Последовательность ДНК сканировалось с помощью окна длиной 500 нуклеотидов, что соответствовало длине изучаемых промоторов. Выбиралась длина периода п и для последовательности, попавшей в окно, создавались четыре последовательности (для каждого нуклеотида) путем введения символов К. Для каждой этих 4-х последовательностей определялось максимальное значение 2, как было описано выше. Затем для полученных значений 2„, 2,, 2С и 2% по формуле (2) определялось значение 2шт.

В пределах окна определялся максимум для значения 21Ю1 посредством варьирования границ изучаемой последовательности, а именно, правая и левая ее границы независимо изменялись с шагом 2, и каждый раз рассчитывалась статистика 2„т

Модифицируем приведенный выше пример - пусть последовательность .У имеет вид ^с§ааааПааасаааа§, S'=FtcgcgFaaaatFtaaacFaaaagF. В этом случае вариационный ряд для нуклеотида а будет иметь вид (0. 0. 1. 1. 1. 1. 0, 1. 1. 1. 0, 1. 1. 1. 1, 0}. Данный пример показывает, что при увеличении числа символов в каждом из периодов число серий не увеличивается. Для больших длин периода (>4) это может привести к тому, что некоторые последовательности, обладающие регулярностью, не будут выявлены.

В целях разрешения данной проблемы вносились дополнительные символы в последовательность 5" В результате все периоды последовательности 5 делятся на части (или «ящики», по аналогии с моделями, используемыми в комбинаторике) одинаковым образом. Для примера, показанного выше, последовательность 5" после внесения дополнительного символа ^ в каждый период может выглядеть как ^г/cgFcg/oaa/гaíFtoa^чзcFaaaFíгgF (жирным шрифтом выделены новые символы). Рассматривались все возможные позиции размещения новых символов, и выбиралось такое положение нового символа в периоде (во всех периодах идентично), которое обеспечивало наибольшее значение числа серий. Затем заново определялась статистическая значимость посредством имитационного моделирования методом Монте-Карло, как это было описано выше

В результате проведения имитационного моделирования было получено пороговое значение статистики критерия 2,„„,= 4 0. Данное значение гарантирует, что на исследуемом множестве промоторов будет найдено не более одной случайной последовательности, обладающей регулярностью.

«Схемой регулярности» называется схематичное изображение расположения символов F в последовательности, для которого распределение нуклеотидов оказалось наиболее неслучайным, то есть, значение 2тт для данной последовательности достигает максимальной величины. Например, приведенная ниже схема означает, что максимальное значение статистики критерия было получено для последовательности имеющей нуклеотид а в любой позиции периода с 1-го по 4-й нуклеотид, а также в любой из 5-й и 6-й позиций

периода. Нуклеотид с может наблюдаться в 1-3 позициях и в 4-6 позициях периода, символ 'Б' — в 1,2, 3-5 и в 6-й позициях периода. Нуклеотид I в исследуемой последовательности отсутствовал. Регулярность в данном случае наблюдается по трем символам - "ас§" при

длине периода в шесть нуклеотидов. г----г—г а

-Г-р д

В разделе 2.2 приведено описание алгоритма классификации периодичности последовательностей ДНК.

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

Рис. 2. Блок-схема классификации матриц скрытой периодичности.

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

Статистическая значимость объединения матриц обеспечивалась заданием порогового уровня для объединения в 95%. Это означает, что процесс объединения матриц автоматически заканчивается при подобии матриц в классах, составляющем менее чем 95%.

В разделе 2.3 приведено описание профильного анализа - основного алгоритма, использованного для поиска периодичности в последовательностях ДНК в условиях наличия вставок и делеций символов.

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

При проведении поиска периодических последовательностей в базе данных Genbank проводилось построение позиционно-специфичных матриц (ПСМ) частот нуклеотидов для каждого из классов периодичности, полученных ИР. В целях предотвращения искажений частот в изотипичных последовательностях (эффект неравномерного представления) было проведено взвешивание каждой последовательности обратно пропорционально числу последовательностей, имеющих с ней высокий уровень сходства Полученные ПСМ были преобразованы в позиционно-специфичные весовые матрицы (ПСВМ) по формулам: w\Sj) = AS,j)ia{f(S,j)/p(S)} (3)

w(S,j) = w'(.SJ)-w'(j) где S = {A,T,C,G}, f(S j) - элемент матрицы ПСМ, p(S) = £ f(S, j),

j

i^/) = 0.252>'(S,./)

s - средний вес нуклеотидов в j -м столбце ПСМ матрицы, w(S j) - вес

нуклеотида 5 в ПСВМ.

Для выравнивания анализируемой последовательности из Genbank относительно ПСВМ использовался динамический алгоритм нахождения локального подобия, также известный как алгоритм Смита-Уотермана (Smith-Waterman). Элементы матрицы выравнивания определялись по формулам:

F(i,J) - max{ max {/•(<-*,y)-v,(l + log(*))}; max -/)-vd(l+ l0g(/))};

\ik<,dmax \<.l<.dnt ax

F(I-U-1) + W(S(0J),0.0}; (4)

F( 0,0) = 0.0; F(i, 0) = F(0,0) - v„ (1 + Iog(i)); F( 0, j) = f (0,0) - v„ (1 + log (J))

где I - позиция нуклеотида в анализируемой последовательности, } - позиция в консенсусной последовательности, <1тах = 40 — максимальное анализируемое количество вставок и делений, IV = 1.0 - штраф за открытие делении и - элемент ПСВМ,

рассчитываемый по формулам (3), ОД - нуклеотид в г-н позиции анализируемой последовательности.

Сканирование базы СепЬапк с помощью ПСВМ проводилось с шагом в 20 оснований. Консенсус-последовательность, полученная на основе класса периодичности, воспроизводилась необходимое для соответствия длине максимальной подпоследовательности количество раз. На каждом шаге проводилось выравнивание анализируемой последовательности относительно ПСВМ Матрица заполнялась

полностью, затем определялся ее максимальный элемент /тах(кт , }„,). На основании положения /шах определялось оптимальное выравнивание как путь от максимального элемента до первого нулевого элемента, координаты которого обозначались как (ко , _/о).. Полученное выравнивание задает «максимальную подпоследовательность» при этом положение соответствующей ПСВМ отмечено нуклеотидами, имеющими больший вес.

Для определения статистической значимости найденного выравнивания последовательности из СепЬапк необходимо оценить вероятность существования выравнивания случайных последовательностей с тем же нуклеотидным составом относительной заданной ПСВМ Таким образом, заполнялась матрица по формулам

то есть, аналогично формулам (4), но без рассмотрения нулевых значений при выборе максимума. Далее рассчитывалась величина с1 =/(кт , ]т) - /(ко, Jo), распределение которой при использовании данных формул близко к нормальному. Данная гипотеза была подтверждена путем проведения имитационного моделирования (метод Монте-Карло). При этом было сгенерировано 100 последовательностей с тем же символьным составом, что и в рассматриваемой последовательности (то есть, с теми же частотами появления символов и триплетной корреляцией), а затем матрица Р' была заполнена для каждой последовательности.

В качестве меры статистической значимости было определено 2-значение, то есть, нормализованное отклонение веса найденного выравнивания анализируемой последовательности от среднего веса выравниваний случайных последовательностей относительно ПСВМ:

где IV - вес найденного выравнивания, И^ - вес выравнивания случайной последовательности, М и а - среднее значение и стандартное отклонение соответственно.

Г0,7) = шах{ шах {5"(/-*,./)-^(1 + 1о6(А))}; шах {¿"(,,7-/)-^(1 + 1о§(/))};

\<1<1>тах 1 <1<Лпшх

^ '(0,0) = 0.0; ^'(', 0) = Г '(0,0) - V, (1 + 1оё(0); Р(0, Л = Р '(0,0) - V, (1 + 1о20)),

\<1<атах

(5)

(6)

Поскольку МПА обеспечивает статистическую значимость подобия последовательностей, а не их периодичность, были проведены дополнительные статистические испытания последовательностей, обнаруженных с помощью данного алгоритма. Вначале рассчитывался спектр ИР для всех последовательностей. Затем был использован метод Монте-Карло для оценки статистической значимости, а именно, для каждой последовательности было сгенерировано 200 последовательностей путем случайного перемешивания ее символов, рассчитаны значения средней величины, дисперсии и, наконец, 2-значение, как это было описано выше. Считалось, что рассматриваемая последовательность является периодической с заданной длиной периода, если соответствующее этой длине значение Ъ было максимальным в спектре ИР при дополнительном условии 2>=7.0. Использование данного критерия позволяет утверждать, что последовательность, ему удовлетворяющая, обладает периодичностью с заданной длиной периода на статистически значимом уровне.

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

Разработанное программное обеспечение представляет собой, комплекс, состоящий из собственно базы данных (информации, хранимой в виде таблиц), системы управления базой данных (СУБД), программных компонент обработки запросов к базе данных, программных средств ведения базы данных и веб-интерфейса пользователя.

База данных по потенциальным мини- и микросателлитным последовательностям содержит следующую информацию: участки ДНК, обладающие скрытой периодичностью; координаты последовательностей в соответствующем локусе (участке последовательности с уникальным идентификатором) ОепЬапк, тип и параметры найденной периодичности. Обеспечивается возможность поиска последовательностей по различным параметрам, получения информации о наличии подобных последовательностей на некотором заранее заданном участке ДНК, просмотра результатов запросов посредством веб-обозревателя и сохранения результатов запроса в локальный файл на компьютере пользователя. Веб-интерфейс пользователя реализован в виде Интернет-страницы. Дашгая страница содержит элементы, обеспечивающие возможность создания запросов к базе данных и отображения результатов запросов. Также поддерживается возможность сохранения результатов запроса в файл на компьютере пользователя. Взаимодействие программных компонентов в виде диаграммы потоков данных представлено на рис. 3.

Хранилище данных

Рис.3. Взаимодействие программных компонентов (ПК) и подсистем (ПС) базы данных.

В разделе 2.5 описаны методы создания веб-сервера поиска скрытой периодичности. Веб-сервер LEPSCAN (LAtent Periodicity SCANner) позволяет осуществлять поиск скрытой периодичности, тип которой относится к заранее определенному множеству классов. Классы были получены для различных групп организмов и различных длин периода с помощью алгоритмов, описанных в разделе 2.2. Основным алгоритмом, используемым при сканировании последовательности в целях выявления скрытой периодичности, является МПА. Сервер реализован на платформе openSuse Linux 10.0; для проведения вычислений используется суперкомпьютер с кластерной архитектурой, состоящий из 114 блоков, укомплектованных процессорами AMD Opteron и Pentium. Проведение параллельных вычислений реализовано с помощью технологии MPI (Message Passing Interface) с использованием системы очередей Cleo [13] Веб-интерфейс пользователя реализован на основе технологии CGI (Common Gateway Interface) Также с использованием этой технологии реализован доступ к базе данных, содержащей классы периодичности. Язык реализации - Perl. Основной вычислительный модуль реализован на языке С++ с использованием MPI, вспомогательные программы представляют собой Рег1-сценарии (скрипты). Базы данных реализованы под управлением СУБД PostgreSQL версии 8.04. Диаграмма потоков данных представлена на рис.4.

Хранил «-ило «З-холн^хд-эким*

о х о ^ a. s

Пол система

jdTyÛ^ 3*1/134

10

ё н

Хранилище классса периодично*.?«

формирования и ? пт)рче?|«и вы*одчы* ! данных |

H.iSop у/иесо»

Уграэпяошие инструкции

Статус

Б ычислительиы й м-эдуяь

Рис. 4. Диаграмма потоков данных программного комплекса LEPSCAN.

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

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

В разделе 3.1 приведены результата поиска регулярных последовательностей в эукариотических промоторах из базы данных EPD [14] версии 93 (общее количество последовательностей, содержащихся в базе - 4809). Было выбрано 2236 последовательностей, представляющих все группы организмов, при этом уровень подобия любых двух последовательностей из этого множества составлял не более 50% (опция базы данных).

При поиске ре1улярности были использованы следующие параметры сканирования, размер окна=500, шаг внутри окна=2 Длина обнаруживаемых регулярных последовательностей находилась в диапазоне 50-500 нуклеотидов. В 1342 промоторах была выявлена регулярность на статистически значимом уровне. Таким образом, более 60% промоторов содержат последовательности с регулярной структурой в диапазоне длин от 2 до 16 нуклеотидов. Регулярность в остальных промоторных последовательностях также была обнаружена, но уровень статистической значимости для этих последовательностей был меньше порогового.

Важным для понимания биологической значимости регулярности является изучение распределения местоположения регулярных последовательностей в промоторах. Длина промотора была разбита на интервалы длиной 10 нуклеотидов, после чего определялось число последовательностей, попавших в каждый из этих интервалов. Было использовано имитационное моделирование (метод Монте-Карло) для определения, является ли распределение регулярных последовательностей случайным Для этого все найденные регулярные последовательности 200 раз размещхтись случайным образом но длине промотора.

На основе полученных данных для каждого интервала были рассчитаны среднее значение и дисперсия, после чего для каждого интервала рассчитывалось значение Z с помощью формулы (1). Число регулярных последовательностей, найденных в интервале с 400 по 500 нуклеотид (от -99 до +1 относительно начала гена), заметно превышает уровень, ожидаемый для случайных последовательностей. При этом наибольшее превышение наблюдается для мест связывания факторов транскрипции и РНК-полимеразы (-45, +5). Начиная с -100-ого нуклеотида, значение Z превышает уровень 5.0. Кроме того, в интервалах с -389 по -169 нуклеотид наблюдалось отклонение значений Z в отрицательную сторону, что связано с преимущественной локализацией районов с регулярностью в интервале с -99 по +1 нуклеотид.

Тестирование разработанного алгоритма показало, что он способен выявлять как явную, так и скрытую периодичность со сравнительно небольшим числом делеций или вставок. Однако, используемый подход может пропустить длинные вставки нуклеотидов в район ДНК с имеющейся регулярностью В этом случае последовательности категорий К(г) могут содержать достаточно большое количество пустых «ящиков», что будет приводить к заметному снижению статистической значимости района регулярности с протяженной вставкой Такое явление может быть причиной того, что в ряде промоторных последовательностей регулярность в районе (-99, +1) была обнаружена при значениях Z<4.0.

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

В целом проведенные расчеты показывают, что регулярное строение является неотъемлемым свойством промоторных районов ДНК.

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

Ниже представлены основные результаты классификации для длин периодов 2,4 и 5.

Таблица 1. Результаты классификации для длин периода 2, 4, 5. Верхнее значение соответствует число обнаруженных периодических последовательностей, а нижнее значение

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

Группа организмов / 2 4 5

Длина периода

Бактерии 454 883 867

45 34 25

Беспозвоночные 29430 17966 6113

199 73 62

Вирусы и фаги 306 171 136

29 12 8

Грызуны 131265 107013 12821

211 189 135

Позвоночные 17170 17536 3601

136 120 88

Приматы 168164 107297 10736

188 174 329

Растения 14766 8170 2107

141 160 131

Как видно из таблицы, число классов значительно меньше числа исходно обнаруженных периодических последовательностей - от 10 раз для небольшого числа исходных последовательностей до 100 и более раз для большого количества периодичностей, обнаруженных посредством использования информационного разложения. Таким образом, вторая цель проведения классификации (сокращение числа исходных данных для профильного анализа без потери их представительности), очевидно, достигнута. Рассмотрим теперь, каким образом полученные классы отражают общие закономерности периодичности соответствующих групп организмов. В качестве примера рассмотрим классификацию динуклеотидной (длина периода = 2) периодичности геномов растений. Более половины последовательностей попало в три самых больших класса (содержащих 3391, 2285 и 1951

последовательность, соответственно) Следовательно, свойства периодичности, определяемые этими классами, являются общими для большого числа последовательностей.

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

АЛ Т1 С1 G1 А2 Т2 С2 G2

1 31 0 0 31 0 0 0

1 2

Л 0,016 0,492

т 0,492 0,000

с 0,000 0,000

г. 0,000 0,000

Рис. 5. Матрица класса (в виде вектора и в нормализованной форме), включившего наибольшее число периодических последовательностей из геномов растений.

Очевидно, что в первой позиции преобладает тимин, а во второй - аденин. Таким образом, условный консенсус для данного периода можно записать в виде {t}{a¡. Рассмотрим теперь второй класс по числу элементов. Он имеет консенсус {a, g}{t}, причем частота гуанина меньше частот аденипа и тимина. Третий по численности класс имеет консенсус {c}{t}, то есть, он отличается от предыдущих двух классов. Мотив АТ является наиболее часто встречаемым в микросателлитах растений, что подтверждается полученными нами результатами. В геномах Oryza sativa и Arabidopsis thahana преобладает мотив GA. Последовательности данных геномов составляют существенную часть Genbank (около 50% от длины всех растительных геномов), и число обнаруженных в них периодических последовательностей также велико. Следовательно, наличие большого класса с тем же консенсусом (СТ является комплементарным по отношению к GA) согласуется с данными, полученными экспериментально.

В разделе 3.3 приведены результата поиска микросателлитных последовательностей ДНК посредством модифицированного профильного анализа.

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

Таблица 2. Результаты поиска скрытой периодичности алгоритмами ИР (верхнее значение в каждой ячейке) и МПА (нижнее значение) в геномах растеши"! и бактерий.

Группа организмов / 2 4 5

Длина периода

Бактерии 454 883 867

6593 7242 3732

Растения 14766 8170 2107

80396 32165 8132

Рассмотрим подробнее результаты поиска дииуклеотидной периодичности в геномах растений. Был проведен поиск скрытой периодичности посредством МПА для 141 класса, полученного ранее. Каждая из матриц классов была использована для поиска во всех последовательностях ДНК из геномов растений, представленных в Genbank. При этом использовалось пороговое значение уровня значимости Z, равное 7.0, обеспечивающее неслучайность данного поиска. Число найденных неперекрывающихся последовательностей составило 103556. После фильтрации, проведенной согласно процедуре, описанной в разделе 2.2., число последовательностей составило 80396. Как и в случае бактерий, число полученных последовательностей намного превосходит исходное значение (14766).

Рассмотрим распределение числа периодических последовательностей, принадлежащих некоторым функциональным элементам. Геномы растений имеют намного больший размер, чем геномы бактерий или дрожжей, что сильно затрудняет проведение их аннотации (определение функциональной значимости участков генома) с помощью экспериментальных методов. Поэтому вполне ожидаемым является тот факт, что большинство найденных периодических последовательностей (более 57000) были обнаружены в ранее неаннотированных участках генома. Таким образом, подтверждается возможность проведения аннотации с помощью используемых алгоритмов Также следует отметить, что более 7000 последовательностей перекрываются с повторами, ранее обнаруженными экспериментально. Небольшое количество периодов с длиной два нуклеотида в генах (на эти области приходится около 12% найденных последовательностей) позволяет сделать вывод о предпочтительности формирования участков с размытой периодичностью в некодирующих областях

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

В разделе 3.4 рассмотрена реализация базы данных потенциальных микро- и минисателлитных последовательностей. MMsat представляет собой аналитическую базу данных по скрытой периодичности в последовательностях Genbank. Последовательности, обладающие скрытой периодичностью с длиной периода 2-100, могут рассматриваться как потенциальные микро- и мшшсателлиты. База данных размещена в свободном доступе в сети Интернет по адресу http://victoria.biengi.ac.ru/mmsat. Языки интерфейса - русский и английский.

В качестве результатов запроса пользователь может увидеть локализацию потенциальных микро- и минисателлитных последовательностей, а также спектр статистической значимости полученных последовательностей.

База данных содержит 2851428 последовательностей, обладающих скрытой периодичностью. Распределение последовательностей по длине периода представлено в табл.3.

Таблица 3 Распределение количества последовательностей, содержащихся в базе данных, по длине периода.

Длина периода 2 3 4 5 6 1 8 9 10

Число последовательностей 366739 1323348 261544 36553 87649 22973 54555 16954 26397

Длина периода 11-20 21-50 51-80 81100

Число последовательностей 133337 269863 196295 60085

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

Для того, чтобы выполнить поиск в базе, необходимо заполнить значения всех желаемых параметров (любой из них можно оставить незаполненным) и нажать кнопку 'Послать запрос'.

В разделе 3.5 рассмотрена программная реализация веб-сервера поиска скрыгой периодичности ЬЕРЗСАЫ (ЬПр:/Лчс1опа.Ыеп§1 ac.ru/lepscan).

Для работы с сервером необходимо задать последовательность, в которой будет осуществляться поиск периодичности (обязательно), адрес электронной почты (обязательно), а также заполнить значения желаемых параметров (любой из них можно оставить незаполненным), после чего нажать кнопку 'Послать запрос'. Результаты поиска высылаются на указанный адрес электронной почты в течение 24 часов в виде 7.1р-архива, содержащего данные по найденным периодическим участкам исходной последовательности, заданной пользователем. Каждой длине периода соответствует один файл результата, содержащийся в архиве. Формат имени файла в архиве - РЕК[длина_периода]_Гша). Исходная последовательность также находится в архиве в файле РООО.

Поиск потенциальных микро- и минисателлитиых последовательностей можно производить с использованием задаваемых пользователем параметров; группы организмов (соответствуют группам, используемым в базе данных ОепЬапк) и длины периода (возможные значения 2-20). Поиск осуществляется с использованием классов периодичности, полученных для соответствующих длин периода и групп организмов

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

Заключение

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

1 Разработан и программно реализован алгоритм классификации скрытой периодичности в последовательностях оснований нуклеиновых кислот; проведена классификация периодических последовательностей ДНК из банка данных СепЬапк для различных длин периода и групп организмов

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

3. Создана база данных по потенциальным мини- и микросателлитным последовательностям ДНК на основе результатов выявления скрьггой периодичности в геномах различных организмов с помощью разработанных алгоритмов.

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

5. Разработан и программно реализован алгоритм поиска регулярности последовательностей нуклеиновых кислот, основанный на использовании критерия серий

6. Разработанный алгоритм применен для поиска регулярности в последовательностях промоторов из различных геномов.

Список литературы

1. Tolh G„ Caspari Z, Jurka J. Microsalelhtes m different eukaryotic genomes: survey and analysis // Genome Res. - 2000. - Vol. 10. - P. 967-981

2. Mishra D., Thangaraj K„ Mandham A , Kumar A , Mutal R. Is reduced CAG repeat length in androgen receptor gene associated with risk of prostate cancer in Indian population? // Clin. Genet. - 2005. - Vol. 68, No 1 -P. 55-60.

3 \lakeev V.Y, Frank G K., Tumanyan VG. Statistics of periodic patterns in the sequences of human introns // Biophysics. - 1996. - Vol. 41. No 1. - P. 263-268.

4 Chechetkm V.R., Lobzin V V. Levels of ordering in coding and noncoding regions of DNA sequences // Phys. Lett. A -1996 - Vol. 222. -P 354-360

5. Benson G. Tandem repeats finder: a program to analyse DNA sequences // Nucleic Acids Res. -

1999.-Vol.27.-P. 573-580. 6 HerzelH, Trifonov E N.. IVeiss О, Grobe I Interpreting correlations in biosequcnces // Physica A.-1998 - Vol.249. - P.449-459.

7. Korotkov E V., Korotkoxa M.A., Kudryashov N.A Information decomposition method to analyze symbolical sequences // Phys. Let. A. - 2003. - Vol. 312. - P.198-210.

8. Landau G„ Schmidt J., Sokol D. An algorithm for approximate tandem repeats I! J. Сотр. Biol. -2001 - Vol. 8.-P. 1-18.

9. Rice P., Longden I., Bleasby A EMBOSS: The european molecular biology open software suite // Trends Genet. - 2000. - Vol. 16. - P. 276-277.

10. Subramaman S, Mishra R.K., Singh L Genome-wide analysis of microsatellite repeats in humans: their abundance and density in specific genomic regions // Genome Biol - 2003. - Vol.

4, No. 2. - P R13

11. Bajic V.B. et al. Promoter prediction analysis on the whole human genome // Nat. Bioteclinol. -2004 - Vol 22.-P 1467-1473.

12. Xie X., Wu S., Lam К-M, Yan H. PromoterExplorer an effective promoter identification method based on the AdaBoost algorithm // Bioinformatics. - 2006. - Vol. 22. - P. 2722-2728.

13. Воеводин Вл. В, Жуматий С.А. Вычислительное деле и кластерные системы. - М: Изд-во МГУ, 2007.- 150 с.

14 Schmid C.D., Perier R, Praz Г., Bucher P. EPD in its twentieth year- towards complete promoter coverage of selected model organisms // Nucleic Acids Res. - 2006. - Vol 34. - D82-

5.

Основные положения диссертации изложены в публикациях:

1. Шеленков А.А, Коротков Е В Классификация скрытой периодичности нуклеотидных последовательностей из банка данных Genbank // Материалы 8-й Пущинской школы-конференции молодых ученых «Биология - наука XXI века» - Пущино. - 2004. - С. 245.

2. Shelenkov А.А., Chaley М В, Korotkov E.V. Revelation and classification of dmucleotide periodicity of bacterial genomes using the methods of information decomposition and modified profile analysis // Proceedings of the International Conference on Bioinformatics of Genome Regulation and Structure - Novosibirsk. - 2004. - Vol 2. - P. 293-296.

3 Shelenkov A A, Chaley M.B., Korotkov E.V. Revelation and classification of dinucleotide periodicity of bacterial genomes using the method of information decomposition // Материалы 9-й Пущинской школы-конференции молодых ученых «Биология - наука XXI века». - Пущино. -2005. - С. 323.

4 Шеленков А А. Классификационный анализ скрытой периодичности последовательностей оснований нуклеиновых кислот // Материалы международной школы-конференции молодых ученых «Системная биология и биоинженерия». — Звенигород. - 2005. - С. 92-93.

5. Shelenkov A A., Korotkov E.V. Search and Classification of Potential Minisatellite Sequences from Bacterial Genomes // Доклады I Международной конференции «Математическая биология и биоинформатика». - Пущино. - 2006. - С. 187-188.

6. Шеленков А.А, Коротков Е.В. Поиск регулярных последовательностей в эукариотичсских промоторах // Доклады II Международной конференции «Математическая биология и биоинформатика». - Пущино. - 2008. - С. 94-95.

7 Шеленков А.А LEPSCAN - веб-сервер поиска скрытой периодичности // Доклады II Международной конференции «Математическая биология и биоинформатика». - Пущино -2008.-С. 100-101.

8 Shelenkov А А, Chaley М.В., Skryabin K.G., Korotkov E.V. Revelation and classification of dinucleotide periodicity of bacterial genomes using the method of information decomposition / Bioinformatics of Genome Regulation and Structure II. Eds . Kolchanov N , Hofestaedt R., Milanesi L. - New-York: Springer Science+Business Media Inc. - 2006. - P. 179-188.

9. Shelenkov A. A., Skryabin K.G., Korotkov E.V. Search and Classification of Potential Minisatellite Sequences from Bacterial Genomes // DNA Res. - 2006. - Vol. 13, No. 3. - P. 89-102.

10. Шеленков A A, Скрябин К.Г., Коротков Е.В. Классификационный анализ скрытой динуклеотидной периодичности геномов растений II Генетика. - Т. 44, №1. - С.120-136.

10а. Shelenkov A. A., Skryabin К. G., Korotkov Е. V. Classification Analysis of a Latent Dinucleotide Periodicity of Plant Genomes // Rus. J. Genet. - 2008. - Vol. 44, No. 1. - P. 101-114.

11. Shelenkov A A., Korotkov A.E, Korotkov E.V. MMsat - a database of potential micro- and minisatellites // Gene. - 2008 - Vol. 409, No. 1-2 -P.53-60.

12. Шеленков А А., Коротков Е.В Поиск регулярных последовательностей в промоторах из геномов различных групп организмов с использованием критерия серий // Математическая биология и биоинформатика. - 2008. - Т .3, №1. - С. 1-15.

Подписано в печать 20Л 0 2008 г.

Печать трафаретная

Заказ №999 Тираж: 100 экз.

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР МАТЕМАТИЧЕСКИХ МЕТОДОВ АНАЛИЗА НУКЛЕОТИДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ИХ КОМПЬЮТЕРНОЙ РЕАЛИЗАЦИИ.

1.1 Структурная организация последовательностей ДНК.

1.2 Математические методы поиска микросателлитных последовательностей.

1.3 Математические методы классификации периодических последовательностей ДНК.

1.4 Базы данных микросателлитных последовательностей ДНК.

1.5 Веб-серверы поиска микросателлитных последовательностей.

1.6 Периодичность бактериальных и растительных геномов и промоторных районов ДНК, обнаруженная существующими методами.

ГЛАВА 2. РАЗРАБОТКА НОВЫХ АЛГОРИТМОВ И ПРОГРАММ ДЛЯ ВЫЯВЛЕНИЯ РЕГУЛЯРНОСТИ В ПОСЛЕДОВАТЕЛЬНОСТЯХ ДНК.

2.1 Разработанные алгоритмы.

2.1.1. Алгоритм выявления регулярности последовательностей ДНК.

2.1.2 Алгоритм тассификации периодичности последовательностей ДНК.

2.1.3 Алгоритм модифицированного профильного анализа для выявления скрытой периодичности в последовательностях ДНК.

2.2 Использованные методы.

2.2.1 Методы создания базы данных скрытой периодичности последовательностей ДНК.

2.2.2 Методы создания веб-сервера для поиска скрытой периодичности в последовательностях ДНК.

ГЛАВА 3. РЕЗУЛЬТАТЫ И ОБСУЖДЕНИЕ ПРИМЕНЕНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ПРОГРАММ.

3.1 Регулярность строения промоторных участков ДНК.

3.2 Классификация скрытой периодичности последовательностей ДНК.

3.3 Выявление микросателлитных. последовательностей алгоритмом модифицированного профильного анализа.

3.4 База данных скрытой периодичности последовательностей ДНК.

3.5 Программная реализация веб-сервера для поиска скрытой периодичности последовательностей ДНК.

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

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

В конце XX века с появлением новых технических средств такие области науки как молекулярная биология и генетика вышли на совершенно новый уровень. Рост объемов получаемых биологических данных, в частности, последовательностей геномов различных организмов, приобрел экспоненциальный характер. С наступлением нового века эта тенденция сохранилась. Основным носителем наследственной информации являются молекулы дезоксирибонуклеиновой кислоты (ДНК), представляющих собой двойную спираль, состоящую из двух цепочек азотистых оснований — нуклеотидов. Объем наиболее известного банка данных последовательностей ДНК - Genbank - превышает 85 млрд. нуклеотидов (для сравнения - длина генома человека составляет около 3 млрд. нуклеотидов, высших растений - около 300 млн., бактерий - 3 млн.), при этом в среднем каждые 15 месяцев происходит его удвоение.

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

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

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

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

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

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

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

• создана база данных по потенциальным мини- и микросателлитным последовательностям ДНК на основе результатов выявления скрытой периодичности в геномах различных организмов;

• разработан Интернет-сервер для поиска скрытой периодичности;

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

• разработанный алгоритм применен для выявления регулярности в последовательностях ДНК.

Научная новизна работы.

• Разработан новый алгоритм выявления и классификации скрытой периодичности в последовательностях ДНК.

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

• Разработана база данных, содержащая около 3 млн. последовательностей, обладающих скрытой периодичностью с периодом 2-100, для всех групп организмов.

• Разработан веб-сервер для поиска скрытой периодичности, реализующий новый алгоритм выявления скрытой периодичности.

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

Достоверность результатов работы подтверждена проведенными исследованиями последовательностей ДНК из банков данных Genbank и EPD и сравнением с экспериментальными данными.

Апробация работы. Основные результаты и положения диссертации докладывались на международных конференциях «Биология - наука XXI века», Пущино, в 2004 (17-21 мая) и 2005 (18-22 апреля) гг., Bioinformatics of genome regulation and structure (Новосибирск, 25-30 июля 2004 г.), I и II международной конференции «Математическая биология и биоинформатика» (Пущино, 9-15 октября 2006 г. и 7-13 сентября 2008 г.), российско-французском научном симпозиуме по аннотации бактериальных геномов (Тулуза, Франция, 5-6 октября 2006), на международной школе-конференции молодых ученых «Системная биология и биоинженерия» (Звенигород, 28 ноября — 2 декабря 2005 г.), а также на ежегодных конкурсах-конференциях аспирантов и сотрудников Центра «Биоинженерия» РАН в 2004-2008 годах.

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

На защиту выносятся

• Алгоритм эффективной классификации скрытой периодичности в последовательностях оснований нуклеиновых кислот.

• Алгоритм поиска сильно размытой периодичности в условиях наличия вставок и делеций символов с использованием классов периодичности.

• База данных по потенциальным мини- и микросателлитным последовательностям ДНК.

• Веб-сервер для выявления скрытой периодичности.

• Алгоритм выявления регулярности последовательностей ДНК.

• Результаты поиска регулярных последовательностей в геномах различных организмов.

Краткое содержание работы.

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

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

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

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

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

Приведено описание алгоритма классификации периодичности последовательностей ДНК. В качестве класса периодичности рассматривается матрица частот нуклеотидов в различных позициях периода. Описан алгоритм классификации и представлена оценка вероятности попадания в получаемые классы случайных последовательностей.

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

Рассмотрены методы создания базы данных скрытой периодичности, приведено описание ее структуры и принципов функционирования.

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

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

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

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

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

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

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

1. Шеленков А.А, Коротков Е.В. Классификация скрытой периодичности нуклеотидных последовательностей из банка данных Genbank // Материалы 8-й Пущинской школы-конференции молодых ученых «Биология — наука XXI века». — Пущино. - 2004. - С. 245.

2. Shelenkov А.А., Chaley М.В., Korotkov E.V. Revelation and classification of dinucleotide periodicity of bacterial genomes using the methods of information decomposition and modified profile analysis // Proceedings of the International Conference on Bioinformatics of Genome Regulation and Structure. - Novosibirsk. - 2004. - Vol. 2. - P. 293-296.

3. Shelenkov A.A., Chaley M.B., Korotkov E.V. Revelation and classification of dinucleotide periodicity of bacterial genomes using the method of information decomposition // Материалы 9-й Пущинской школы-конференции молодых ученых «Биология - наука XXI века». — Пущино. - 2005. - С. 323.

4. Шеленков А.А. Классификационный анализ скрытой периодичности последовательностей оснований нуклеиновых кислот // Материалы международной школы-конференции молодых ученых «Системная биология и биоинженерия». — Звенигород. - 2005. - С. 92-93.

5. Shelenkov A. A., Korotkov E.V. Search and Classification of Potential Minisatellite Sequences from Bacterial Genomes // Доклады I Международной конференции «Математическая биология и биоинформатика». - Пущино. - 2006. - С. 187-188.

6. Шеленков А.А., Коротков Е.В. Поиск регулярных последовательностей в эукариотических промоторах // Доклады II Международной конференции «Математическая биология и биоинформатика». — Пущино. — 2008. - С. 94-95.

7. Шеленков А.А. LEPSCAN - веб-сервер поиска скрытой периодичности // Доклады II Международной конференции «Математическая биология и биоинформатика». — Пущино. - 2008. - С. 100-101.

8. Shelenkov А.А., Chaley М.В., Skryabin K.G., Korotkov E.V. Revelation and classification of dinucleotide periodicity of bacterial genomes using the method of information decomposition /

Bioinformatics of Genome Regulation and Structure II. Eds.: Kolchanov N., Hofestaedt R., Milanesi L. - New-York: Springer Science+Business Media Inc. - 2006. - P. 179-188.

9. Shelenkov A.A., Skryabin K.G., Korotkov E.V. Search and Classification of Potential Minisatellite Sequences from Bacterial Genomes // DMA Res. - 2006. — Vol. 13, No. 3. - P. 89-102.

10. Шеленков А.А., Скрябин К.Г., Короткое E.B. Классификационный анализ скрытой динуклеотидной периодичности геномов растений //Генетика. - Т. 44, №1. - С.120-136.

10а. Shelenkov A. A., Skryabin К. G., Korotkov Е. V. Classification Analysis of a Latent Dinucleotide Periodicity of Plant Genomes // Rus. J. Genet. - 2008. - Vol. 44, No. 1. - P.101-114.

11. Shelenkov A.A., Korotkov A.E., Korotkov E.V. MMsat - a database of potential micro- and minisatellites // Gene. - 2008. - Vol. 409, No. 1-2. - P.53-60.

12. Шеленков А.А., Коротков E.B. Поиск регулярных последовательностей в промоторах из геномов различных групп организмов с использованием критерия серий // Математическая биология и биоинформатика. — 2008. - Т .3, №1. - С. 1-15.

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

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

Для выявления периодических последовательностей разработаны разнообразные математические методы, использующие преобразование Фурье, динамическое программирование и некоторые комбинаторные алгоритмы. Одними из лучших программ поиска тандемных повторов являются Tandem Repeat Finder [30] и MREPS [58]. Однако у всех ранее разработанных алгоритмов есть достаточно серьезные ограничения по выявлению периодичности в нуклеотидных последовательностях.

Основным недостатком использования преобразования Фурье при поиске периодичности в символьных последовательностях является необходимость перекодировки символьной последовательности в числовую. Эту перекодировку можно рассматривать как введение разных весов для равноправных символов, что в конечном итоге может приводить к невозможности обнаружения некоторых типов периодичности при использовании преобразования Фурье [20]. Кроме того, такие методы не способны обнаруживать периодичности при наличии вставок и делеций и они не дают возможность получить матрицу или некоторую другую характеристику типа периодичности, которая могла бы использоваться в дальнейших вычислениях.

При использовании динамического программирования и некоторых других подходов серьезным ограничением для выявления периодичности является поиск идентичных совпадений символов между последовательностями при выявлении повторов. Под идентичными совпадениями понимаются совпадения вида s(i)s(i), i=l, .,h, где s(i) — символ алфавита последовательности, h — размер алфавита символьной последовательности. В случае динамического программирования поиск преимущественно идентичных повторов задается при помощи весовой матрицы совпадений символов. Для аминокислотных последовательностей в качестве такой матрицы выступают РАМ или же BLOSUM, а для нуклеотидных последовательностей это матрица идентичности (Identity matrix) или подобные ей матрицы. В этих матрицах веса идентичных совпадений (аа, tt,cc,gg для нуклеотидной последовательности) значительно выше, чем веса всех других видов парных совпадений. Это приводит к тому, что сильно размытые повторяющиеся последовательности, которые можно обнаружить на статистически значимом уровне только при наличии в последовательности многих периодов (>2). не могут быть выявлены этими методами [20]. Образование таких последовательностей в реальной ДНК может происходить посредством множественных замен оснований, а также путем образования делеций и вставок символов.

Программы поиска тандемных повторов в геномных последовательностях, представленные в пакете EMBOSS [59], находят только те повторы, которые принадлежат к ограниченному множеству возможных типов периодичности (некоторые микросателлиты). Другая группа используемых при поиске периодичности алгоритмов предназначена для осуществления непрямого поиска с использованием методов сжатия данных. Алгоритм [60] обнаруживает «простые последовательности», то есть, некоторую смесь заданных заранее фрагментов. Простые последовательности могут как содержать, так и не содержать тандемные повторы, кроме того, в этом алгоритме не делается попыток определить повторяющийся элемент. Некоторые алгоритмы демонстрируют сильную чувствительность к наличию вставок н делеций, таким образом, они могут обнаруживать только повторы, подчиняющиеся очень строгим правилам [61, 62].

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

1.3 Математические методы классификации периодических последовательностей ДНК

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

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

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

В работе [63] классификация применялась в основном для выявления различий между штаммами бактерий, но также использовалась для дифференциации триплетной периодичности, присущей этим штаммам. В качестве меры была использована взаимная информация, представляющая собой взвешенную сумму всех 16 возможных корреляционных функций для четырех нуклеотидов. Мера рассчитывалась по формуле: п п а Р где ра, p[i - независимые частоты появления символов в позициях i и j, рар (к) - условная вероятность появления символа а в позиции / при условии, что символ Р находится в позиции] = i + к, п=4 (число символов в алфавите последовательности).

В работе [64] предпринята попытка критической оценки различных методов сжатия данных, используемых в качестве аппроксимации Колмогоровской сложности двух сравниваемых последовательностей. Колмогоровская сложность К(х.у) пары последовательностей х и у — это длина самой короткой программы, которая может породить эти последовательности, а также метод их различения. В частности, обсуждается универсальная метрика подобия, определяемая для двух объектов х иу как

37) max{£(x),iCO;)} где х*.^* - самая короткая программа, которая может породить х и у, соответственно, при отсутствии входных данных.

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

В работе [66] представлена программа для поиска и классификации коротких и длинных рассеянных повторов (SINE и LINE). При поиске производится определение участков с высокой консервативностью нуклеотидного состава путем расчета позиционно-специфичных матриц вероятностей. Элементами таких матриц являются вероятности появления каждого нуклеотида в каждой позиции сканирующего окна, рассчитанные с использованием Марковской модели нулевого уровня. Собственно классификация выполняется с помощью нейронной сети, обучение которой проводится на множестве уже известных повторов, обнаруженных экспериментально.

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

1.4 Базы данных микросателлитных последовательностей ДНК

На данный момент существует достаточно большое количество свободно доступных баз данных по тандемным повторам. Среди этих баз встречаются содержащие как экспериментальные данные, так и результаты, полученные применением математических методов, основанных на динамическом программировании или же некоторых комбинаторных алгоритмах. Наиболее известными являются база данных мини- и микросателлитных последовательностей, найденных в бактериальных геномах [3], STRbase [67], TRDB [30], а также TRbase [68]. Краткое описание баз данных по тандемным повторам, микро- и минисателлитным последовательностям с указанием методов, использованных при их создании, приведено в табл. 2 (Интернет-ресурсы активны на 15.10.2008).

ЗАКЛЮЧЕНИЕ

Представляемая диссертационная работа посвящена разработке и программной реализации алгоритмов поиска регулярности в нуклеотидных последовательностях геномов различных организмов. Частным случаем регулярности является скрытая периодичность, существование которой в некоторых генетических последовательностях было показано ранее [20, 101, 102]. Конкретные задачи проводимого исследования включали разработку алгоритма классификации периодических последовательностей по частотным матрицам встречаемости нуклеотидов в позициях периода. Практическая работа состояла в проведении классификации скрытой периодичности в различных геномах с целью выявления общих закономерностей строения периодических последовательностей. В результате были получены классы периодичности для всех групп организмов, содержащихся в банке данных Genbank, и для различных длин периода. Полученные результаты согласуются с экспериментальными данными по обнаружению микросателлитных последовательностей. Информация по обнаруженным последовательностям была представлена в виде базы данных, доступной для свободного использования в сети Интернет по адресу http://victoria.biengi.ac.rii/mmsat.

Классы периодичности были использованы для расширенного поиска скрытой периодичности в тех же последовательностях ДНК, но уже при возможности наличия вставок и делеций относительно консенсусной последовательности класса. Для проведения такого поиска был разработан алгоритм модифицированного профильного анализа, использующий динамическое программирование для выявления оптимального выравнивания последовательности относительно матрицы класса. В результате такого поиска было обнаружено в 10-100 раз больше потенциальных микросателлитов, чем при поиске алгоритмом информационного разложения. Большая часть обнаруженных последовательностей не выявлялась с помощью аналогичных алгоритмов, в том числе, основанных на преобразовании Фурье и динамическом программировании. Разработанный программный комплекс доступен для удаленного использования в сети Интернет по адресу http://victoria.biengi.ac.ru/lepscan

Обнаружение микросателлитных последовательностей имеет важное практическое значение в связи с их частым использованием для маркирования различных геномов. Кроме того, было показано, что изменение числа повторяющихся элементов в некоторых последовательностях может приводить к возникновению серьезных заболеваний [14, 15]. Еще более важным с практической точкой зрения является обнаружение регулярности в регуляторных элементах генома, в частности, в промоторах — элементах, ответственных за правильное функционирование практически всего генетического аппарата. Тем не менее, при поиске скрытой периодичности в промоторах не было выявлено большого числа повторяющихся последовательностей. Однако, предварительные данные позволяли сделать предположение о наличии регулярности в их строении. Для поиска такой регулярности был разработан и программно реализован новый алгоритм, основанный на критерии серий. Было показано, что более 60% промоторов обладают регулярностью на статистически значимом уровне. В связи с неравномерным распределением регулярных последовательностей по длине промотора, сделано предположение о необходимости наличия регулярности в районах связывания белков с ДНК.

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

1. Молекулярная биология: Структура и биосинтез нуклеиновых кислот: Учеб. для биол. спец. вузов / В. И. Агол, А. А. Богданов, В. А. Гвоздев и др.; Под ред. А. С. Спирина.- М.: Высшая школа, 1990. 352 е., ил.

2. Гены и геномы: В 2-х т. / М. Сингер, П. Берг. Т. 1. Пер. с англ. М.: Мир, 1998. - 373 е., ил.

3. Le Fleche P., Наиск Y., Onteniente L., et al. A tandem repeats database for bacterial genomes:application to the genotyping of Yersinia pestis and Bacillus anthracis // BMC Microbiology. 2001. -Vol. 1, No. 2.

4. Wells R. Molecular basis of genetic instability of triplet repeats // J. Biol. Chem. 1996. - Vol. 271.1. P. 2875-2878.

5. Weitzmann M., Woodford K., Usdin K. DNA secondary structures and the evolution of hypervariabletandem arrays II J. Biol Chem. 1997. - Vol. 272. - P. 9517-9523.

6. Richards R., Holman K., Yu S. Sutherland G. Fragile X syndrome unstable element, p(CCG)n, andother simple tandem repeat sequences are binding sites for specific nuclear proteins // Hum. Mol. Genet. 1993. - Vol. 2. - P. 1429-1435.

7. Lu O., Wallrath L., Granok II. Elgin S. (CT)n (GA)n repeats and heat shock elements have distinctroles in chromatin structure and transcriptional activation of the Drosophila hsp26 gene // Mol. Cell. Biol. 1993. - Vol. 13. - P. 2802-2814.

8. Keim P., Price L.B., Klevytska A.M., et al. Multiple-Locus Variable-Number Tandem Repeat Analysis

9. Reveals Genetic Relationships within Bacillus anthracis II J. Bacteriol. 2000. - Vol. 182. - P. 29282936.9. loth G., Gaspari Z., Jurka J. Microsatellites in different eukaryotic genomes: survey and analysis //

10. Genome Res. 2000. - Vol. 10. - P. 967-981.

11. Gur-Arie R., Cohen С J., Eitan Y., Shelef L., Hallerman E.M., Kashi Y. Simple sequence repeats in

12. Escherichia coli: abundance, distribution, composition, and polymorphism // Genome Res. 2000. -Vol. 10.-P. 62-71.

13. Adair D.M., Worsham P.L., Hill K.K., et al. Diversity in a variable-number tandem repeat from Yersinia pestis II J. Clin. Microbiol. 2000. - Vol. 38. - P. 1516-1519.

14. Riley D.E., Krieger J.N. X Chromosomal short tandem repeat polymorphisms near thephosphoglycerate kinase gene in men with chronic prostatitis // Biochim Biophys Acta. 2002. -Vol. 1586, No. l.-P. 99-107.

15. Mishra D., Thangaraj K, Mandhani A., Kumar A., Mittal R. Is reduced CAG repeat length inandrogen receptor gene associated with risk of prostate cancer in Indian population? // Clin. Genet. -2005. Vol. 68, No. 1. - P. 55-60.

16. Small, S., Kraut, R., Hoey, Т., Warrior, R., Levine, M. Transcriptional regulation of a pair-rule stripein Drosophila // Genes Dev. 1991. - Vol.5. - P. 827-839.

17. Pedersen A.G. et al. The biology of Eukaryotic promoter prediction: a review // Сотр. Chem. — 1999.-Vol. 23.-P. 191-207.

18. Herzel H., Trifonov E.N., Weiss O., Grobe I. Interpreting correlations in biosequences // Physica A. —1998. Vol. 249. - P.449-459.

19. Herzel H„ Weiss O., Trifonov E.N. 10-11 bp periodicities in complete genomes reflect proteinstructure and DNA folding // Bioinformatics. 1999. - Vol. 15, No. 3. - P.187-193.

20. Korotkov E. V., Korotkova M.A., Kudryashov N.A. Information decomposition method to analyzesymbolical sequences // Phys. Let. A. 2003. - Vol. 312. - P.198-210.

21. Makeev V.Y., Frank G.K, Tumanyan KG. Statistics of periodic patterns in the sequences of humanintrons // Biophysics. 1996. - Vol. 41, No.l. - P. 263-268.

22. Chechetkin V.R., Turygin A.Y. Size dependence of three-periodicity and long range correlations in

23. DNA sequences // Phys.Lett. A. 1995. - Vol. 199. - P. 75-80.

24. Chechetkin V.R., Lobzin V. V. Levels of ordering in coding and noncoding regions of DNA sequences

25. Phys. Lett. A. -1996. Vol. 222. - P. 354-360.

26. Chechetkin V.R., Lobzin V. V. Study of correlations in segments DNA sequences: application tostructural coupling between exons and introns I I J.Theor.Biol. — 1998. Vol. 190. - P. 69-83.

27. Лобзии B.B., Чечеткии B.P. Порядок и корреляции в геномных последовательностях ДНК.

28. Спектральный подход // Успехи физических наук. — 2000. Т. 170, №1. - С. 57-81.

29. Tiwari S., Ramachandran S., Bhattacharya A., Bhattacharya S., Ramaswamy R. Prediction ofprobable genes by Fourier analysis of genomic sequences // CABIOS. — 1997. Vol.13. - P. 263270.

30. Needleman S.B., Wunsch C.D. A general method applicable to the search for similarities in the aminoacid sequence of two proteins // J. Mo I. Biol. 1970. - Vol. 48, No. 3. - P. 443-453.

31. Математические методы для анализа последовательностей ДНК. Пер. с англ. / Под. ред. М.С.

32. Уотермена М.: Мир, 1999. - 349 с.

33. Coward Е., Drablos F. Detecting periodic patterns in biological sequences // Bioinformatics. — 1998.- Vol. 14, No. 6. P. 498-507.

34. Benson G. Tandem repeats finder: a program to analyse DNA sequences // Nucleic Acids Res. 1999.-Vol. 27. P. 573-580.

35. Benson G. Sequence alignment with tandem duplications // J.Comput.Biol. 1997. — Vol. 4. - P. 351367.

36. Landau G., Schmidt. /// Proceedings.of the IV annual symposium on combinatorial patterns matching,1.cture notes in computer science. 1993. — Vol. 648. - P. 120-133.

37. Karlin S., Morris M., Ghandour G., Leung M.-Y. Efficient algorithms for molecular sequence analysis

38. Proc. Natl. Acad. Sci. USA. 1988. - Vol. 85. - P. 841-845.

39. Benson G., Waterman M. A method for fast database search for all k-nucleotide repeats // Nucleic

40. Acids Res. 1994. - Vol. 22. - P. 4828-4836.

41. Sagot M., Myers E. Proceedings of the II annual international conference on computational molecularbiology. New-York: AMC press, 1998. P. 20-29.

42. Miller JV., Myers E. Approximate matching of regular expressions // Bull.Math. Biol. 1989. - Vol.51.-P. 5-37.

43. Kannan S.K., Myers E. W. An Algorithm for Locating Nonoverlapping Regions of Maximum

44. Alignment Score // SIAMJ. Comput. 1996. - Vol. 25. - P. 648-662.

45. Schmidt J. P. All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings // SIAMJ. Comput. 1998. - Vol. 27. - P. 972-992.

46. Gribskov M., McLachlan A.D., Eisenberg D. Profile analysis: detection of distantly related proteins // Proc. Natl. Acad. Sci. USA. 1987. - Vol. 84. - P. 4355-4358.

47. DayhoffM.O. Atlas of protein sequence and structure // Natl. Biomed. Res. Found. 1979. Vol. 5, No. 3. - P. 353-358.

48. Gribskov M, Burgess R.R. Sigma factors from E. coli. B. subtilis, phage SP01, and phage T4 are homologous proteins // Nucleic Acids Res. 1986. - Vol. 14. - P. 6745-6763.

49. Patthy L. Detecting homology of distantly related proteins with consensus sequences // J. Mol. Biol. -1987.-Vol. 198. -V.561-511.

50. Tatusov R.L., Altschul S.F., Koonin E. V. Detection of conserved segments in proteins: iterative scanning of sequence databases with alignment blocks // Proc. Natl. Acad. Sci. USA. — 1994. Vol. 91.-P. 12091-12095.

51. Yi T.M., Lander E.S. Recognition of related proteins by iterative template refinement (ITR) II Protein Sci. -1994.-Vol. 3.-P. 1315-1328.

52. Henikoff S., Henikoff J.G. Position-based sequence weights // J. Mol. Biol. 1994. - Vol. 243. -P.574-578.

53. Altschul S.F., Koonin E.V. Iterated profile searches with PSI-BLAST—a tool for discovery in protein databases // Trends Biochem. Sci. 1998. - Vol. 23. - P. 444-447.

54. Vingron M., Argos P. A fast and sensitive multiple sequence alignment algorithm // Comput. Appl. Biosci. 1989. - Vol. 5. - P.115-121.

55. Sander C., Schneider R. Database of homology-derived protein structures and the structural meaning of sequence alignment // Proteins. 1991. - Vol. 9. - P. 56-68.

56. Karchin R., Hughey R. Weighting hidden Markov models for maximum discrimination // Bioinformatics. 1998. Vol. 14. - P. 772-782.

57. Valdar IV.S. Scoring Residue Conservation // Proteins. 2002. - Vol. 48. - P. 227-241.

58. Sunyaev S.R., Eisenhaber F., Rodchenkov I.V., Eisenhaber B.E., Tumanyan KG., Kuznetsov E.N. PSIC: profile extraction from sequence alignments with position-specific counts of independent observations // Protein Eng. 1999.-Vol. 12. - P.387-394.

59. May A.C. Optimal classification of protein sequences and selection of representative sets from multiple alignments: application to homologous families and lessons for structural genomics // Protein Eng. 2001. - Vol. 14. - P. 209-217.

60. Durbin R., Eddy S., Krogh A., Mitchison G. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge (UK): Cambridge University Press, 1998.

61. Sibbald P.R., Argos P. Weighting aligned protein or nucleic acid sequences to correct for unequal representation // J. Mol. Biol. 1990. - Vol. 216. - P. 813-818.

62. Altschul S.F., Lipman D.J. Equal animals // Nature. 1990. - Vol. 348. - P. 493^194.

63. Gerstein M., Sonnhammer E., Chothia C. Volume changes in protein evolution // J. Mol. Biol. 1994. -Vol. 236. - P.1067-1078.

64. Kolpakov R., Bana G., Kucherov G. mreps: efficient and flexible detection of tandem repeats in DNA II Nucleic Acids Res. 2003. - Vol. 31, No. 13. - P. 3672-3678.

65. Rice P., Longden I., Bleasby A. EMBOSS: The european molecular biology open software suite // Trends Genet. 2000. - Vol. 16. - P. 276-277.

66. Milosavljevic A., JurkaJ. Discovering simple DNA sequences by the algorithmic significance method // CABIOS. 1993. - Vol. 9. - P. 407-411.

67. Landau G., Schmidt J., Sokol D. An algorithm for approximate tandem repeats // J. Сотр. Biol. -2001.-Vol. 8.-P. 1-18.

68. Subramanian S., Mishra R.K., Singh L. Genome-wide analysis of microsatcllite repeats in humans: their abundance and density in specific genomic regions // Genome Biol. 2003. - Vol. 4, No. 2. - P. R13

69. Swati D. In silico comparison of bacterial strains using mutual information // J. Biosci. — 2007. — Vol. 32,No. 6.-P. 1169-1184.

70. Ferragina P., Giancarlo R., Greco V., Manzini G., Valiente G. Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment // BMC Bioinformatics. 2007. - Vol. 8, No. 252.

71. Li M., Chen X, Li X, Ma В., Vitany P. The Similarity Metric // IEEE T. Inform. Theory. 2004. -Vol. 50, No. 12. - P. 3250-3264.

72. NaikP.K., Mittal V.K., Gupta S. RetroPred: A tool for prediction, classification and extraction of non-LTR retrotransposons (LINEs & SINEs) from the genome by integrating PALS, PILER, MEME and ANN // Bioinformation. 2008. - Vol. 2, No. 6. - P. 263-270.

73. Ruitberg C.M., Reeder D.J., Butler J.M. STRBase: a short tandem repeat DNA database for the human identity testing community // Nucleic Acids Res. 2001. - Vol. 29. - P. 320-322.

74. Bohy Т., Patch A.-M., Axes S. J. TRbase: a database relating tandem repeats to disease genes for thehuman genome // Bioinformatics. 2005. - Vol. 21, No. 6. - P. 811-816.

75. Macas J., Meszaros Т., Nouzova M. PlantSat: a specialized database for plant satellite repeats //

76. Bioinformatics. 2002. - Vol. 18. - P. 28-35.

77. Sreenu V., Alevoor V., Nagaraju J., Nagarajaram H.A. MICdb: Database of Prokaryotic

78. Microsatellites // Nucleic Acids Res. 2003. - Vol. 31. - P.106-108.

79. Collins J.R., Stephens R.M., Gold В., Long В., Dean M., Burt S.K. An exhaustive DNA micro-satellitemap of the human genome using high performance computing // Genomics. 2003. Vol. 82, No. 1. -P. 10-19.

80. Chang СЛ., Chang Y.C., Underwood A., Chiou C.S., Kao C.Y. VNTRDB: a bacterial variablenumber tandem repeat locus database // Nucleic Acids Res. 2007. - Vol. 35 (database issue). - P. 416-421.

81. Wexler Y., Yakhini Z, Kashi Y, Geiger D. Finding Approximate Tandem Repeats in Genomic1. Sequences // RECOMB 2004.

82. Bikandi, J., San Millan, R., Rementeria, A., Garaizar, J. In silico analysis of complete bacterialgenomes: PCR, AFLP-PCR, and endonuclease restriction // Bioinformatics. 2004. - Vol. 20, No. 5. - P. 798-799.

83. Prasad M.D., Muthulakshmi M., Arunkumar K.P., Madhu M., Sreenu V.B., Pavithra V., Bose В.,

84. Nagarajaram H.A., Mita K„ Shimada Т., Nagaraju J. SilkSatDb: a microsatellite database of the silkworm. Bombyx mori // Nucleic Acids Res. 2005. - Vol. 33(Database issue). - P. D403-6.

85. Sreenu КВ., Ranjitkumar G., Swaminathan S., PriyaS., Bose В., Pavan M.N., Thanu G., Nagaraju J.,

86. Nagarajaram H.A. MICAS: A fully automated web server for microsatellite extraction and analysisfrom prokaryote and viral genomic sequences // Applied Bioinformatics. 2003. - Vol. 2. — P. 165168.

87. Smit A.F.A., Hubley R. Green P., unpublished data. Current Version: open-3.1.9 (RMLib: 20071204).

88. Kohany O., Gentles A.J., Hankus L., Jurka J. Annotation, submission and screening of repetitiveelements in Repbase: RepbaseSubmitter and Censor //

89. BMC Bioinformatics. 2006. - Vol. 7, No. 474.

90. Sharma D., Jssac В., Raghava G.P., Ramaswamy R. Spectral Repeat Finder (SRF): identification ofrepetitive sequences using Fourier transformation // Bioinformatics. 2004. - Vol. 20. - P. 14051412.

91. Cleland C.A, Leach R. W., Forst C. Tandyman, 2000, Los Alamos National Laboratory, unpublished.

92. Smitlders M.J.M., Van Der Shoot J., Arens P., Vosman B. Trinucleotide repeat microsatellite markers for black poplar (Populus nigra L.) // Mol. Ecol. Notes. 2001. - Vol. 1. - P. 188-190.

93. Thompson H., Schmidt R., Dean C. Identification and distribution of seven classes of middle-repetitive DNA in the Arabidopsis thaliana genome // Nucleic Acids Res. 1996. - Vol. 24, No. 15. -P.3017-3022.

94. Li, Y-C., Fahima Т., Roder M.S. et al. Genetic effects on microsatellite diversity in wild emmer wheat (Triticum dicoccoides) at the Yehudiyya microsite, Israel // Heredity. 2003. - Vol. 90. - P. 150-156.

95. Yaish M.W.F., Perez de la Vega M. Isolation of (GA)n Microsatcllite Sequences and Description of a Predicted MADS-box Sequence Isolated from Common Bean (Phaseolus vulgaris L.) // Genet. Mol. Biol. 2003. - Vol. 26, No. 3. - P. 337-342.

96. Benson G. Tandem Cyclic Alignment, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching // LNCS 2001. Vol. 2089. - P. 118-130.

97. Lngham L.D., Hanna W.W., Baier J.W., Hannah L.C. Origin of the main class of repetitive DNA within selected Pennisetum species // Mol Gen. Genet. 1993. - Vol. 238. - P. 350-356.

98. Moore G., Cheung IV., Schwarzacher Т. Flavell R.B. BIS 1, a major component of the cereal genome and a tool for studying genomic organization // Genomics. 1991. - Vol. 10. - P. 469-476.

99. Smyth D.R. Dispersed repeats in plant genomes // Chromos. 1991. Vol. 100. - P. 355-359.

100. Hake S., Walbot V The genome of Zea mays, its organization and homology to related grasses // Chromos. 1980. - Vol. 79. - P. 251-270.

101. Wang Z., Weber J.L., Zhong G., Tanksley S.D. Survey of plant short tandem DNA repeats // Theor. Appl. Genet. 1994. - Vol. 88. - P. 1-6.

102. Gupta P.K., Varshney R.K. The development and use of microsatellite markers for genetic analysis of plant breeding with emphasis on bread wheat // Euphytica. 2000. - Vol. 113. - P. 163-185.

103. Groathouse N.A., Rivoire В., Kim H„ Lee H., Cho S.-T. et al. Multiple Polymorphic Loci for Molecular Typing of Strains of Mycobacterium leprae II J. Clin. Microbiol. 2004. - Vol. 42, No. 4. -P. 1666-1672.

104. MrazekJ., Guo X., Shah A. Simple sequence repeats in prokaryotic genomes // Proc. Natl. Acad. Sci. USA. 2007. - Vol. 104, No. 20. - P. 8472-8477.

105. Ussery D. W, Binnewies Т. Т., Gouveia-Oliveira R., Jarmer H„ Hallin P. F. Genome Update: DNA repeats in bacterial genomes // Microbiology. 2004. - Vol. 150. - P. 3519-3521.

106. Ohler U„ Liao G.C., Niemann K, Rubin G.M. Computational analysis of core promoters in the Drosophila genome // Genome Biol. 2002. - Vol. 3, No. 12. - P. 0087.1-0087.12.

107. Knudsen S. Promoter2.0: for the recognition of PoIII promoter sequences // Bioinformatics. — 1999. -Vol. 15,No. 5.-P. 356-361.

108. Bajic V.B., Seah S.H. Dragon gene start finder: an advanced system for finding approximate locations of the start of gene transcriptional units // Genome Res. 2003. - Vol. 13. - P. 1923-1929.

109. Solovyev V. V., Shahmuradov I.A. PromH: promoters identification using orthologous genomic sequences // Nucleic Acids Res.- 2003. Vol. 31. - P. 3540-3545.

110. Bajic V.B. et al. Promoter prediction analysis on the whole human genome // Nat. Biotechnol. 2004. -Vol. 22.-P. 1467-1473.

111. Xie X., Wu S., Lam K.-M., Yan H. PromoterExplorer: an effective promoter identification method based on the AdaBoost algorithm // Bioinformatics. 2006. - Vol. 22. - P. 2722-2728.

112. Frenkel F.E., Chaley M.B., Korotkov E.V., Skryabin KG. Evolution of tRNA-like sequences and genome variability // Gene. 2004. - Vol. 335. - P.57-71.

113. Korotkov E.V., Korotkova M.A., Rudenko KM. MIR: family of repeats common for vertebrate genomes // Mol. Biol. (Mosk). 2000. - Vol. 34, No. 4. - P. 553-559.

114. HoelP.G. Introduction to Mathematical Statistics, 3rd ed. New-York: Wiley, 1966.

115. Браунли К. А. Статистическая теория и методология в науке и технике. Пер с англ. М.: Наука. 1977.-407 с.

116. Sheskin D.J. Handbook of Parametric and Nonparametric Statistical Procedures. 2nd ed. New York: Chapman & Hall/CRC, 2000.

117. Shelenkov A.A., Skryabin KG., Korotkov E. К Search and Classification of Potential Minisatellite Sequences from Bacterial Genomes II DNA Res. 2006. - Vol. 13, No. 3. - P. 89-102.

118. Waterman M.S. Introduction to Computational Biology. Map, Sequences and Genomes. London: Chapman & Hall, 1995. xvi + 432 pp.

119. Smith T.F., Waterman M.S. Identification of common molecular subsequences // J. Mol. Biol. -1981.-Vol. 147.-P. 195-197.

120. Webber С., Barton G.J. Estimation of P-values for global alignments of protein sequences // Bioinformatics. 2001. - Vol. 17, No. 12. - P. 1158-1167.

121. Воеводин Вл. В, Жуматий С.А. Вычислительное дело и кластерные системы. М: Изд-во МГУ, 2007. - 150 с.

122. Schmid C.D., Perier R., Praz V., Bucher P. EPD in its twentieth year: towards complete promoter coverage of selected model organisms II Nucleic Acids Res. 2006. - Vol. 34. - D82-5.

123. Werner T. The state of the art of mammalian promoter recognition // Brief. Bioinform. — 2003. -Vol. 4. No. l.-P. 22-30.

124. Fickett J. W., Hatzigeorgiou A.G. Eukaryotic promoter recognition // Genome Res. — 1997. Vol. 7, No. 9.-P. 861-78.