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

• Назипова, Нафиса Наиловна
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Назипова, Нафиса Наиловна

Введение.

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

1.1. Статистический анализ и предсказание сайтов связывания рибосом.

1.2. Исследование сложности генетических текстов.

1.3. Нахождение повторяющихся участков в последовательностях.

1.3.1. Статистическая значимость повторов.

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

2.1. Интерфейс пользователя и типы входных данных.

2.2. Сервисные программы.

2.2.1. Программа BNKFREQ - формирование по базе данных выборки участков.

2.2.2. Программа BNKFR2 - формирование по базе данных выборок участков.

2.2.3. Программа RANDSEQ - генерирование псевдослучайной последовательности.

2.2.4. Программа TAKESEQ - подготовка заданного фрагмента последовательности.

2.3. Специальные программы для исследования серий последовательностей.

2.3.1. Программа G2 - вычисление информационного содержания выборки.

2.3.2. Программа ABAСК-выравнивание выборки участков.

2.3.3. Программы SHH1ST, SHHIST2 - расчет статистик.

2.3.4. Программы EXCELF1, EXCELF2, EXCELF3 - расчет данных для электронных таблиц.

2.3.5. Программы TEST1, TEST2, TEST3 - - расчет активности участков выборки.

2.3.6. Программы ERHIST, ERHIST - расчет характеристик распределения значений функции, полученных на выборке.

2.3.7. Программа STAT - оценка качества расчета активностей выборок.

2.4. Программы обработки.

2.4.1. Высоко- и низкочастотная компоненты графа /-граммного разложения.

2.4.2. Программа SHENON - расчет информационной избыточности текста.

2.4.3. Программа LZW- алгоритмическая сложность текста.

2.4.4. Программа MOTIFS - поиск неточных повторов.

2.4.5. Программа LGRAMM - построение словаря последовательности.

Глава 3. Методика распознавания функциональных блоков на полных геномах.

3.1. Поиск общего сигнала в сериях участков биологических последовательностей.

3.2. Равновесное состояние графа /-граммного разложения.

3.3. Выбор параметров скользящего окна и длины /-грамм.

3.4. Какие особенности генетических последовательностей определяет новая информационная мера.

Введение диссертации (часть автореферата) на тему «Разработка алгоритмов и программного обеспечения для исследования информационного содержания генетических последовательностей»

Быстрое накопление данных о первичных структурах биополимеров поставило перед разработчиками программного обеспечения много интересных задач. В течение последнего пятнадцатилетия появилось большое число программ и программных комплексов, предназначенных для анализа этих данных. При этом решались разнообразные задачи. Программные средства, созданные для их решения, тоже разнообразны, среди них встречаются отдельные программы, направленные на решение одной конкретной задачи (информационно-поисковой, молекулярно-физической, сравнения последовательностей и др.), такие, как DIAGON [10], CLUSTAL[\ 1], MULTALIN[\2l РМАР[ 13], PM4PS[13], MULTAN[U]. Таких специализированных программ очень много, они продолжают создаваться вместе с оригинальными алгоритмами. Были созданы также большие комплексы программ с высокой степенью интеграции, такие, как отечественные DNASUN, GeneBee [15], SAMSON [9], CONTEXT [16], VOSTORG [17], западные GCG, DNASTAR, IBI/Pustell[ 18], MicroGenie, PC/Gene, ZX/V/l .SYSf 19] и др. Как правило, крупные универсальные пакеты создавались большими коллективами программистов, имеют коммерческую направленность и содержат в себе традиционный набор средств обработки, ориентированных на биологов-экспериментаторов. При разработке таких программ основное внимание уделяется простоте и удобству работы пользователя, в пользовательском интерфейсе используется большое количество визуальной информации, окна, подсказки. Такие программы обычно кодируют известные алгоритмы, параметры которых уже достаточно изучены, подобраны и запрятаны внутри. Часто пользователь не догадывается об их существовании. Примерами программных разработок такого рода являются семейства поисковых программ BLAST [20,21], FAST [22] и др., которые обеспечивают поиск последовательностей, до некоторой степени похожих на заданную, в соответствующих банках данных. Математическое и алгоритмическое обеспечение этих ресурсов разрабатывалось давно и только с появлением INTERNET превратилось в довольно удобные общедоступные поисковые системы. Все они построены на хэшировании базы данных и новой последовательности с последующим сравнением хэш-таблиц, отличаются друг от друга способами статистической оценки достоверности сходства. Они обеспечивают поиск и по электронной почте, если у пользователя нет доступа во всемирную информационную сеть. Однако, несмотря на то, что программы подобного рода работают эффективно, более пытливый пользователь, вникший в суть алгоритма, хочет сам менять и подбирать параметры для достижения конкретной исследовательской цели. Такие возможности у подобного рода универсальных программ бывают ограничены.

