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

• Гельфанд, Михаил Сергеевич
• доктор биологических наук
• 1998

Оглавление диссертации доктор биологических наук Гельфанд, Михаил Сергеевич

Содержание

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

Введение__6

0.1. Экзон-интронная структура генов высших эукариот_8

0.2. Предсказание белок-кодирующих областей в ДНК высших эукариот_10

0.3. Предсказание белок-кодирующих областей с использование дополнительной

информации ___

0.4. Статистический анализ нуклеотидных последовательностей_17

Глава 1. Статистический анализ экзон-интронной структуры и сайтов сплайсинга_22

1.1. Статистический анализ экзон-интронной структуры __22

1.2. Статистический анализ сайтов сплайсинга__25

1.3. Контекстные особенности и корреляции___31

1.4. Обсуждение ____38

1.5. Приложение. Описание выборок__41

Глава 2. Предсказание экзон-интронной структуры_42

2.1. Метод векторного динамического программирования. Формальная постановка задачи_^______

2.2. Метод векторного динамического программирования. Основной алгоритм_45

2.3. Результаты______48

2.4. Обсуждение ________________

2.5. Приложение 1. Варианты основного алгоритма_57

2.6. Приложение 2. Общая постановка задачи на языке теории графов_59

Глава 3. Алгоритмы поддержки эксперимента по поиску генов __63

3.1. Алгоритм__________________63

3.2. Тестирование_______66

3.3. Обсуждение__

Глава 4. Предсказание экзон-интронной структуры с использованием информации о

гомологах

4.1. Сплайсированное выравнивание_73

4.2. Фильтрация потенциальных экзонов__76

4.3. Тестирование____77

4.4. Обсуждение___86

4.5. Приложение. Формальная постановка задачи и описание алгоритма_94

Глава 5. Статистический анализ последовательностей ДИК__97

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

модификации _______97

5.2. Продолжаемые слова_____107

5.3. Приложение. Ранговый статистический критерий для подмножеств_113

Выводы. Основные результаты___115

Список работ по теме диссертации__119

Статьи в реферируемых изданиях__119

Другие публикации____121

Литература___124

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

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

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

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

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

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

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

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

Научная новизна и практическая ценность работы. Проведен статистическй анализ экзонной структуры генов человека и впервые найден ряд закономерностей в распределении длин интронов и экзонов, а также сигналов сплайсинга. Предложен, реализован и тестирован алгоритм векторного динамического программирования для предсказания экзон-интронной структуры. Предложен, реализован, тестирован и введен в практику новый комбинаторный подход к проблеме компьютерной поддержки экспериментов по поиску генов. Предложен и реализован метод точного предсказания экзон-интронной структуры генов при наличии гомологов, со средним уровнем предсказания 98-99% и гарантированно точным предсказанием приблизительно в одной трети случаев. Создан и поддерживается электронный сервер, осуществляющий такие предсказания по анонимным запросам. Обнаружены несколько новых генов человека. Произведен статистический анализ полных бактериальных геномов, в ходе которого показано избегание палиндромов длины 4-6. Показано, что это избегание связано с

эволюцией систем рестрикции-модификации. Предсказаны новые системы рестрикции-модификации в геноме архебактерии МеШапососсж}аппаисШ.

Апробация работы. Основные результаты были представлены на ГУ-УШ конференциях "Геном человека" (Черноголовка, 1993, 1994, 1996, Москва, 1997, Черноголовка, 1998), Школах по проблемам молекулярной биологии и биофизики (Черноголовка, 1993, Репино, 1996), Научных конференциях Института белка РАН (Пущино, 1993, 1995), Международном конгрессе "Компьютерные системы и прикладная математика С8АМ'93" (Санкт-Петербург, 1993), 1-м международном конгрессе по вычислительной медицине и биотехнологии (Остин, США, 1994), 3-й международной конференции по биоинформатике и геномным исследованиям (Таллахасси, США, 1994), Конференции "Комбинаторные методы картирования и секвенирования ДНК (Ратгерс, США, 1994), Конференции "Поиск генов и предсказание структуры генов" (Филадельфия, США, 1995), 5-й конференции программы "Геном человека" Министерства энергетики США (Санта-Фе, США, 1996), 11-й международной конференции по математическому и компьютерному моделированию (Вашингтон, США, 1997), Конференции по распознаванию генов (Колд Спринг Харбор, США, 1997), 5-й международной конференции по интеллектуальным системам для молекулярной биологии 18МВ'97 (Халкидики, Греция, 1997), 2-й международной конференции "Математический анализ биологических последвательностей" (Руан, Франция, 1997), Конференции Ньютоновского института "Статистический анализ нуклеотидных и белковых последовательностей (Кембридж, Великобритания, 1997), Конференции, посвященной 30-летию журнала "Молекулярная биология" (Москва, 1997).

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

Введение

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

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

Важность ее обусловлена тем, что эта задача практически эквивалентна предсказанию белков, закодированных в данном фрагменте, и тем самым является предпосылкой применения всей батареи методов анализа первичных последовательностей белков (поиск гомологов, предсказание пространственной структуры, предсказание функции и т.д.). Более того, предварительный компьютерный анализ может сыграть существенную, а иногда и решающую роль в экспериментах по идентификации генов. Только в 1996 компьютерный анализ был применен при идентификации генов b'MRl на хромосоме X, связанного с легкой олигофренией [69А], RPCG, мутированного при Х-связанном retinitis pigmentosa [69Б], генов синдрома ДиГеорге [70-71] и Х-связанной миотубулярной дистрофии [72], мышечноспецифичного гена ипс-89 нематоды Caenorhabditis elegans [73], а также при анализе альтернативного сплайсинга гена zipper дрозофилы, кодирующего тяжелую цепь немышечного миозина 11 [74j. При этом, в первых двух случаях ген вообще не мог быть обнаружен без предварительного сужения области поиска с применением компьютерного анализа.

Сложность же этой задачи связана с наличием у большинства белковых генов высших эукариот нетривиальной экзон-интронной структуры и относительно небольшим размером

экзонов (в среднем около 130 нп [75-76]), что препятствует применению таких традиционных техник, как анализ открытых рамок считывания и построение графиков кодирующего потенциала для скользящего окна.

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

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

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

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

0.1. экзон-интронная структура генов высших эукариот

В настоящее время существуют две основных теории происхождения интронов. Согласно одной (Гилберт [77-79], Блейк [80-82], Дулиттл [83], Сенапати [84] и др.), интроны существовали изначально и были потеряны у прокариот под давлением отбора в сторону экономии объема генома. Согласно второй (Кавалье-Смит [85], Хики [86-87] и др.), интроны появились у эукариот после разделения последних с прокариотами в результате действия ретропозон-подобного механизма.

Во многих случаях экзоны соответствуют функциональным [77, 88-89] и/или структурным [79-81, 88-90] доменам белков (критический обзор см. в [76], попытку опровержения - в [91]). Модульная структура многих семейств может быть результатом перестановки экзонов [92-93]. Во многих семействах генов имеются признаки потери, смещения и экзонизации интронов [94-97]. Согласно наблюдению Патти [93], дуплицированные или заимствованные экзоны должны иметь длину, кратную 3; действительно, такие экзоны встречаются чаще, чем в 33% случаев (например, [75, 98]).

С другой стороны, в некоторых случаях было показано внедрение интронов в существующие гены [92, 99-100]. Хики и соавт. [86-87] постулировали аналогию между интронами и ретропозонами, при помощи которой можно также объяснить случаи тасовки экзонов. Утверждается, что интроны встроились в подходящие места, из которых они могли выщепляться каким-либо предсуществующим механизмом. Такой подход позволяет объяснить, почему вставка интрона не разрушала белок-кодирующее сообщение, на что указывал еще Дулиттл [83]. Вероятная вставка интронов в ходе эволюции белковых семейств была показана Райтом [101].

Модель поздних интронов подтверждается также аналогиями между ядерным сплайсингом и самосплайсингом интронов типа II [102-103] и существовании транс-

сплайсинга в геномах кинетопластид и нематод с механизмом практически аналогичным обычному сплайсингу [104-105].

Следует отметить, что результаты эволюционного и. или структурного анализа позиций интронов в семействах гомологичных белков из разных таксономических групп часто бывают противоречивы. Среди примеров, вызвавших особую полемику, упомянем актины [100, 106-107], триозофосфат-изомеразы [79, 109-111], глицеральдегид-3-фосфат дегидрогеназы [91, 112-113].

Другим важным аспектом анализа экзон-интронной структуры является сам механизм сплайсинга, точнее, механизм узнавания концов одного интрона. В ряде ранних работ предполагалось наличие сканирующего механизма, который просматривал бы транскрипт в направлении от 5f конца к У концу и устанавливал соответствие между донорными и акцепторными сайтами [114], однако результаты опытов с дупликацией сайтов были противоречивы [115-118]. Хотя последовательной теории выбора сайтов при сплайсинге в настоящее время не существует, по современным представлениям такие механизмы могут быть различны в зависимости от длин соответствующих экзонов и интронов. В частности, при коротких интронах, каковыми являются многие интроны беспозвоночных, первоначальное узнавание происходит между донорным и акцептроным сайтами на левом и правом концах интрона соответственно, а при длинных интронах и коротких экзонах -узнаются акцепторный сайт на левом и донорный сайт на правом концах экзона [119-123].

В ряде работ экзон-интронная структура изучалась при помощи статистических методов. Было показано, что предпочитаются экзоны длины, кратной 3 [75] и интроны, расположенные между кодонами [75-76]. Во многих работах делались попытки предложить алгоритмы распознавания сайтов (обзоры см. в [14, 31]), и, хотя ни один алгоритм не позволяет осуществлять надежное предсказание, многие распознающие функции правильно предсказывают результаты мутаций [124-126]; показано также, что в ряде случаев истинный сайт имеет больший вес, чам сайтоподобные последвательности в прилегающих экзоне и интроне [127] (кроме того, удается обнаружить наиболее грубые ошибки в таблицах особенностей GenBank [128-129]).