Другим примером поисковых программ являются программы, осуществляющие поиск документов в базе данных, удовлетворяющих запросу пользователя к содержимому конкретных полей документа. Каждая крупная база данных в настоящее время имеет выход в INTERNET, а также свой поисковый сервер, примерами таких систем являются Entrez[23], 5&5[24] и другие. Поисковые программы, привязанные к основным базам данных, решили проблему организации и хранения информации. Если в программных пакетах 80-х, начала 90-х годов обязательной компонентой была подсистема работы с базами данных, то в нынешних программных реализациях эта задача с помощью возможностей всемирной сети частично решена.

Представленный в этой работе пакет прикладных программ создан для исследовательской работы по разработке новых подходов в решении задач теоретического анализа последовательностей. Это задел для большого интегрированного пакета анализа протяженной символьной последовательности, являющейся простейшей моделью молекулы биополимера. Его появление вызвано тем фактом, что, благодаря налаживанию промышленных технологий расшифровки первичных структур молекул ДНК, темпы роста объемов соответствующих им символьных последовательностей в последние год-два вышли на экспоненциальную кривую. Если раньше считалось, что объем крупнейшей базы данных GenBank удваивается за 18 месяцев, то теперь это удвоение объема происходит за 15 месяцев [23]. Необходимо отметить также и то, что нарастание объема происходит не за счет количества документов, а за счет роста длин последовательностей.

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

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

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

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

Сильное возрастание за последние 2-3 года объемов единиц хранения, делает актуальной задачу обработки сверхдлинных символьных последовательностей. Многие из существующих программных реализаций не могут работать с длинными последовательностями. Большинство систем организации крупнейших специализированных баз данных претерпели в последнее время значительные изменения, которые были обусловлены необходимостью работы с гигантскими объемами данных.

Цели работы

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

Научная новизна

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

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

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

Практическая ценность

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

В результате работы по распознаванию участков связывания генетической последовательности с рибосомой получены частотные матрицы, они разные для каждой разновидности биологических объектов, нами получены матрицы для 21-го бактериального организма, которые в 1999 году были помещены на сайт Internet по адресу http://www.eimb.rssi.ru/databases и использовались для поиска генов на новых последовательностях. Пакет содержит программное обеспечение [1,2] работы со специализированными базами данных для получения неизбыточных выборок коротких участков, содержащих внутри себя начала генов, программ для получения распознающих матриц, а также программ для распознавания этих участков другими известными методами. Эти средства позволяют получать распознающие матрицы для любых организмов по мере появления новых расшифрованных генов. Кроме того, созданы программные средства для исследования правильности локализации начала трансляции генов, с помощью которых можно корректировать базы данных.

Другим практическим результатом является создание программ для исследования неоднородностей геномных последовательностей. Он состоит из программ подсчета избыточности текста тремя различными способами (в смысле алгоритма сжатия/декодирования, по Шеннону и по низкочастотной компоненте графа /-граммного разложения)[3-6], программы нахождения статистически значимых повторов [7-9], программы генерирования псевдослучайной последовательности с заданным частотным составом взаимно перекрывающихся слов любой длины.

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

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

Автор защищает:

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

-метод обнаружения на протяженной символьной последовательности зон периодичностей и неоднородностей состава;

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

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

Результаты, положенные в основу диссертационной работы, опубликованы в [1-9] и докладывались на Московском семинаре по компьютерной генетике (ИМБ РАН) в октябре 1996 года; на международной конференции "Mathematics and Molecular Biology VI" (Санта-Фе, США, 9-14 января 1999), а также на межлабораторном семинаре в ИМПБ РАН в феврале 2000 года.

Структура и содержание работы:

Диссертация состоит из введения, трех глав, заключения, 5 приложений и списка литературы из 105 наименований. Общий объем диссертации - 104 страницы, из них 81 страница - основной текст, который содержит .10 графиков, 2 схемы и 5 таблиц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Назипова, Нафиса Наиловна

Результаты исследования генома вируса EBV программой Shenon и последующим использованием EXCEL приведены на рис.3.6. Характерная периодичность 12*3062 н.п. отделяет Short Unique Region от Large Unique Region. Данные повторы имеют неравномерное распределение троек по длине повторяющегося участка и высокую степень гомологии. Буквенный состав в целом на протяжении 12*3062 н.п. равен (FA=0.163, Ff= 0.166, Fc=0.282, Fc= 0.389), в то время как в среднем по геному - (^=0.198, Ff=0.202, F<f=0.295, Fc= 0.305). Данные по буквенному составу получены программой LGRAMM. Сочетание этих факторов приводит к появлению характерной пилообразной кривой со смещенным средним уровнем колебаний. В силу высокой степени сходства 12-ти повторов (менее 100 замен при длине каждого в 3072 н.п.) характер профиля сохраняется также и при меньших размерах окна.

Наличие на профилях R3LF и R3sh ярко выраженных 12-ти пиков позволяет предположить наличие внутренних повторов в повторяющемся участке длиной 3072 н.п. Исследовался первый участок с координатами 12001-15072 п.н. (пик 1 на рис.3.6). На общем фоне многочисленных повторов выделены непересекающиеся между собой повторяющиеся фрагменты. 12859-12876-повтор А 13013-13043 - повтор В 13307-13337-повторВ 13420-13450-повтор В 13749-13766-повтор А повторА CCAGAGCCCCT(t/c)(tig)(tig)GCCC длиной 18, повтор В CAGGCCAGCCGGAGGGACCCCGGCAGCCCGG длиной 31. Все перечисленные повторы найдены с помощью программы MOTIFS и не могут считаться случайными. Нахождение повторяющихся участков приблизительно в центре фрагмента согласуется с симметричной формой пика.

В случае, когда повторяющаяся последовательность неоднократно укладывается в окне, наблюдается пик на профиле избыточности. Наиболее выраженные пики соответствуют известным областям повторов, в том числе области oriP (с координатами от 7421-й позиции до 8042-й), гену латентного цикла, кодирующему EBRNAI-Qqjiok (в позициях 107950-109875), терминальным повторам (170094-172231).

На рис.3.6 горизонтальными линиями под осью к указаны зоны повторов, описанные в базе данных GenBanK 22.0. Наше исследование пиков 2 и 3 показало наличие в них повторяющихся участков. Все обнаруженные структуры прямых неточных повторов относятся к некодирующим участкам генома вируса.

Участки рассогласования 2-х графиков избыточности, рассчитанной 2-мя различными способами R3LF и R3Sh, были выделены для бактериофага Л. Выделялись такие участки относительного повышения избыточности R3LF, для г» Sh которых значение R3 оставалось в пределах значении, характерных для соседних районов. На рис. 3.8 приведена разность между нормированными избыточностями бактериофага X. Наиболее низкие значения величины ARi(Q) наблюдаются в районе 21500-23000 н.п. (стрелка 1). Данный район выделен также у Певзнера [53] на основе анализа стационарных 2- и 3-грамм как граница между функционально и статистически различными модулями. Другой участок низких значений ARi(Q) (стрелка 2) соответствует правой границе области генов рекомбинации.