Для дрозофилы и нематоды Caenorhabditis elegans были показаны различия в сигналах сплайсинга длинных и коротких интронов [130-131]. Заметим, что наблюдаемый в генах позвоночных in vivo и in vitro нижний предел длины интрона в 70 нт не соблюдается в генах беспозвоночных (до 50 нт у дрозофилы, до 40 нт у нематоды) и низших эукариот (до

50 нт у Tetrahymena, до 20-30 нт у Paramecium, у органеллы нуклеоморфа, родственного одноклеточным водорослям Chlamydomonas, большинство интронов имеют длину 18-20 нт). Наконец, были декларированы зависимости между длинами соседних экзонов, а также между степенью близости к консенсусу сайтов, соответствующих одному интрону [132].

В первой главе подробно рассмотрены статистические особенности экзон-интронной структуры ряда высших эукариот (млекопитающих, дрозофилы, нематоды, растений) [1,2, 7, 24, 34]. Ряд литературных данных не подтвердился, в то же время, было сделано много новых наблюдений.

0.2. Предсказание бе л ок-код и ру ющих областей в ДНК высших эукариот

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

Во-первых, использовался тот факт, что белок-кодирующие области обладают статистическими особенностями, отличающими их как от случайных последовательностей, так и от некодирующих областей. Был предложен целый ряд статистических функций ("кодирующих потенциалов"), измеряющих эти различия, в том числе: особенности употребления кодонов и синонимичных кодонов, отличия частот кодонов от частот тринуклеотидов в некодирующих областях, универсальные предпочтения кодонов типа RNY и GHN, слабую 3-периодичность кодирующих областей и позиционные предпочтения нуклеотидов, отличия в употреблении олигонуклеотидов в кодирующих и некодирующих областях и т.д. (обзоры см. в [3, 9, 14, 31,134-139]).

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

Методы, использующие отличия статистик кодирующих и некодирующих областей, позволяют "отстроиться" от общих особенностей ДНК, но они часто бывают

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

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

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

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

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

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

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

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

Далее рассматриваются всевозможные комбинации сайтов сплайсинга, каждая из которых определяет потенциальную экзон-интронную структуру (это означает, что должны быть соблюдены некоторые естественные условия, в частности - правильное чередование акцепторных и донорных сайтов). Каждая структура определяет возможную (зрелую) мРНК и характеризуется следующими параметрами: среднее качество предсказанных сайтов каждого типа {А для акцепторных сайтов и /) для донорных сайтов) и кодирующий потенциал всей мРНК С. Заметим, что, поскольку в возможной мРНК интроны уже сплайсированы, а экзоны непосредственно примыкают друг к другу, длина непрерывного белок-кодирующего участка достаточно велика для того, чтобы снизить влияние статистического шума.

Качество структуры характеризуется функцией

„ = Л-цДТУ-Г) , /)-МА/-1) , С-ц,./, аАЫ-Г) ' п^ГЕ '

Л V У АУ V .< О *

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

Рис. 1. Примеры предсказания при помощи традиционных методов. Ген химотрипсина крысы (ИАТСТКВ). Горизонтальная ось - позиция. Приведены предсказания донорных (а) и акцепторных (б) сайтов при помощи дискриминационной энергии (сильным сайтам соответствуют низкие значения; 0 - истинные сайты, х -ложные сайты). На рисунке (в) - график кодирующего потенциала ТевСоёе [140] (предсказанным кодирующим областям соответствуют высокие значения; горизонтальные линии - пороги предсказания кодирующий / отказ / некодирующий; ширина окна 120 нуклеотидов, шаг 15 нуклеотидов, позиция на графике соответствует середине окна). Под графиком горизонтальными линиями показаны истинные экзоны.

дискриминационная энергия с параметрами из [1], кодирующего потенциала - TestCode [140]. Структуры упорядочиваются по убыванию качества и несколько лучших (в идеале -одна) принимаются в качестве предсказания.

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

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

Были предложены различные попытки решить или обойти эти проблемы. В частности, алгоритм GenelD [143, 145] использует для сокращения перебора разделение экзонов на такие множества, что в каждой структуре может присутствовать лишь один представитель такого множества, а затем оставляет лишь лучший из экзонов в каждом множестве. GeneParser [148] испольует комбинацию динамического программирования и нейронной сети для опрделения оптимальных весов базовых параметров на этапе обучения и сокращения перебора на этапе распознавания. Различные эмпирические процедуры использованы в алгоритме Gen Viewer [146].

В алгоритме GRALL [141, 147], делается попытка сборки экзонов следующим образом. На первом этапе используется сочетание нейронной сети, в которой входными параметрами служат различные кодирующие потенциалы и примитивные признаки типа частот оли гонуклеотидов, с техникой скользящего окна. Далее для областей, в которых нейронная сеть предсказывает наличие закодированного белка, подбираются расположенные рядом сайты сплайсинга. Таким образом предсказываются отдельные экзоны. Для сборки потенциальных экзонов в экзон-интронную структуру используется специальная процедура GAP, использующая динамическое программирование.

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