В отношении перечисленных районов рассогласование функций RiLF и RiSh с указанным знаком сохраняется при варьировании 2<1<5. Одной из возможных причин несоответствия процесса точечных мутаций замены в данных районах диффузионной модели может являться меньшая скорость накопления точечных мутаций замены, чем в других районах генома,

Sh сравнимых по значению R{ .

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

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

76

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

650 3150 5650 8150 10650 13150 15650 18150 20650^3150 25650 28150 30650 3^150 35650 38150 40650 43150 45650 48150 1 2 геномы вируса EBV, Mycoplasma genitalium, фага Л. Полученные данные для вируса ЕВ V, и фага Я согласуются с опубликованными ранее выводами о неоднородности их 2- и 3-граммного составов. Представляется неожиданным тот факт, что геном Mycoplasma genitalium имеет значимо меньшее среднеквадратичное отклонение избыточности R3LF по сравнению с вирусом Эпштейна-Барр (Р>0.998). Кроме того, видно, что никакой корреляции между величиной избыточности и длиной генома не наблюдается.

Табл.3.3

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

Организм фаг MS2 вирус SV40 фаг Chpl фаг Lambda фаг 77 Myc.g. вирус EBV Random

Длина генома (п.н.) 3569 5243 4877 48502 39937 580073 172281 130000

Средняя избыточность 0.119 0.209 0.203 0.170 0.166 0.222 0.205 0.140

Ст.отклонение ) 0.006 0.017 0.017 0.021 0.023 0.023 0.064 0.0006

Средняя избыточность по Sh Шеннону М^з ) 0.008 0.049 0.057 0.027 0.017 0.076 0.048 0.025

Ст.отклонение O^R^1) 0.002 0.015 0.010 0.008 0.005 0.020 0.041 0.0002

В графе Random указаны данные для случайной последовательности с тем же распределением перекрывающихся 3-грамм, что и у последовательности EBV.

Интересным кажется и факт очень незначительной избыточности генетических последовательностей, по сравнению с лингвистическими текстами. Опыты Шеннона [105] показали, что для английского языка избыточность по порядку величины близка к 80%, в то время как для исследованных нами текстов избыточность по Шеннону имеет диапазон значений приблизительно от 0.008 до 0.08.

Заключение

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

77 обработки символьных последовательностей. Идейно новыми являются перечисленные ниже компоненты пакета.

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

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

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

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

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

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

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

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

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

Автор выражает большую благодарность за интересную и плодотворную совместную работу к.т.н. Боровиной Т.А., к.т.н. Кислюку О.С., д.б.н. Гельфанду М.С. Особую благодарность выражается к.б.н. Зимину А.А. за помощь в работе над текстом диссертации, к.б.н. Шабалиной С.А. за постоянный интерес к этой работе.

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

1.Боровина Т.А., Назипова Н.Н., Овербик Р., Гельфанд М.С. (1999) Статистический анализ и предсказание бактериальных сайтов связывания рибосом. Биофизика, 44(4), 611-619

2. М.С.Гельфанд, Н.Н.Назипова, Т.А.Боровина (1999) Метод распознавания сайтов связывания рибосом у прокариот. Труды IX Всероссийской конференции "Математические методы распознавания образов", Москва, 163-165.

3. Кислюк О.С., Боровина Т.А., Назипова Н.Н. (1999) Оценка избыточности генетических текстов с помощью высокочастотной компоненты графа /-граммного разложения. Биофизика, 44(4), 639-648

4. Назипова Н.Н., Боровина Т.А. (1997) Метод обнаружения повторяющихся лексических структур в генетических текстах. Тезисы VIII Всероссийской конференции "Математические методы распознавания образов", Москва, 196-197.

5. Corpet F. (1988) Multiple sequence alignment with hierarchical clustering. Nucleic Acids Res., V16, No.22, 10881-10890

6. Polner G., Dorgai L., Orosz L. (1984) PMAP, PMAPS: DNA physical map constructing programs. Nucleic Acids Res., V.12, No.l, 227-236

7. Bains W. (1986) MULTAN: a program to align multiple DNA sequences. Nucleic Acids Res., V.14, 159-177

8. Solovyev V.V., Rogozin I.B. (1986) Program package of context analysis of DNA, RNA and protein sequences "CONTEXT" (Institute of Cytology and Genetics, Russian Acad.Sci., Novosibirsk)

9. Zharkikh A.A., Rzhetsky A.Y., Morosov P.S., Sitnikova T.L., Krushal J.S. (1991) VOSTORG: a package of microcomputer programs for sequence analysis and construction of phylogenetic trees. Gene, V.101, 251-254

10. Pustell J., Kafatos F.C. (1986) A convenient and adaptable microcomputer environmentn for DNA and protein sequence manipulation and analysis. Nucleic Acids Res., V.14, No.l, 479-488

11. Hoyle P. (1987) Use of commercial software on IBM personal computers. In\Nucleic acid and protein sequence analysis: a practical aproach. Bishop M.J., Rawlings C.J., eds. Oxford; Washington. D.C.: IRL Press.

12. Altschul S.F., Gish W., Miller W., Myers E.W., Lipman D.J. (1990), Basic local alignment search tool, JMB, V.215, 403-410

13. Altschul S.F., Madden T.L., Schaffer A.A., Zhang J., Zhang Z., Miller W., Lipman D.J. (1997), Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, NAR, V.25, 3389-3402

14. Pearson W.R. (1990) Rapid and sensitive sequence comparison with FASTP and FASTA. Meth. in Enzyimol, V.183, 63-98

15. Benson D.A., Boguski M.S., Lipman D.J., Ostell J., Francis Ouellette B.F., Rapp B.A., Wheeler D.L. (1999) GenBank, Nucleic Acids Research, 27(1): 12-17

16. Stoesser G., Tuli M.A., Lopez R., Sterk P. (1999) The EMBL Nucleotide Sequence DataBase. Nucleic Acids Res., 27(1), 18-24

17. EMBL Nucleotide Sequence Database. "User Manual. Release 62, March 2000".

18. Gelfand M.S. (1995) Prediction of function in DNA sequence analysis. J.Comput.Biol., V.2, 87-115.

19. Shine J., Dalgarno L. (1974) The 3'-terminal sequence of Escherichia coli 16S ribosomal RNA: complementarity to nonsense triplets and ribosome binding sites. Proc.Natl.Acad.Sci.USA, V.71, 1342-1346.

20. Steitz J.A., Jakes K. (1975) How ribosomes select initiator regions in mRNA: base pair formation between the 3' terminus of 16S rRNA and the mRNA during initiation of protein synthesis in Escherichia coli. Proc.Natl.Acad.Scu, V.72, 4734-4738

21. Steege D.A. (1977) 5'-Terminal nucleotide sequence of Escherichia coli lactose repressor mRNA: features of translational initiation and reinitiation sites. Proc.Natl.Acad.Sci.USA, V.75, 4163-4167

22. Stormo G.D., Schneider T.D., Gold L.M (1982) Characterization of translational initiation sites in E. coli. Nucleic Acids Res., V.10, 2971-2996.

23. Stormo G.D., Schneider T.D., Gold L.M., Ehrenfeucht A. (1982) Use of the 'Perception' algorithm to distinguish translational initiation sites in E. coli. Nucleic Acids Res., V.10, 2997-3011.

24. Bisant D., Maizel J. (1995) Identification of ribosome binding sites in Escherichia coli using neural network models. Nucleic Acids Res., V.23, 16321639.

25. Александров H.H., Каламбет Ю.А. (1990) Распознавание функциональных сигналов. В кн.: Александров А. А. и др., Компьютерный анализ генетических текстов, М.:Наука, 113-153

26. Berg O.G., von Hippel Р.Н.(1987) Selection of DNA binding sites by regulatory proteins. Statistical-mechanical theory and application to operators and promoters. J.Mol.Biol., V.193, 723-750

27. Berg O.G., von Hippel P.H. (1988) Selection of DNA binding sites by regulatory proteins. II. The binding specificity of cyclic AMP receptor protein to recognition sites J.Mol.Biol., V.200, 709-723