Окончательным подтверждение белковой последовательности можно считать последовательность мРНК (разумеется остаются проблемы, связанные с точной идентификацией стартового кодона: хотя в подавляющем большинстве генов эукариот используется первый AUG от 5' конца матрицы, бывают и исключения [150-152]). Для поиска соответствующей матрицы при наличии фрагмента геномной ДНК осуществляется прямой скрининг клонотек кДНК, блоттинг по Нозерну, гибридизационная селекция кДНК и т.д. Лимитирующим фактором в таких экспериментах часто является неспецифическая гибридизация [153-154]. Для ее уменьшения применяется пре-гибридизация к повторяющимся последовательностям, а также ограничение области поиска на фрагменты ДНК, для которых имеются дополнительные основания подозревать наличие белок-кодирующей области. Для этого использоется zoo-blotting, селекция CpG-островков, амплификация экзонов (обзоры см., например, в [155-156]).

Серьезным ограничением во всех этих экспериментальных техниках является низкое отношение сигнал-шум в гибридизационных подходах и частые пропуски экзонов или ложные экзоны в методах амплификации экзонов. Например, эти методы не дали результата при поиске гена FMR1 на X хромосоме, связанного с легкой умственной недостаточностью [68] и гена RPGR, мутации в котором вызывают retinitis pigmentosa [69 j. Кроме того, многие из этих методов чрезвычайно трудоемки [153, 157].

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

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

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

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

В третьей главе описаны программы прямой поддержки эксперимента по идентификации генов [27, 30, 32]. Они позволяют осуществлять высокоспецифичное предсказание зондов для гибридизации и ПДР-праймеров, и таким образом экономят время и затраты на проведение экспериментов.

0.3. Предсказание белок-кодирующих областей с использованием

дополнительной информации

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

Идея использования банков данных для детекции генов была впервые высказана в [159]: в качестве кодирующих принимались участки, которые (после трансляции) имели сходство с уже известными белками (этот подход реализован в известной программе ВЬАЗТХ). Похожесть на уже известные гены может использоваться также как дополнительный параметр в многопараметрической распознающей процедуре [160], средство для выбора из нескольких (суб)оптимальных экзон-интронных структур примерно равного веса [161], либо даже служить основным параметром, характеризующим потенциальные экзоны [162]. Ряд существующих серверов производят поиск аналогов предсказанных экзонов по белковой базе данных в качестве стандартного постпроцессинга. Даже такой относительно примитивный подход позволяет существенно улучшить качество предсказаний [158]. Ясно, что с завершением ряда больших проектов по секвенированию геномов высших эукариот эти подходы будут приобретать все большее значение.

Последовательное использование информации о гомологах формализовано в алгоритме сплайсированного выравнивания, описанном в четвертой главе [20-21]. Следует отметить, что впервые пользователю вместе с предсказанием выдаются ожидаемая и гарантированная оценка его надежности (в отличие от существующих методов, которые указывают только среднее качество предсказаний) [33]. Тем самым, во многих случаях вообще отпадает практическая необходимость в проведении трудоемких экспериментов.

0.4. статистический анализ нуклеотидных последовательностей

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

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

последовательность [167-170]. Обширное сравнение различных марковских моделей содержится в [171-172].

Биомолекулярная лингвистика - термин, предложенный нами [6, 9] вместо термина "лингвистика нуклеотидных последовательностей", введенного Трифоновым [173]. В основе этого подхода лежит предположение, что олигонуклеотиды, частоты которых не могут быть предскааны достаточно простой случайной модель, имеют биологическое значение.

Простейший вариант данной техники - рассмотрение олигонуклеотидов, частоты которых не описываются моделью Бернулли. Было показано, что регуляторные сайты генов млекопитающих часто содержат редкие [174] или частые [175] олигонуклеотиды (впрочем, следует отметить, что в этих работах набор регуляторных сайтов определен крайне нечетко). Другой простой вариант - сравнение частот олигонуклеотидов в функционально различных областях ДНК (например, экзонах и интронах высших эукариот [176], на комплементарных цепях [177] или в различных геномах (эта область примыкает к построению филогенетических деревьев и поиску гомологий и выходит за рамки настоящего рассмотрения).

Более продвинутый подход, имеющий параллели в классической лингвистике (см. ниже), был предложен в [173, 178-181]. Пусть как обычно N(wv..wm) - частота (количество) олигонуклеотида W = wl...wm в обучающей выборке. Ожидаемое количество его появлений согласно марковской модели максимального порядка (т-2) составляет

K(wl ...wm) = N(wl... wm_1)N(w2... wj / N(w2 ... wm_!). Контраст определяется как нормированная разность между ожидаемой и наблюдаемой частотами

C{W) = T{W)I o(W), где а( W) - среднеквадратичное отклонение разности

T(W) = (N(W) - K(W)) /

1, - длина последовательности.

Первоначально [178-181] контраст измерялся как ( А'(И-) - А'(If)) / Var А'(¡V). В [178179] среднеквадратичное отклонение N вычислялось как Var K(W) = jK(W), однако в [181] было показано, что Var/V зависит от внутренних симметрий W, отраженных в его автокорреляционном многочлене (ср. [182-183]). Однако при этом считается, что параметры марковской цепи (переходные вероятности) известны. На самом же деле, эти

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

Распределение контраста на случайных последовательностей - это стандартное нормальное распределение с математическим ожиданием 0 и среднеквадратичным отклонением 1. Олигонуклеотид W считается предпочитаемым, если С(Ж)>3, и избегаемым, если C(iV)<3. Множество контрастных слов состоит из предпочитаемых и избегаемых олигонуклеотидов. В [178] было показано, что в Ё. coli избегаются многие комплементарные палиндромы длины 4-6. Следует отметить, что результаты такого рода, несмотря на стабильность основных тенденций, могут зависеть от в деталях от обучающей выборки и особенностей конкретного исследования. Например, TGC избегается в геноме Е. coli по данным [178] и предпочитается по данным [185]; аналогично, GÀGC избегается в геноме фага Т7 по данным [178] и предпочитается по данным [181].

Кроме того, при аккуратность требуется при интерпретации списков контрастных слов. Если по какой-либо причине слово сильно предпочитается, т.е. имеет большой положительный контраст, слова, отличающиеся от него в одной крайней позиции, будут автоматически иметь отрицательный контраст. Поэтому наблюдения [184] и в особенности работа [186], в которой на основании статистического анализа предполагается существование в Haemophilus influenzae специфического мутационного механизма, затрагивающего концы палиндромов, являются в лучшем случае сильно предварительными.

Проиллюстируем это простым примером [29]. Рассмотрим сбалансированную последовательность, в которой все слова имеют нулевой контраст, и добавим M экземпляров слова W = w1... wm. Обозначим первоначальные частоты слова W и его подслов через N = N(wv.. wm), Nm = JV(w,„. >ViX Amiddle = N(w2... wm_x). Частоты после добавления будут, соответственно, N' = N + M, М{ей = Nm + M, kiddie = A'middlc + M. Теперь рассмотрим слово W" =(wi...w^), отличающееся от W в единственной крайней позиции т. Положим N* = N(wx...w*n) и _/V*ght = N(w2... w*m). Изначально контраст PV* был равен нулю, и поэтому его наблюдаемая частота равнялась ожидаемой N" = N]éi / Nmidd[e. После увеличения наблюдаемая частота Ж* не

с72{W)

K(W)

изменилась, а ожидаемая чаСшта изменилась, поскольку изменились частоты подСлов wi ■ ■ ■ wm-1 и w2 ■ ■ ■ wm-i ■ Новая ожидаемая частота W* равна К'* = (Nle& + M)jV*2ht /(Nmiàdle + M), a разность наблюдаемой и ожидаемой частот после увеличения равна

N* — К'* = (Nleit - 7Vmiddle / (jVmiddle (Nmiddle + M)).

Все множители кроме первого очевидно положительны, а первый множитель отрицателен, так как w2... wm_x - это подслово wv.. wm_t, и поэтомуNm < /vrmiddlc. Это означает, что слово IV* имеет отрицательный контраст и кажется избегаемым.

Аналогично, если мы убираем M экземпляров слова W, слово W* будет иметь положительный контраст и казаться предпочитаемым.

Гомонуклеотидные последовательности с наибольшим трудом поддаются описанию марковскими моделями. Кластеризация аденинов (poiyA-тенденция) была замечена еще в 1980 [187-188]. Влияние третьей позиции кодона на polyS и polyW последовательности рассматривалось в [164]. Подробное рассмотрение гомонуклеотидных последовательностей было предпринято в [189]. Было показано, что как правило длинные гомонуклеотидные блоки предпочитаются в некодирующих областях и избегаются в кодирующих, однако есть исключения: polyÀ и poly Г предпочитаются как в кодирующих, так и в некодирующих областях прокариот, polyR и poly Y - в обоих типах областей эукариот. polyG и polyC блоки избегаются в прокариотах и кодирующих областях эукариот и предпочитаются в некодирующих областях эукариот. polyS и polyW блоки предпочитаются в некодирующих областях как прокариот, так и эукариот. В [190] рассматривались другие регулярные последовательности: poIy(TG/CÂ) и poly(CT/ÀG).

Сложность олигонуклеотидов и ее связь с частотой рассматривалась в [191]. Сложность определялась как энтропия олигонуклеотида: пусть в состав олигонуклеотида Wдлины m входит п(Ь) оснований типа Ь (b = A,T,G,C); У_^п(Ь) = т. Тогда

" ! - /, '"62

4 m m

Как обычно, обозначим через F{W) частоту олигонуклеотида ¡У в обучающей выборке. Были рассмотрены октануклеотиды в белок-кодирующих и некодирующих областях прокариот и эукариот. Оказалось, что в обеих выборках эукариотических последовательностей существует положительная корреляция между F{W) и H{W). С другой стороны, средняя энтропия октануклеотидов в кодирующих областях выше, чем в

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

Лингвистические аналогии. Многие методы, рассмотренные выше, имеют близкие параллели в лингвистической теории дешифровочных моделей. Некоторые из этих аналогов, а именно, алгоритмы выделения морфем в тексте без пробелов, будут рассмотрены в этом разделе. При этом мы оставляем в стороне как общесемиотические проблемы, так и некоторые другие применения лингвистических понятий в анализе ДНК. Подробное обсуждение этих вопросов содержится в [5, 13].

Первый алгоритм сегментации текста на морфемы был предложен в [192]. Он основан на том, что морфемы встречаются в более разнообразном окружении, чем произвольные отрезки текста. Наиболее развитая система морфемной сегментации была предложена в [193]. Морфемы определяются как цепочки символов, обладающие внутренней стабильностью (появление части морфемы хорошо предсказывает появление всей морфемы) и внешней стабильностью, т.е. способностью морфемы встречаться в разнообразных локальных контекстах. Пусть - цепочка букв, а, Ь, х, у - отдельные буквы. Были предложены несколько определений стабильности, например,

\maSb) ЩаХЬ)I [ЩаЗЪу) Ы{ха8Ь)\

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

Следует отметить, что, несмотря на сходство этих подходов с техникой, применяемой в биомолекулярной лингвистике, необходимо учитывать два существенных отличия текстов на естественных языках (во всяком случае тех европейских языках, для которых разрабатывались данные алгоритмы) от последовательностей ДНК:

(Г) морфемы не перекрываются;

(2) каждая морфема принадлежит по меньшей мере одной (по свойству (1) - ровно одной) морфеме.

Заключение диссертации по теме «Молекулярная биология», Гельфанд, Михаил Сергеевич

Выводы Основные результаты

Приведем основные результаты настоящего исследования (по главам).

I. Произведено статистическое исследование сайтов сплайсинга и экзон—интронной структуры генов высших эукариот (млекопитающих, дрозофилы, нематоды, растений).

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

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

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

Обнаружена положительная корреляция между длинами соседних экзонов.

Показано предпочтение экзонов типа О (имеющих длину, кратную 3) и интронов, расположенных между кодонами. Впервые обнаружено предпочтение пар экзонов типа 0 — 0, 1—2 и 2—1 и избегание пар неО — 0 и 0 —неО, что согласуется с гипотезой о тасовании (перестановке и вставке) экзонов.

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

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

Показана зависимость сигнала сплайсинга от GC — содержания прилегающей области генома.

IL Разработан новый алгоритм распознавания генов и предсказания экзон—интронной структуры в последовательностях ДНК высших эукариот.

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

III. Предложен новый комбинаторньш подход к проблеме компьютерной поддержки экспериментов по поиску генов.

Построен, реализован и тестирован метод высокоспецифичного предсказания кодирующих сегментов. Создана программа Cassandra, доступная как отдельный модуль или по электронным сетям (bttp://www— hto.usc.edu/software/procrastes/ cassandra), которая предназначена для использования в экспериментальной практике при конструировании олиготтуклеотидных зондов и затравок ПЦР с последующим анализом библиотек кДНК и тотальной клеточной мРНК. В отличие от существующих методов, предложенный алгоритм базируется на простых статистических параметрах (частоты кодонов и позиционные частоты нуклеотидов в сайтах сплайсинга) и таким образом может быть использован при работе с относительно малоизученными геномами, для которых недоступны большие обучающие выборки. Структура алгоритма позволяет легко приспосабливать его к разнообразным запросам экспериментатора.

IV. Предложен и реализован метод точного предсказания экзон— интронной структуры генов при наличии гомологов.

Создан, реализован и тестирован алгоритм сплайсированного выравнивания. Создана программа Procrustes, доступная как отдельный модуль или по электронным сетям (http://www—hto.usc.edu/software/procrustes), которая предназначена для анализа генов, имеющих известных гомологов. При тестировании оказалось, что качество предсказания при использовании гомологов из геномов млекопитающих составляет 99%, причем точно предсказываются более 85% генов, а при гомологах из других таксономических групп — 93 — 97%. Впервые пользователю предоставляется информация об ожидаемом и гарантированном качестве индивидуальных предсказаний (а не о среднем качестве на выборке). При тестировании был исправлен ряд ошибок GenBank, в частности, обнаружены случаи неаннотированного альтернативного сплайсинга. Программа широко используется в экспериментальной практике.

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

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

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

На основе статистического анализа ДНК и анализа белковых гомологий в геноме Methanococcus jannaschii предсказаны две пары генов (метилаз и эндонуклеаз) со специфичностью GATC и GTYRAC; вторая система — первый пример системы с гексануклеотидным сайтом узнавания в этой архебактерии.

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

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

Для слов с регулярной структурой показано, что вероятно появление X непосредственно перед и после ХХХХ и после ХТХ7., а также Z перед (X и Z — произвольные нуклеотиды), что является проявлением общей тенденции распределения длин регулярных блоков к смещению в область больших значений по сравнению с марковской моделью.

Продолжаемость слов с бедным нуклеотидным составом характерна для последовательностей эукариот. Относительно мала вероятность СиС после и перед Ш\ЛАЛАУ; перед 5888 мала вероятность А и велика вероятность С, аналогично после Я88Я предпочитается С и избегается Т. Продолжаемыми вправо являются также слова вида УУУУ и ММММ, а продолжаемыми влево

- ШШ1 и КККК (Я - пурин, Y - пиримидин, Ш - А или Тт 8 - С или С, М

А или С, К — в или Т) .

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

Разработан новый метод оценки статистической значимости наблюдаемых особенностей для классов слов.

Список работ по теме диссертации

Статьи в реферируемых изданиях

1. Гельфанд М.С. Статистический анализ областей сплайсинга млекопитающих // Молекулярная биология. 1989. Т. 23. № 5. 1428-1439.

2. Gelfand M.S. Statistical analysis of mammalian pre-mRNA splicing sites // Nucl. Acids Res. 1989. V. 17. N. 15. 6369-6382.

3. Gelfand M.S. Global methods for the computer prediction of protein-coding regions in nucleotide sequences // Biotechnology Software. 1990. V. 7. N. 4. P. 3-11.

4. Gelfand M.S. Computer prediction of the exon-intron structure of mammalian pre-mRNAs // Nucl. Acids Res. 1990. Y. 18. N. 19. P. 5865-5869.

5. Гельфанд М.С. Коды генетического языка и естественный язык // Вопросы языкознания. 1990. № 6. С. 60-70.

6. Gelfand M.S., Kozhukhin C.G., Pevzner P.A. Extendable words in nucleotide sequences // Comput. Appl. Biosci. 1992. Y. 8. N. 2. P. 129-135.

7. Gelfand M.S. Statistical analysis and prediction of the exonic structure of human genes //J. Mol. Evol. 1992. Y. 35. N. 2. P. 239-252.

8. Gelfand M.S., Roytberg M.A. Prediction of the exon-intron structure by a dynamic programming procedure // Biotechnology Software. 1993. V. 10. N. 1. P. 13-18.

9. Gelfand M.S. Computer functional analysis of nucleotide sequences: problems and approaches // Mathematical Methods of the Analysis of Biopolymer Sequences. Gindikin S.G., ed. / Providence: AMS, 1992. P. 19-61.

10. Gelfand M.S. Prediction of protein-coding regions in DNA of higher eukaryotes // Mathematical Methods of the Analysis of Biopolymer Sequences. Gindikin S.G., ed. / Providence: AMS, 1992. P. 87-98.

11. Gelfand M.S. Prediction of protein-coding regions interrupted by introns // Modelling and Computer Methods in Molecular Biology and Genetics. Ratner V.A., Kolchanov N.A., eds. / New York: Nova Science, 1992. P. 81-86.

12. Gelfand M.S., Roytberg M.A. A dynamic programming algorithm for prediction of the exon-intron structure//BioSystems. 1993. V. 30. P. 173-182.

13. GelfandM.S. Genetic language: metaphore or analogy //BioSystems. 1993. V. 30. P. 277-288.

14. Gelfand M.S. Prediction of function in DNA sequence analysis // J. Сотр. Biol. 1995. V. 2. P. 87-117.

15. Razgulyaev O., Rubinov A., Gelfand M., Chetverin A. Sequencing potential of nested strand hybridization // J. Сотр. Biol. 1995. V. 2. P. 383-395.

16. Rubinov A.R., Gelfand M.S. Reconstruction of a string from substring precedence data //J. Сотр. Biol. 1995. V. 2. P. 371-381.

17. Gelfand M.S., Podolsky L.I., Astakhova T.V., Roytberg M.A. Prediction of the exon-intron structure and multicriterial optimization // Lim H.A., Cantor C.R., eds. Bioinformatics and Genome Research. / World Scientific, 1995. P. 173-180.

18. Gelfand M.S. FANS-REF - a bibliographic reference data bank on statistics and functional analysis of nucleotide sequences // Comput. Appl. Biosci. 1995. V. 11. P. 541.

19. Gelfand M.S., Podolsky L.I., Astakhova Т. V., Roytberg M.A. Recognition of genes in human DNA sequences // J. Comput. Biol. 1996. V. 3. P. 223-234.

20. Gelfand M.S., Mironov A. A., Pevzner P. A. Spliced alignment: a new approach to gene recognition//Lect. Notes in Computer Science. 1996. V. 1075. P. 141-158.

21. Gelfand M.S., Mironov A.A., Pevzner P.A. Gene recognition via spliced sequence alignment //Proc. Natl. Acad. Sci. USA. 1996. V. 93. P. 9061-9066.

22. Gelfand M.S., Astakhova T.V., Roytberg M.A. An algorithm for highly specific recognition of protein-coding regions // Genome Informatics 1996 / Tokyo: Universal Academy Press, 1996. P. 82-87.

23. Гельфанд M.C., Чжао Минь. О ранговых распределениях частот букв в естественных языках//Проблемы передачи информации. 1996. Т. 32. С. 89-95.

24. ГЦепетковаИ.Л., Гельфанд М.С. Некоторые статистические особенности сайтов сплайсинга позвоночных и бекпозвоночных//Биофизика. 1997. Т. 42. № 1. С. 8291.

27. Ройтберг М.А., Астахова Т.В., Гельфанд М.С. Комбинаторный алгоритм для высокоспецифичного распознавания белок-кодирующих областей в последовательностях ДНК высших эукариот // Молекулярная биология. 1997. Т. 31. № 1.С. 26-32.

28. Гельфанд М.С., Пугачев В.В., Евграфов О.В. Новый член семейства повторов MER2 обнаружен в промоторной области гена XI1 человека // Доклады РАН. 1997. Т. 354. № 5. С. 690-695.

29. Gelfand M.S., Koonin E.V. Avoidance of palindromic words in bacterial and archaeal genomes: a close connection with restriction enzymes // Nucleic Acids Res. 1997. V. 27. P. 2430-2439.

30. Roytberg M.A., Astakhova T.V., Gelfand M.S. Combinatorial approaches to gene recognition//Comput. Chem. 1997. V. 21. P. 229-235.

31. Гельфанд М.С. Компьютерный анализ последовательностей ДНК // Молекулярная биология. 1998. Т. 32. № 1. С. 107-124.

32. Sze S.-H, Roytberg М.А., Gelfand M.S., Mironov A.A., Astakhova T.V., Pevzner P.A. Algorithms and software for support of gene identification experiments // Bioinformatics (in press).

33. Mironov A.A., Roytberg M.A., Pevzner P.A., Gelfand M.S. Performance guarantee gene predictions via spliced alignment // Genomics (in press).

34. КривенцеваЕ.В., Макеев В.Ю., Гельфанд М.С. Статистический анализ экзон-интронной структуры генов высших эукариот // Биофизика (в печати).

35. Назипова Н.Н., Коровина Т.Б., Овербик Р., Гельфанд М.С. Статистический анализ и предсказание бактериальных сайтов связывания рибосом // Биофизика (в печати).

Другие публикации

36. Pevzner Р.А., Gelfand M.S., eds. Computer Genetics. A special issue on computational molecular biology //BioSystems. 1993. V. 30.

37. Гельфанд М.С. FANS-REF: библиография работ по статистике и предсказанию функций нуклеотидных последовательностей // 3-я конференция "Геном человека -93"/Черноголовка. 1993. С. 116.

38. Подольский Л.И., Ройтберг М.А., Гельфанд М.С. Предсказание экзон-интронной структуры и динамическое программирование над недистрибутивными полукольцами // 3-я конференция "Геном человека - 93" / Черноголовка. 1993. С. 130.

39. Сприжицкий Ю.А., Шепелев В.А., Голованов Е.И., Гельфанд М.С. Интегрированные базы данных характеристик и поисковых моделей функциональных сигналов на молекулах нуклеиновых кислот // 3-я конференция "Геном человека - 93" / Черноголовка. 1993. С. 138.

40. Borodovsky М., Gelfand M.S. Prediction of exons by the maximum likelyhood approach // Int. Congr. on Computer Science and Applied Mathematics CSAM'93 / St. Petersburg. 1993. P. 153-154.

41. Gelfand M.S. Prediction of function in DNA sequence analysis // Int. Congr. on Computer Science and Applied Mathematics CSAM'93 / St. Petersburg. 1993. P. 155156.

42. Roytberg M.A., Podolsky L.I., Gelfand M.S. Prediction of the exon-intron structure by the vecor dynamic programming approach // Int. Congr. on Computer Science and Applied Mathematics CSAM'93 / St. Petersburg. 1993. P. 163.

43. Rubinov A.R., Razgulyaev O.I., Nakipov R.F., Gelfand M.S, Chetverin A.B. Reconstruction of a symbol sequence given information about k-tuple precedence // Int. Congr. on Computer Science and Applied Mathematics CSAM'93 / St. Petersburg. 1993. P. 165.

44. Rubinov A.R., Gelfand M.S., Ivanov M.Y., Spirin S.A., Razgulyaev O.I., Nakipov R.F., Chetverin A.B. Computer modeling of sequencing by nested strand hybridization // Int. Workshop on Sequencing by Hybridization / Woodlands TX, 1993. P. 35.

45. Rubinov A.R., Gelfand M.S., Razgulyaev O.I., Chetverin A.B. Comuter analysis of sequencing by nested strand hybridization // 1st Int. Congr. on Computational Medicine and Biotechnology / Austin TX. 1994.

46. Gelfand M.S. Prediction of the exon-intron structure and multicriterial optimization // 3rd Int. Conf. on Bioinformatics and Genome Research / Tallahassee FL. 1994. P. 39.

47. Gelfand M.S. FANS-REF - a bibliography on statistical and functional analysis of nucleotide sequences // 3rd Int. Conf. on Bioinformatics and Genome Research / Tallahassee FL. 1994. P. 74-75.

48. Gelfand M.S., Podolsky L.I., Astakhova T.V., Roytberg M.A. Recognition of genes in human DNA sequences // Pennsylvania State University. 1994. Technical Report CSE-94-059.

49. Gelfand M.S. Prediction of function in DNA sequence analysis // Pennsylvania State University. 1994. Technical Report CSE-94-060.

50. Gelfand M.S., Rubinov A.R., Razgulyaev O.I., Chetverin A.B. Mathematical aspects of sequencing by nested strand hybridization // Workshop on Combinatorial Methods for DNA Mapping and Sequencing / DIMACS, Rutger University, 1994.

51. Gelfand M.S., Mironov A.A., Pevzner P.A. Spliced alignment: a new approach to gene recognition // Pennsylvania State University. 1995. Technical Report CSE-95-019.

52. Gelfand M.S., Roytberg M.A. Dynamic programming for gene recognition // Конференция "Математические методы распознавания образов / Пущино, 1995. С. 85-86.

53. Pevzner Р.А., Gelfand M.S., Mironov A.A., Sze S.-H. Spliced alignment: a new (and naive) approach to gene recognition // Gene-Finding and Gene Structure Prediction Workshop/Philadelphia PA, 1995.

54. Gelfand M.S., Roytberg M.A. Dynamic programming for gene recognition // Gene-Finding and Gene Structure Prediction Workshop / Philadelphia PA, 1995.

55. Ройтберг M.A., Астахова T.B., Гельфанд М.С. Надежное распознавание белок-кодирующих областей и конструирование олигонуклеотидных зондов // 5-я конференция "Геном человека - 96" / Черноголовка. 1996. С. 103-104.

56. Гельфанд М.С., Миронов А.А., Певзнер П.А. Сплайсированное выравнивание: новый подход к распознаванию генов в ДНК человека // 5-я конференция "Геном человека - 96" / Черноголовка. 1996. С. 107-108.

57. Щепеткова И.Л., Гельфанд М.С. Статистический анализ сайтов сплайсинга // 5-я конференция "Геном человека - 96" / Черноголовка. 1996. С. 112.

58. Pevzner P.A., Gelfand M.S., Mironov A.A. Gene recognition: combinatorics versus statistics // 2nd Sandia National Laboratories Workshop on Computational Molecular Biology / Albuquerque NM, 1996.

59. Gelfand M.S., Mironov A.A., Pevzner P.A. Spliced alignment: a new approach to gene recognition // DOE Human Genome Program. Contractor-Grantee Workshop V / Santa Fe NM, 1996. P. 170.

60. Gelfand M.S., Mironov A.A., Pevzner P.A. Spliced alignment: a similarity-based algorithm for gene recognition // Folding & Design. 1996. V. 1. P. 62.

61. Gelfand M., Mironov A., Roytberg M., Pevzner P. Gene prediction problems that can be solved (almost) exactly //11th Int. Conf. on Mathematical and Computer Modelling and Scientific Computing / Washington DC, 1997. P. 105.

62. Gelfand M. Prediction of function in DNA sequence analysis (tutorial) // 5th Int. Conf. on Intelligent Systems for Molecular Biology / Halkidiki, Greece, 1997.

63. Gelfand M.S., Koonin E.V. Avoidance of palindromes in prokaryote genomes: a close connection with restriction-modification (R-M) systems // Analyse Mathematique des Sequences Biologiques / Rouen, France, 1997. P. 27.

64. Pevzner P.A. et al. Combinatorial gene recognition. U.S. Patent application 60/035,720.

65. Астахова T.B., Гельфанд M.C., Миронов A.A., Певзнер П.А., Ройтберг M.A. Комплекс программ для распознавания белок-кодирующих областей в ДНК человека // 8-я конференция "Геном человека - 98" / Черноголовка. 1998. С. 42-43.

66. КривенцеваЕ.В., Макеев В.Ю., Гельфанд М.С. Статистический анализ экзон-интронной структуры генов высших эукариот // 8-я конференция "Геном человека - 98" / Черноголовка. 1998. С. 43.

67. Гельфанд М.С., Ройтберг М.А., Тверская С.М., Евграфов О.В. Разработка метода идентификации и анализа новых генов на основе компьютерного анализа Д НК // 8-я конференция "Геном человека - 98" / Черноголовка. 1998. С. 43-44.

Список литературы диссертационного исследования доктор биологических наук Гельфанд, Михаил Сергеевич, 1998 год

ЛИТЕРАТУРА

68А. Sulston J., Du Z., Thomas К., Wilson R, Hillier L., Staden R., Halloran N., Green P., Thieny-Mieg J., Qui L., Dear S., Coulson A., Craxton M., Durbin R., Berks M., Metzstein M., Hawkins Т., Ainscough R., Waterson R. The C. elegans genome sequencing project: a beginning//Nature. 1992. V. 356. P. 37-41.

68Б. Oliver S.G et al. The complete sequence of yeast chromosome I // Nature. 38-46.

68В. Баев А.А., Мирзабеков А.Д., Беляева H.H. Структурное исследование генома человека // Итоги науки и техники. Сер. Геном человека. Т. 2. М. ВИНИТИ. 1994.

69A. Gu Y., Shen Y., Gibbs R.A. Nelson, D.L. Identification of FMR2, a novel gene associated with the FRAXE CCG repeat and CpG island // Nature Genet. 1996. V. 13. P. 109-113.

69Б. Meindl A., Dry K., Herrmann K., Manson F., Ciccodicola A., Edgar A., Carvalho M.R.S., Achatz H, Hellebrand H., Lennon A., Migliaccio C., Porter K., Brenner E., Bird A., Jay M., Lorenz В., Wittwer В., D'Urso M., Meitinger Т., Wright A. A gene

(RPGR) with homology to the RCC1 guanin nucleotide exchange factor is mutated in X-linked retinitis pigmentosa (RP3) // Nature Genet. 1996. V. 13, P. 35-42.

70. Goldmuntz E., Wang Z., Roe B.A., Budarf M.L. Cloning, genomic organization, and chromosomal localization of human citrate transport protein to the DiGeorge/ velocardiofacial syndrome minimal critical region // Genomics. 1996. V. 33, P. 271276.

71. Budarf M.L., Collins J., Gong W., Roe B., Wang Z., Bailey C.L., Sellinger B., Michaud D., Driscoll D.A., Emanuel B.S. Cloning a balanced translocation associated with DiGeorge syndrome and identification of a disrupted candidate gene // Nature Genet. 1995. V. 10, P. 269-278.

72. Laporte J., Hu L.J., Kretz C„ Mandel J.-L., Kioschis P., Coy J.F., Klauck S.M., Poustka A., Dahl N. A gene mutated in X-linked myotubular myopathy defines a new putative tyrosine phosphatase family conserved in yeast // Nature Genet. 1996. V. 13, P. 175182.

73. Benian G.M., Tinley T.L., Tang X., Borodovsky M. The Caenorhabditis elegans gene unc-89, required for muscle M-line assembly, encodes a giant modular protein composed of Ig and signal transduction domains // J. Cell Biol. 1996. V. 132, P. 835848.

74. Mansfield S.G., Al-Shirawi D.Y., Ketchum A.S., Newbern E.C., Kiehart D.P. Molecular organization and alternative splicing in zipper, the gene that encodes the Drosophila non-muscle myosin II heavy chain // J. Mol. Biol. 1996. V. 255, P. 98-109.

75. Smith M.W. Structure of vertebrate genes: a statistical analysis imlicating selection // J. Mol. Evol. 1988. V. 27. P. 45-55.

76. Traut T.W. Do exons code for structural or functional units? // Proc. Nat. Acad. Sci. USA. 1988. V. 85. P. 2944-2948.

77. Gilbert W. Why genes in pieces? // Nature. 1978. V. 271. P. 501.

78. Gilbert W. Genes-in-pieces revisited// Science. 1985. V. 228. P. 823-824.

79. Gilbert W., Marchionni M., McKnight G. On the antiquity of introns // Cell. 1986. V. 46. P. 151-154.

80. Blake C.C.F. Do genes-in-pieces imply proteins-in-pieces //Nature. 1978. V. 273. P. 267.

81. Blake C.C.F. Exons - present from the beginning//Nature. 1983. V. 306. P. 535-537.

82. Blake C.C.F. Exons and the evolution of proteins // Int. Rev. Cytol. 1985. V. 93. P. 149-185.

83. Doolittle W.F. Genes in pieces - were they ever together // Nature. 1978. V. 272. P. 581-582.

84. Senapathy P. Origin of eukaryotic introns: a hypothesis, based on codon distribution statistic in genes, and its implications // Proc. Nat. Acad. Sci. USA. 1986. V. 83. P. 2133-2137.

85. Cavalier-Smith T. Selfish DNA and the origin of introns // Nature. 1985. V. 315. P. 283-284.

86. Hickey D.A., Benkel B. Introns as relic retrotransposons: implications for the evolutionary origin of eukaryotic mRNA splicing mechanisms // J. Theor. Biol. 1986. V. 121. P. 283-291.

87. Hickey D.A., Benkel B.F., Abukashawa S.M. A general model for the evolution of nuclear pre-mRNA introns //J. Theor. Biol. 1989. V. 137. P. 41-53.

88. Stone M.E., Rothblum K.N., Schwartz R.J. //Nature. 1985. V. 313. P. 498.

89. Go M. Correlation of DNA exonic regions with protein structural units in haemoglobin //Nature. 1981. V. 291. P. 90-92.

90. Go M. Modular structural units, exons and function in chicken lysozime // Proc. Nat. Acad. Sci. USA. 1983. V. 80. P. 1964-1968.

91. Stoltzfus A. //Nature. 1994. V. 369. P. 526-527.

92. Patthy L. Evolution of proteases of blood-coagulation and fibrinolysis by assembly from modules // Cell. 1985. Y. 41. P. 657-663.

93. Patthy L. Intron-dependent evolution - exon shuffling and intron insertion in serine protease genes // FEBS Lett. 1987. V. 214. P. 1-7.

94. Buttice G., Kaytes P., D'Armiento J. et al. Evolution of collagen IV genes from a 54-base air exon: a role for introns in gene evolution // J. Mol. Evol. 1990. V. 30. P. 479488.

95. Craik C.S., Rutter W.J., Fletterick R. Splice junctions: association with variation in protein structure // Science. 1983. V. 220. P. 1125-1129.

96. Rogers J. Introns between protein domains: selective insertion or frameshifting? // Trends Genet. 1986. V. 2. P. 223.

97. Parma J., Cristophe D., Pohl V., Vassart G. Structural organization of the 5' region of the thyroglobin gene. Evidence for intron loss and "exonization" during evolution // J. Mol. Biol. 1987. V. 196. P. 769-779.

98. Demchuk E .J., Esipova N.G., Tumanyan V.G. Length regularities of genetic texts // Electrophoresis, Supercomputing and the Human Genome (Abstr. 1st. Int. Conf., Tallahassee, USA, 1990). P. 279-285.

99. Rogers J. Split gene evolution - exon shuffling and intron insertion in serine protease genes //Nature. 1985. V. 315. P. 458-459.

100. Dibb N.J., Newman A.J. Evidence that introns arose at proto-slice junctions // EMBO J. 1989. V. 8. P. 2015-2021.

101. Wright HT. //J. Mol. Evol. 1993. V. 36. P. 136-143.

102. Michel F., Umesono K., Ozeki H. // Gene. 1989. V. 82. P. 5-30.

103. Madhani H.D., Guthrie C. //Annu. Rev. Genet. 1994. V. 28. P. 1-26.

104. Agabian N. // Cell. 1990. V. 61. P. 1157-1160.

105. Blumenthal T. //Trends Genet. 1995. V. 11. P. 132-136.

106. Weber K. Kabsch W. // EMBO J. 1994. V. 13. P. 1280-1286.

107. Nyberg A.M., Cronhjort M.B. //J. Theoret. Biol. 1992. V. 157. P. 175-190.

108. Tittiger C„ Whyard S., Walker V.K. //Nature 1993. V. 361. P. 470-472.

109. Dibb N.J. //FEBSLett. 1993. V. 325. P. 135-139.

110. Kwiatkowski J., Krawczyk M., Kornacki M., Bailey K., Ayala F.J. // Proc. Natl. Acad. Sci. 1995. V. 92. P. 8503-8506.

111. Logsdon Jr. J.M., TyshenkoM.G., Dixon C., D.-Jafari J., Walker V.K., Palmer J.D. // Proc. Natl. Acad. Sci. USA. 1995. V. 92. P. 8507-8511.

112. Kersanach R., Brinkmann H, Liaud M.F., Zhang D.X., Martin W., CerffR. // Nature. 1994. V. 367. P. 387-389.

113. Logsdon Jr. J.M., Palmer J.D. //Nature. 1994. V. 369. P. 526.

114. Aebi M„ Weissmann C. // Trends Genet. 1987. V. 3. P. 102.

115. Kuhne T., WieringaB., Weissmann C. // EMBO J. 1983. V. 2. P. 727.

116. Lang K.M., Spritz R.A. // Science. 1983. V. 220. P. 1351.

117. ReedR., Maniatis T. // Cell. 1986. V. 46. P. 681.

118. Reed R., Maniatis T. // Genes Devel. 1988. V. 2. P. 1268.

119. Robberson B.L., Cote G.J., Berget S.M. // Mol. Cell. Biol. 1990. V. 10. P. 84.

120. Guo M., Lo. P.C.H., Mount S.M. //Mol. Cell. Biol. 1993. V. 13. P. 1104.

121. Talerico M., Berget S.M. // Mol. Cell. Biol. 1994. V. 14. P. 3434.

122. McCullough A., Blanton J., Carlo T., Kennedy C., Searls D., Berget S.M. // Abstr. "RNA Processing" Meeting, Cold Spring Harbor, NY, USA, May 17-21, 1995. P. 23.

123. Sterner D.A., Carlo T., Berget S.M. //Proc. Natl. Acad. Sci. USA. 1996. V. 93. P. 15081.

124. Iida Y. Quantification analysis of 5-splice site signal sequences in mRNAprecursors. Mutations in rabbit p-globin gene // Biochim. Biophys. Acta. 1989. V. 1007. P. 270276.

125. Iida Y. Quantification analysis of 5'-splice site signal sequences in mRNA precursors. Mutations in 5'-splice signal sequence of human P-globin gene and ^-thalassemia // J. Theor. Biol. 1990. V. 145. P. 523-534.

126. Iida Y. Nucleotide sequence analysis of human P-globin by the quantification method: mutations in 3'-splice junction sequence and P-thalassemia // J. Biochem. 1990. V. 108. P. 934-937.

127. Ohshima Y., Gotoh Y. Signals for the selection of a splicing site in pre-mRNA. Computer analysis of splice junction sequences and like sequences // J. Mol. Biol. 1987. V. 195. P. 247-259.

128. Brunak S., Engelbrecht J., Knudsen S. Cleaning up gene databases // Nature. 1990. V. 343. P. 123.

129. Brunak S., Engelbrecht J., Knudsen S. Neural network detects errors in the assignment of mRNA splice sites //Nucl. Acids Res. 1990. V. 18. P. 4797-4801.

130. Fields C.A. //Nucleic Acids Res. 1990. V. 18. P. 1509.

131. Mount S.M., Burks C., Hertz G., Stormo G.D., White O., Fields C. // Nucleic Acids Res. 1992. V. 20. P. 4255.

132. Zhang M.Q., Marr T.G. // Proc. Gene Finding and Gene Structure Prediction Workshop, Philadelphia, PA, USA, October 13-14,1995.

134. Fickett J.W. The gene identification problem: An overview for developers // Comput. Chem. 1996. V. 20. P. 103-118.

135. Fickett J.W. Finding genes by computer: the state of the art // Trends Genet. 1996. V. 12. P. 316-320.

136. Staden R. Measurements of the effect that coding for a protein has on a DNA sequence and their use for finding genes // Nucl. Acids Res. 1984. V. 12. P. 551-567.

137. Бородовский М.Ю. Предсказание кодирующих областей в нуклеотидных последовательностях // Компьютерный анализ генетических текстов (Франк-Каменецкий М.Д., ред.) / М. "Наука". 1990. С. 81-112.

138. Staden R. Finding protein coding regions in genomic sequences // Meth. Enzymol. 1990. V. 183. P. 163-179.

139. Fickett J.W., Tung C.-S. Assessment of protein coding measures //Nucl. Acids Res. 1992. V. 20. P. 6441-6450. ,

140. Fickett J.W. Recognition of protein coding regions in DNA sequences // Nucl. Acids Res. 1982. V. 10. P. 5303-5318.

141. Einstein J.R., Uberbacher E.C., Guan X., Mural R.J., Mann R.C. GAP - a computer program for gene assembly // Prerint. ORNL/TM-11934, Martin Marietta Energy Systems, Inc., Oak Ridge National Laboratory, September 1991.

142. Farber R., Lapedes A., Sirotkin K. Determination of eukaryotic protein coding regions using neural networks and information theory // J. Mol. Biol. 1992. V. 226. P. 471-479.

143. Guigo R., Knudsen S., Drake N., Smith T. Prediction of gene structure // J. Mol. Biol. 1992. V. 226. P. 141-157.

144. Fields C., Adams M.D., Kerlavage A.R., Dubnick M., McCombie W.R., Martin-Gallardo A., White O., Venter J.C. Identification of genes in genomic and EST sequencies // The Second International Conference on Bioinformatics, Supercomputing and Complex Genome Analysis (StPetersburg, FL, 1992) (Lim H.A., Fickett J.W., Cantor C.R., Robbins R.J., eds.) / World Scientific. Singapore. 1993. P. 429-433.

145. Knudsen S., Guigo R., Smith T. GenelD - a computer server for prediction of genes in DNA sequences // The Second International Conference on Bioinformatics, Supercomputing and Complex Genome Analysis (St.Petersburg, FL, 1992) (Lim H.A., Fickett J.W., Cantor C.R., Robbins R.J., eds.) / World Scientific. Singapore. 1993. P. 545-553.

146. Milanesi L., Kolchanov N.A., Rogozin I.B., Ischenko I.V., Kel A.E., Orlov Y.L., Ponomarenko M.P., Vezzoni P. Gen Viewer: a computing tool for protein-coding regions prediction in nucleotide sequences // The Second International Conference on Bioinformatics, Supercomputing and Complex Genome Analysis (St.Petersburg, FL,

1992) (Lim H.A., Fickett J.W., Cantor C.R., Robbins R.J., eds.) / World Scientific. Singapore. 1993. P. 573-587.

147. Uberbacher E.C., Einstein J.R., Guan X., Mural R.J. Gene recognition and assembly in the GRAIL system: progress and challenges // The Second International Conference on Bioinformatics, Supercomputing and Complex Genome Analysis (St. Petersburg, FL, 1992) (Lim H.A., Fickett J.W., Cantor C.R., Robbins R.J., eds.) / World Scientific. Singapore. 1993. P. 465-476.

148. Snyder E.E., Stormo G.D. Identification of coding regions in genomic DNA sequences: an application of dynamic programming and neural networks // Nucl. Acids Res. 1993. V. 21. P. 607-613.

149. Uberbacher E., Mural R. Locating protein coding regions in human DNA sequences by a multiple sensor - neural network approach // Proc. Nat. Acad. Sci. USA. 1991. V. 88. P. 11261-11265.

150. Спирин A.C. Молекулярная биология. Структура рибосомы и биосинтез белка // М.: Высшая школа, 1986.

151. Kozak М. Regulation of translation in eukaryotic sequences // Annu. Rev. Cell Biol. 1992. V. 8. P. 197-225.

152. Kozak M. Interpreting cDNA sequences: some insights from studies on translation // Mammalian Genome. 1996. V. 7. P. 563-574.

153. Hattier Т., Bell R, Shaffer D., Stone S., Phelps R.S., Tavtigian S.V., Skolnik M.H., Shattuck-Eidens D., Kamb A. Monitoring the efficacy of hybrid selection during positional cloning//Mammalian Genome. 1995. V. 6. P. 873-879.

154. Timmermans M.C.P., Das O.P., Messing J. Characterization of a meiotic crossover in maize identified by a restriction fragment length polymorphism-based method // Genetics. 1996. V. 143, P. 1771-1783.

155. Parimoo S., Patanjali S.R., Kolluri R, XuH., Wei H., Weissman S.M. cDNA selection and other approaches in positional cloning // Analytical Biochemistry. 1995. V. 228, P. 1-17.

156. Parrish J.E., Nelson D.L. Methods for finding genes: A major rate-limiting step in positional cloning // Gene Anal. Tech. Appl. 1993. V. 10,29-41.

157. Selleri L., Smith M.W., Holmsen A.L., Romo A.J., Thomas S.D., Paternotte C., Romberg L.C.R., Wei Y.H., Evans G.A. // High-resolution physical mapping of a 250-

kb region of human chromosome 1 lq24 by genomic sequence sampling (GSS) // Genomics. 1995. V. 26, P. 489-501.

158. Burset M., Guigo R. Evaluation of gene structure prediction programs // Genomics. 1996. V. 34. P. 353-367.

159. Gish W., States D.J. // Nsture Genet. 1993. V. 3. P. 266-272.

160. Snyder,E.E., Stormo G.D. Identification of protein coding regions in genomic DNA // J. Mol. Biol. 1995. V. 248. P. 1-18.

161. Rogozin I.B., Milanesi L., Kolchanov N.A. Gene structure prediction using information on homologous protein sequence // Comput. Appl. Biosci. 1996. V. 12. 161-170.

162. Hultner M., Smith D.W., Wills C. Similarity landscapes: A way to detect meny structural and sequence motifs in both introns and exons // J. Mol. Evol. 1994. V. 38. P. 188-203.

163. Almagor H. A Markov analysis of DNA sequences // J. Theor. Biol. 1983. V. 104. P. 633-645.

164. Blaisdell B.E. Markov chain analysis finds a significant influence of neighboring bases on the occurence of a base in eukaryotic nuclear DNA sequences both protein-coding and noncoding // J. Mol. Evol. 1985. V. 21. P. 278-288.

165. Phillips G.J., Arnold J., Ivarie R. Mono- through hexanucleotide composition of the Escherichia coli genome: a Markov chain analysis // Nucl. Acids Res. 1987. V. 15. P. 2611-2626.

166. Arnold J., Cuticchia A.J., Newsome D.A., Jennings III W.W., Ivarie R. Mono-through hexanucleotide composition of the sense strand of yeast DNA: a Markov chain analysis //Nucl. Acids Res. 1988. V. 16. P. 7145-7158.

167. Garden P.W. Markov analysis of viral DNA/RNA sequences // J. Theor. Biol. 1980. V. 82. P. 679-684.

168. Fuchs C. On the distribution of nucleotides in seven completely sequenced DNAs // Gene. 1980. V. 10. P. 371-373.

169. Piroird D.B. Chaines de Markov et sequences d'A.D.N. // Revue Bio-Mathematique. 1988. N. 101. P. 5-30.

170. Tavare S., Giddings B.W. Some statistical aspects of the primary structure of nucleotide sequences // Mathematical Methods for DNA Sequences (M.S. Waterman, ed.) / CRC Press. Boca Raton, Fla. 1989. P. 116-132.

171. Tavare S., Song B. Codon preference and primary sequence structure in protein-coding regions//Bull. Math. Biol. 1989. V. 51. P. 95-115.

172. Tavare S., Raftery A.E. Estimation of the mixture transition distribution model for high order Markov chains // Appl. Stat.

173. Trifonov E.N., Brendel V. Gnomic, a dictionary of genetic codes // Balaban Publishers. Rehovot, Philadelphia. 1986

174. Volinia S., Bernardi F., Gambari R., Barrai I. Co-localization of rare oligonucleotides and regulatory elements in mammalian upstream gene regions // J. Mol. Biol. 1988. V. 203. P. 385-390.

175. Bodnar J.W., Ward DC. Highly recurring sequence elements identified in eukaryotic DNAs by computer analysis are often homologous to regulatory sequences or protein binding sites//Nucl. Acids Res. 1987. V. 15. P. 1835-1851.

176. Claverie J.-M., Sauvaget I., Bougueleret L. k-tuple frequency analysis: from intron/exon discrimination to T-cell epitope mapping // Meth. Enzymol. 1990. V. 183. P. 252-281.

177. Volinia S., Gambari R., Bernardi F., Barrai I. The frequency of oligonucleotides in mammalian genie regions // Comput. Appl. Biosci. 1989. V. 5. P. 33-40.

178. Brendel V., Beckmann J.S., Trifonov E.N. Linguistics of nucleotide sequences: morphology and comparison of vocabularies // J. Biomol. Struct. Dynam. 1986. V. 4. P. 11-21.

179. Beckmann J.S., Brendel V., Trifonov E.N. Intervening sequences exhibit distinct vocabulary//J. Biomol. Struct. Dynam. 1986. V. 4. P. 391-400.

180. Trifonov E.N. Nucleotide sequences as a language: morphological classes of words // Classification and Related Methods of Data Analysis (Bock H.H.) / Elsevier Science Publishers. North-Holland. 1987. P. 57-64.

181. Pevzner P.A., Borodovsky M.Yu., Mironov A. A. Linguistics of nucleotide sequences I: The significance of deviations from mean statistical characteristics and prediction of the frequences of occurence of words // J. Biomol. Struct. Dynam. 1989. V. 6. P. 10131026.

182. Breen S., Waterman M., Zhang N. Renewal theory for several patterns // J. Appl. Prob. 1985. V. 22. P. 228-234.

183. Guibas L.J., Odlyzko A.M. String overlaps, pattern matching and nontransitive games //J. Combinat. Theory, ser. A. 1981. V. 30. P. 183-208.

184. Schbath S., Prüm В., de Turckheim E. // J. Comput. Biol. 1995. V. 3. P. 417-437.

185. Phillips G.J., Arnold J., ivarie R. The effect of codon usage on the oligonucleotide composition of the E. coli genome and identification of over- and underrepresented sequences by Markov chain analysis //Nucl. Acids Res. 1987. V. 15. P. 2627-2638.

186. Merkl R., Fritz H.J. //Nucleic Acids Res. 1996. V. 24. P. 4146-4151.

187. Grantham R. Nucleic acid sequence similarities: ,лро!у(А) tendency" // FEBS Lett. 1980. V. 121. P. 193-199.

188. Nussinov R. Strong adenine clustering in nucleotide sequences // J. Theor. Biol. 1980. V. 85. P. 285-291.

189. Sprizhitsky Yu.A., Nechipurenko Yu.A., Alexandrov A.A., Volkenstein M.V. // Statistical analysis of nucleotide runs in coding and noncoding DNA sequences // J. Biomol. Struct. Dynam. 1988. V. 6. P. 345-358.

190. Tripathi J., Brahmachari S.K. Distribution of simple repetitive (TG/CA)n and (CT/AG)n sequences in human and rabbit genomes // Biomol. Struct. Dynam. 1991. V. 9. P. 387-397.

191. Konopka A.K., Owens J. Non-continuous patterns and compositional complexity of nucleic acid sequences // Computers and DNA (Bell G.I., Marr T.G., ed.). SFI Studies in the Sciences of Complexity. V. VII / Addison-Wesley. 1990. P. 147-155.

192. Harris Z.G. From phoneme to morpheme // Language. 1955. V. 31. P. 190-222.

193. Сухотин Б.В. Выделение морфем в текстах без пробелов между словами // М. Наука. 1984.

194. Fichant G. A. Splice sites and local amino acid composition of the protein encoded by the gene // Genome Analysis Conf. / Santa Fe, NM, USA, 1991. P. P8.

195. Schneider T.D., Stormo G.D., Gold L., Ehrenfeucht A. information content of binding sites in nuceotide sequences //J. Mol. Biol. 1986. V. 188. P. 415-431.

196. Berg O.G., von Hippel P.H. Selection of DNA binding sites by regulatory proteins. Statistical-mechanical theory and application to operators and promoters // J. Mol. Biol. 1987. V. 193. P. 723-750.

197. Staden R. Computer methods to locate signals in nucleic acid sequences //Nucl. Acids Res. 1984. V. 12. P. 505-519.

198. Shapiro M.B., Senapathy P. RNA splice junctions of different classes of eukaryotes: sequence statistics and functional implications in gene expression //Nucl. Acids Res. 1987. V. 15. P. 7155-7174.

199. Stormo G.D. Identifying coding sequences //Nucleic acid and protein sequence analysis: a practical approach (Bishop M.J., Rawlings C.J., eds.). P. 359-385 (IRL Press, Oxford, 1987).

200. Shulrnan M.J., Steinberg C.M., Westmoreland N. // The coding function of nucleotide sequences can be discerned by statistical analysis // J. Theor. Biol. 1981 V. 88. P. 409420.

201. Trifonov E.N. Translation framing code and frame-monitoring mechanism as suggested by the analysis of mRNA and 16S rRNA nucleotide sequences // J. Mol. Biol. 1987. V. 194. P. 643-652.

202. Fichant G.A. Splice sites and local amino acid composition of the protein encoded by the gene // Genome Analysis (Abstr. Int. Conf., Santa Fe, USA, 1991). P. P8.

203. Craik C.S., Sprang S., Fletterick R., R utter W.J. Intron-exon splice junctions map at protein surfaces //Nature. 1982. V. 299. P. 180-182.

204. Bernardi G. The isochore organization of the human genome // Annu. Rev. Genet. 1989. V. 23. P. 637-661.

205. Nussinov R. // J. Biomo!. Struct. Dynatn. 1989. V. 6. P. 985.

206. Lukashin A. V., Engelbrecht J., Brunak S. // Nucleic Acids Res. 1992. V. 20. P. 2511.

207. Bernardi G. // Annu. Rev. Genet. 1985. V. 228. P. 953.

208. Zhang M.Q., Marr T.G. // Proc. Gene Finding and Gene Structure Prediction Workshop, Philadelphia, PA, USA, October 13-14, 1995.

209. Fields C.A. //Nucleic Acids Res. 1990. V. 18. P. 1509.

210. Mount S.M., Burks C„ Hertz G., Stormo G.D., White O., Fields C. //Nucleic Acids Res. 1992. V. 20. P. 4255.

211. Long M.. Rosenberg C„ Gilbert W. // Proc. Natl. Acad. Sei. USA. 1995. V. 92. P. 12495.

212. TomitaM., ShimizuN., BrutlagD.L. //Mol. Biol. Evol. 1996. V. 13. P. 1219.

213. Trifonov E.N. The multiple codes of nucleotide sequences //Bull. Math. Biol. 1989. V. 51. P. 417-432.

214. Trifonov E.N. Sequence ontogenesis and spatial separation of overlaping messages // Open Problems of Computational Molecular Biology (Abstr. Int. Workshop, Telluride, USA, 1991). P. 58-62.

215. Bürge C., Karlin S. // J. Mol. Biol. 1997. V. 268.

216. Solovyev V.V., Salamov A.S., Lawrence C.B. //Nucleic Acids Res. 1994. V. 22. P. 5156-5163.

217. Zuker M. The use of dynamic programming algorithms in RNA secondary structure rediction // Mathematical methods for DNA sequences (Waterman M., ed.) / CRC Press. Boca Raton. 1989. P. 159-184.

218. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов //М. Мир. 1982. 416 С.

219. Lengauer Т., Theunc D. Unstructured path problems and the making of semirings // Proceedings of the WADS'91. 1992.

220. Finkelstein A.V., RoytbergM.A. Computation of biopolymers: A general aproach to different problems // BioSystems. 1993. V. 30. P. 1-19.

221. Roytberg M.A. Fast algorithm for optimal aligning of symbol sequences // Mathematical methods of the analysis of biopolymer synthesis (Gindikin S.G., ed.) / D1MACS Series in Discrete Mathtematics and Computer Science. 1992. V. 8. P. 113126.

222. Авдошин C.M., Белов Б. Б., Mac лов В. П. Математические аспекты синтеза программного обеспечения // М. ВИНИТИ. 1984.

223. Hirshberg D.S. A linear space algorithm for computing maximum common subsequences//Commun. ACM. 1975. V 18. P. .341-343.

224. RoytbergM.A. Pareto-optimal alignments of symbol sequences // CSAM'93. (Proc. Int. Congr. on Computer Systems and Applied Mathematics, St.Petersburg, 1993). P. 161-162.

225. Ройтберг M.A. Еще один подход к задаче выравниваия последовательностей: больше сходств, меньше делеций - и никаких весовых коэффициентов //Геном человека - 93 (3-я конференция, Черноголовка, 1993). С. 135.

226. Alexandrov N.N, Mironov A. A. Application of a new method of pattern recognition // Nucl. Acids Res. 1990. V. 18. P. 1847-1852.

227. Korning P.G., Hebsgaard S.M., Rouze P., Brunak S. Cleaning the GenBank Arabidopsis thaliana data set // Nucleic Acids Res. 1996. V. 24, P. 316-320.

228. Nakamura Y., Wada K.-n., Wada Y., Doi H., Kanaya S., Gojobori Т., Ikemura T. Codon usage tabulated from the international DNA sequence databases //Nucleic Acids Res. 1996. V. 24. P. 214-215.

229. Sze S.-H., Pevzner P.A. Las Vegas algorithms for gene recognition: suboptimal and error-tolerant spliced alignment// J. Comput. Biol. 1997. V. 4. P. 297-310.

230. Myers E.W., Miller W. // Proc. 6th Annu. ACM-S1AM Symp. on Discrete Algorithms. San Francisco: ACM, 1995. P. 38-47.

231. Wilbur W., Lipman D. / Proc. Natl. Acad. Sci. USA. 1983. V. 80. P. 726-730.

232. Sankoff D. // Math. Biosci. V. 111. P. 279-293.

233. Knecht L. // Lect. Notes Comput. Sci. 1995. V. 937. P. 215-229.

234. Needleman S.B., Wunsch C.D. A general method applicable to search for similarities in the amino acid sequences of two proteins // J. Mol. Biol. 1970. V. 48. P. 444-453.

235. Миронов А.А. Поиск гомологии // Компьютерный анализ генетических текстов. Франк-Каменецкий М.Д., ред. /М.: Наука, 1990. С. 11-35.

236. DayhoffМ.О., Schwartz R.M., Orcutt B.C. // Atlas of PRotein Sequence and Structure. Dayhoff M.O., ed. / Washington, DC: Natl. Biomed. Res. Found., 1978. V. 5. Suppl. 3. P. 345-352.

237. Altschul S.F. Amino acid substitution matrices from an information theoretic perspective // J. Mol. Biol. 1991. V. 219. P. 555-565.

238. Benson D.A., Boguski M.S., Lipman D.J., Ostell, J. GenBank // Nucleic Acids Res. 1997. V. 25. P. 1-6.

239. Stoesser G., Sterk P., Tuli M.A., Stoehr P., Cameron G.N. // The EMBL nucleotide sequence database //Nucleic Acids Res. 1997. V. 25. P. 7-13.

240. Sharp P.A. Split genes and RNA splicing//Cell. 1994. V. 77. P. 805-815.

241. Breathnach R., Chambon P. Organization and expression of eukaryotic slpit genes coding for proteins // Annu. Rev. Biochem. 1981. V. 50. P. 349-383.

242. Jackson I.J. A reappraisal of non-consensus mRNA splice sites //Nucleic Acids Res. 1991. V. 19. P. 3795-3798.

243. Schuler G.D., Epstein J.A., Ohkawa H., Kans, J.A. Entrez: Molecular biology database and retrieval system//Meth. Enzymol. 1996. V. 266. P. 141-162.

244. Altschul S.F., Gish W., Miller W., Myers E.W., Lipman D.J. // J. Mol. Biol. 1990. V. 215. P. 403-410.

245. Pascarella S„ ArgosP. H J. Mol. Biol. 1992. V. 224. P. 461-471.

246. Waterman M.S. Introduction to Computational Biology // Chapman & Hall, 1995.

247. Sharp P.M. //Mol. Biol. Evol. 1986. V. 3. P. 75-83.

248. Karlin S., Bürge C., Campbell A.M. // Nucleic Acids Res. 1992. V. 20. P. 1363-1370.

249. Nolling J., de Vos W.M. // J. Bacteriol. 1992. V. 174. P. 5719-5726.

250. Sharp P.M., Kelleher J.E., Daniel A.S., Cowan G.M., Murray N.E. // Proc. Natl. Acad. Sci, 1992. V. 89. P. 9836-9840.

251. Barcus V.A., Titheradge A.J., Murray N.E. // Genetics. 1995. V. 140. P. 1187-1197.

252. Nito T., Kusano K., Kobayashi I. // Science. 1995. V. 267. P. 897-899.

253. Jeltsch A., Kroger M., Pingoud A. // Gene. 1995. V. 160. P. 7-16.

254. Konopka A.K., Smythers G.W., Owens J., Maizel Jr. J.V. Distance analysis helps to establish characteristic motifs in intron sequences // Gene Anal. Techn. 1987. V. 4. P. 63-74.

255. Nussinov R., Sarai A., Smythers G.W., Jernigan R.L. Sequence context of oligomer tracts in eukaryotic DNA: biological and conformational implications // J. Biomol. Struct. Dynam. 1988. V. 6. P. 543-562.

256. Nussinov R., Sarai A., Smythers G.W., Jernigan R.L. Distinct patterns in homooligomer tracts sequence context in prokaryotic and eukaryotic DNA // Biochim. Biophys. Acta 1989. V. 1008. C. 329-338.

257. Nussinov R., Sarai A., Smythers G.W., Wang D., Jernigan R.L. Strong patterns in homooligomer tracts occurences in non-coding and in potential regulatory sites in eukaryotic genomes // J. Biomol. Struct. Dynam. 1989. V. 7. P. 707-722.

258. Nussinov R. General nearest neighbor preferences in G/C oligomers interrupted by A/T: Correlation with DNA structure // J. Biomol. Struct. Dynam. 1990. V. 8. P. 399411.

259. Nussinov R. The ordering of nucleotides in the DNA: strong pyrimidine-purine patterns near homooligomer tracts // J. Theor. Biol. 1991. V. 149. P. 21-42.

260. Konopka A.K., Owens J. Complexity charts can be used to map functional domains in DNA // Gene Anal. Techn. Appl. 1990. V. 7. P. 35-38.

261. Aigner M. Combinatorial analysis // Springer-Verlag. New York. 1979.