28. Studnicka G.M. (1986) Quantitative computer analysis of signal sequence homologies in DNA. Comput.Appl.Biosci., V.2, 269-275.

29. Studnicka G.M. (1987) Nucleotide sequence homologies in control regions of prokaryotic genomes. Gene, V.58, 45-57.

30. Cavener D.R. (1987) Comparison of the consensus sequence flanking translational start sites in Drosophila and vertebrates. Nucleic Acids Res., V.15, 1353-1361

31. Schurr Т., Nadir E., Margalit H. (1993) Identification and characterization of E.coli ribosomal binding sites by free energy computation Nucleic Acids Res., V.21,4019-4023.

32. Petersen G.B., Stockwell P.A., Hill D.F. (1988) Messenger RNA recognition in Escherichia coli: a possible second site of interaction with 16S ribosomal RNA. EMBOJ., V.7, 3957-3962.

33. Sprengart M.L., Fatscher H.P., Fuchs E. (1990) The initiation of translation in E.coli: apparent base pairing between the 16srRNA and downstream sequences of the mRNA. Nucleic Acids Res., V.18, 1719-1723.

34. Barrick D., Villanueba K., Childs J., Kalil R., Schneider Т., Lawrence C.E., Gold L., Stormo G.D. (1994) Quantitative analysis of ribosome binding sites in E.coli. Nucleic Acids Res., V.22, 1287-1295.

35. Golovanov Eu.I., Sprizhitsky Yu.A., Alexandrov A.A. (1982) Structure and Functions of Proteins and Nucleic Acids, Abstr. 6th USSR-France Symp. Tskhaltubo, p.52.

36. Гусев В.Д., Куличков B.A., Чужанова H.A. (1987) Алгоритмы обнаружения знаков пунктуации в генетических текстах. В сб. "Анализ текстов и сигналов". Вычислительные системы, №123, 3-24

37. Гусев В.Д., Куличков В.А., Титкова Т.Н. (1980) Анализ генетических текстов. 1. /-граммные характеристики. Компьютерные системы, т.83, Новосибирск: Институт математики СО АН СССР, с. 11-33.

38. Kozhukhin C.G., Pevzner P.А. (1990?) Genome inhomogeneity is determined mainly by WW and SS dinucleotides. Comput.Appl.Biosci., V.7, 39-49

39. Nussinov R. (1981) Nearest neighbour nucleotide patterns. J.Biol.Chem., V.256, 84-8462.

40. Blaisdell B.E. (1985) Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucariotic nuclear DNA sequences protein-coding and noncoding. Mol.EvoL, V.21, 278-288.

41. Suboch G.M., Sprizhitsky Yu.A. (1989) A statistical significance of the occurrence of some complex nucleotide combinations: comparison of DNA models. Biopolymers Cell, V.5, 30-36.

42. Бородовский М.Ю., Сприжицкий Ю.А., Голованов Е.И., Александров А.А. (1986) Статистические закономерности в первичных структурах функциональных областей генома Escherichia Coli . П.Неоднородные марковские модели. Молекулярная биология, т. 20, 1024-1033.

43. Bernardi G., Mouchiroud D., Gautier С., Bernardi G. (1988) Compositional patterns in vertebrate genomes: conservation and change in evolution. J.Mol.Evol., V.28, 7-18.

44. Churchill G.A. (1989) Stochastic models for heterogeneous DNA sequences. Bull.Math.Biol., V.51(l), 79-94.

45. Pevzner P.A., Borodovsky M.Yu., Mironov A.A. (1989) Linquistics of nucleotide sequences: ILStationary words in genetic texts and zonnal structure of DNA. J.Biom.Struct.Dyn., V.6, 1027-1038.

46. Gusev V.D., Kulichkov V.A., Chupakhina O.M. (1993) The Lempel-Ziv complexity and local structure analisys of genomes. BioSystems, V.30, 183-200.

47. Gusev V.D., Kulichkov V.A., Chupakhina O.M. (1993) Global complexity analisys of genomes. BioSystems, V.30, 201-214.

48. Колмогоров A.H. (1987) Теория информации и теория алгоритмов. М.: Наука, с.213.

49. Chaitin G.J. (1974) Information-Theoretic Computational Complexity. IEEE Trans.Inform. Theory, V.IT-20, 10-15.

50. Schnorr C.P.(1973) The process complexity and effective random tests. J.Comput.Syst.Sci., V.7, 376-388.

51. Jimenez-Montano M.A. (1984) On the syntactic structure of protein sequences and the concept of grammar complexity. Bull.Math.Biol., V.46, No.4, 641-659.

52. Lempel A., Ziv J. (1976) On the Complexity of Finite Sequences. IEEE Trans.Inform.Theory, V.IT-22, No.l, 75-81.

53. Гусев В.Д., Куличков В.А., Чупахина О.М. (1989) Анализ сложности генетических текстов (на примере фага Я). Препринт 20, Новосибирск: Институт математики СО АН СССР.

54. Шеннон К. (1963) Работы по теории информации и кибернетике. М.: Иностранная литература, с.243.

55. Хакен Г. (1991) Информация и самоорганизация: Макроскопический подход к сложным системам. М.: Мир, с.37.

56. Staden R. (1984) Graphic methods to determine the function of nucleic acid sequences. Nucleic Acids Res., V.12, 521-538.

57. Бородовский М.Ю., Сприжицкий Ю.А., Голованов Е.И., Александров А.А. (1986) Статистические закономерности в первичных структурах функциональных областей генома Escherichia Coli. I.Частотные характеристики. Молекулярная биология, т. 20, 1014-1023.

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

59. Попова Т.Г., Садовский М.Г. (1995) Избыточность генов эукариот уменьшается в результате сплайсинга. Молекулярная биология, Т.29, 500506.

60. Jeffrey H.J. (1990) Chaos game representation of gene structure. Nucleic Acids Res., V.18,No.8, 2163-2170

61. Соловьев В.В., Королев С.В., Туманян В.Г., Лим Х.А. (1991) Новый подход к классификации участков ДНК, основанный на фрактальном представлении набора функционально сходных последовательностей. Докл.Акад.наук СССР, т.319(6), 1496-1500.

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

63. Tautz D., Trick М., Dover G.A. (1986) Cryptic simplicity in DNA is a major source of genetic variation. Nature, V.322, 652-656.

64. Hancock J.M., Armstrong J.S. (1994) SIMPLE34:an improved and enhanced implementation for VAX and Sun computers of the SIMPLE algorithm for analysis of clustered repetitive motifs in nucleotide sequences. Comput.Appl.Biosci., V.10, No.l, 67-70.

65. Hancock J.M. (1996) Simple sequences in a "minimal" genome. Nature Genetics, V. 14, 14-15.

66. Waterman M.S. (1984) General Methods of Sequence Comparison. Bull.Math.BioL, V.46, 473-500.

67. Waterman M.S. (1989) Sequence alignments. In; Mathematical Methods for DNA Sequences. Ed. Waterman M.S., CRC Press, Boca Raton, Florida, pp.53-92

68. Александров A.A., Александров H.H., Бородовский М.Ю., Каламбет Ю.А., Кистер А.З., Миронов А.А., Певзнер П.А., Шепелев В.А. (1990) Компьютерный анализ генетических текстов. М.: Наука.

69. Gibbs A.J., Mclntyre G.A. (1970) The Diagram, a Method for Comparing Sequences. Ero.J.Biochem., V.16, 1-11.

70. Reich J.G., Meiske W. (1987) A simple statistical significance test of window scores in large dot matrices obtained from protein or nucleic acid sequences. Comput.Appl.Biosci., V.3, No.l, 25-30.

71. Martinez H.M. (1983) An efficient method for finding repeats in molecular sequences, Nucleic Acids Res., V.l 1, 4629-4634.

72. Aho V.A., Hopcroft J.E., Ulman J.D. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley, Menlo Park, California.

73. Korn L.J., Queen C.L., Wegman M.N. (1977) Computer Analysis of Nucleic Acid Regulatory Sequences. Proc.Natl.Acad.Sci.USA, V.74, 4401-4405.

74. Karlin S., Ghandour Gh., Ost F., Tavare S., Korn L.J. (1983) New approaches for computer analysis of nucleic acid sequences. Proc.Natl.Acad.Sci.USA, V.80, 5660-5664

75. Knuth D.E., Morris J.H.,Jr, Pratt V.R. (1977) Fast pattern matching in strings. SI AM J.Compute V.6, No.2, 323-350.

76. Apostolico A., Farach M., Iliopoulos C.S. (1991) Optimal superprimitivity testing for strings. Iformation Processing Letters, V.39, 17-20.

77. Crochemore M. (1981) An optimal algorithm for computing the repetitions in a word. Information Processing Letters, V.12., No.5. 244-250.

78. Apostolico A., Preparata F.P. (1983) Optimal off-line detection of repetitions in a string. Theor.Computer Science, V.22, 297-315.

79. Колчанов H.A., Соловьев B.B., Жарких A.A. (1983) Высокая насыщенность прямыми повторами в генах РНК-полимераз по данным контекстного анализа, Докл.Акад.наук СССР, т.273, 741-744

80. McLachlan, A.D., Bosswell D.R. (1985) Confidence Limits for Homology in Protein or Gene Sequences. The с-myc Oncogene and Adenovirus El a Protein. J.Mol.BioL, V.185, 39-49.

81. Brooks L.D., Weir B.S., Schaffer H.E. (1988) The Probabilities of Similarities in DNA Sequence Comparisons. Genomics, V.3, 207-216.

82. Queen C.L., Korn L.J. (1980) Computer analysis of nucleic acids and proteins. In "Methods in Enzymology" (L.Grossman and K.Moldave, Eds), Vol.65, pp.595609, Academic Press, New York.

83. Arratia R., Gordon L., Waterman M.S. (1985) An extreme value theory for sequence matching. Ann. Stat., V.14, 971-993.

84. Smith T.F., Waterman M.S., Burks C. (1985) The statistical distribution of nucleic acid similarities. Nucleic Acids Res., V.13, 645-656.

85. Erdos P., Renyi A. (1970) On a new law of large numbers. J.AnalMath., V.22, 103-111.

86. Barton D.E., Mallows C.L. (1965) Some aspects of the random series. Annals Math. Statist., V.36, 236-260.96."The DDBJ/EMBL/GenBank Feature Table: Definition".

87. Чэн Ш.-К. (1994) Принципы проектирования систем визуальной информации. М.: Мир, с. 94

88. Чисар И., Кернер Я. (1985) Теория информации: теоремы кодирования для дискретных систем без памяти. М., Мир, с.32

89. Кнут Д. (1976) Искусство программирования для ЭВМ. Основные алгоритмы. М.: Мир, с.50

90. Dayhoff M.O., Barker W.C., Hunt L.T. (1983) Establishing homologies in protein sequences. Methods Ensymol., V.91, 524-545.

91. Henikoff S., Henikoff J. (1992) Amino acid substitution matrices from protein blocks. Proc.Natl.Acad.Sci.USA, V.89, 10915-10919.

92. Risler J.L., Delorme M.O., Delacroix H., Henaut A. (1988) Amino Acid Substitutions in Structurally Related Proteins. A Pattern Recognition Approach. Determination of a New and Efficient Scoring Matrix. J.Mol.Biol., 204, 10191029.

93. Rodier F., Sallantin J. (1985) Localization of the initiation of translation in messenger RNAs of prokaryotes by learning techniques. Biochimie, V.67, 533539.

94. Staden R., McLachlan A.D. (1982) Codon preference and its use in identifying protein coding regions in long DNA sequences. Nucleic Acids Res., V.10, 141156.

95. Ю5.Яглом A.M., Яглом И.М. (1973) В кн.: Вероятность и информация. М.: Наука, 253-273.