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

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

Селиверстов Александр Владиславович

АЛГОРИТМ ПОИСКА КЛИКИ В ГРАФЕ, ПРЕДСКАЗАНИЕ РЕГУЛЯТОРНЫХ СТРУКТУР РНК И МОДЕЛИРОВАНИЕ РЕГУЛЯЦИИ БИОСИНТЕЗА ТРИПТОФАНА

05.13.17 - Теоретические основы информатики, 03.00.28 - Биоинформатика

АВТОРЕФЕРАТ

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

Москва-2006

Работа выполнена в Институте проблем передачи информации РАН

Научный руководитель: д.ф.-м.н. проф. В.А. Любецкий

Официальные оппоненты: д.б.н. проф. A.A. Миронов,

д.ф.-м.н. проф. М.Р. Пентус

Ведущая организация: Институт молекулярной биологии им.

В.А. Энгельгарта РАН

Защита диссертации состоится 20 Н£>А<Г|>-% 2006 года в ^ ^ на заседании Диссертационного совета Д.002.077.01 при Институте проблем передачи информации РАН по адресу: 127994, Москва Большой Каретный пер., 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан /0 2006 года.

Учёный секретарь диссертационного совета:

д.ф.-м.н. И.И. Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Ранее многими авторами, в том числе М.С. Гельфандом, отмечалась возможность сведения к поиску клики в многодольном графе задачи нахо-

ждения консервативных участков в наборе невыравненных лидерных областей перед гомологичными генами родственных видов или перед генами, кодирующими ферменты одного метаболического пути. Эти консервативные участки составляют упомянутые выше регуляторные структуры {сигналы) - статику регуляции экспрессии соответствующих генов. Однако практическое применение этого подхода затруднялось из-за отсутствия эффективных методов поиска клики. Другие методы поиска сигнала рассмотрены в работах A.A. Миронова, П.А. Певзнера, М.С. Уотермена и др.

Альтернативный путь изучения регуляторных структур по одной последовательности РНК, впервые рассмотренный A.A. Мироновым, состоит в моделировании кинетики вторичной структуры РНК. Однако, многие регуляторные системы, включая классическую аттенюаторную регуляцию экспрессии генов, не исследовались подобным образом. Более того, невозможность прямого измерения некоторых параметров ставит нетривиальную обратную задачу: выбор параметров модели, соответствующих наблюдаемым зависимостям. И после уточнения модели — решение вопроса о наличии регуляции в одной лидерной области, без множественного выравнивания и поиска сигналов, что представляет собой весьма трудную задачу.

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

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

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

Положения, выносимые на защиту.

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

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

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

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

Потенциальные структуры классической аттенюаторной регуляции предсказаны для: оперонов, кодирующих ферменты биосинтеза триптофана, у СогупеЬаЫегшт и 81герЮтусез\ гена 1грБ, кодирующего триптофанил-

тРНК синтетазу, у Streptomyces avermitilis; генов leiiS, кодирующих лейцил-тРНК синтетазу, у Streptomyces; оперонов ilv у многих актинобактерий. Предсказаны у многих актинобактерий: новый потенциальный тип регуляции трансляции гена leuA, кодирующего 2-изопропилмалат синтазу, Т-боксовая регуляция трансляции гена ileS, кодирующего изолейцил-тРНК синтетазу, потенциальная Rho-зависимая аттенюаторная регуляция биосинтеза цистеина.

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

Практическая значимость работы. Работа носит теоретический характер. В то же время, данное исследование представляет интерес, поскольку сравнительный анализ геномов позволяет лучше понять механизмы возникновения устойчивости бактерий к антибиотикам и найти пути создания более эффективных промышленных штаммов. Компьютерный анализ проведён в части регуляции экспрессии перечисленных выше генов. К актино-бактериям принадлежат индустриальные продуценты аминокислот (Corynebacterium glutamicum, Corynebacterium efficiens) и антибиотиков (Streptomyces spp.), симбионты человека (Bifidobacterium longum, Propionibacterium acnes), возбудители опасных инфекционных болезней ('Corynebacterium diphtheriae, Mycobacterium spp.). В то же время актино-бактерии составляют отдельную филогенетическую группу, и они исследованы гораздо меньше, чем кишечная палочка (представитель протеобакте-рий) или сенная палочка (представитель фирмикутов).

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

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

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

Аппробация работы. Результаты диссертации неоднократно излагались на семинаре Учебно-Научного центра «Биоинформатика» Института проблем передачи информации РАН, на семинаре «Алгоритмы в геномике» кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. Ломоносова, на Научном семинаре по биоинформатике Института проблем передачи информации РАН и на следующих четырёх конференциях: шестая международная конференция РАН «Проблемы управления и моделирования в сложных системах» (14-17 июня 2004, Самара); четвёртая международная конференция по биоинформатике, геномной регуляции и структуре генома (25-30 июля 2004, Новосибирск); седьмая международная конференция РАН «Проблемы управления и моделирования в сложных системах» (27 июня - 1 июля 2005, Самара); вторая международная московская конференция по вычислительной молекулярной биологии (18-21 июля 2005, Москва).

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

Структура и объём работы. Работа состоит из введения, трёх глав, заключения и списка литературы. Список литературы содержит 60 наименований. Объём работы составляет 102 страницы, включая 24 таблицы и 8 рисунков.

СОДЕРЖАНИЕ РАБОТЫ Во введении, раздел 0.1, даны основные определения и обзор алгоритмических результатов. Приведены теоремы Фаркаша, Хачияна и теорема Шефера о ЗКНФ. Далее обсуждаются различные алгоритмы поиска сигнала, т.е. набора наиболее попарно похожих слов, и поиска множественного выравнивания последовательностей. Указана связь задач о поиске сигнала и о поиске клики в многодольном графе. В разделе 0.2 дан обзор результатов по регуляции экспрессии генов у хпоропластов и бактерий. Отмечены примеры белок-РНКового взамодействия у хлоропластов. Кратко описаны ме-

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

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

Ниже индексы р, г равны 1 или 2, а индексы /,у, к пробегают значения от 1 до л. Для любого целого числа л определим многогранник квазиклик, обозначаемый Р„, в 4л -мерном пространстве, как выделяемый следующей системой равенств и неравенств: для всех /,у, р, <7 пусть Х^чр, для всех I пусть Хц\\+Хц2г—\ ■> для всех / пусть ^-,12=0, для всех 1,7, р пусть Хур\+Хур2-Хцт для всех /,/, р> 9 пусть Хут неотрицательно и меньше или равно единице, для всех 1,7, к,р, ц, г пусть сумма Хирр+Х^чг больше или равна сумме Хурд+Х^г.

Лемма 1. Для любого отображения /множества {1,2, ..., л} во множество {1, 2} точка X с координатами Ху(>ч=\, если р=Л0 и Я=Л/)- и Хирч=0, если такое условие не выполнено, является вершиной многогранника квазиклик. Эти точки взаимно однозначно соответствуют всем п-кликам полного п-дольного графа с двумя вершинами в каждой доле.

По л-дольному графу <7, имеющему по две вершины в каждой доле, определим аффинное подпространство //(в), выделяемое всеми уравнения-

ми вида Хурд=0, если индекс / не равен индексу у и р-я вершина /-й доли не соединена ребром с д-й вершинойу'-й доли.

Теорема 1. Пусть п-дольный граф й имеет по две вершины в каждой доле. Если пересечение многогранника квазиклик и пространства Н(С) непустое, то граф в имеет хотя бы одну п-клику. Если размерность пересечения многогранника квазиклик и пространства Н((3) равна единице, то граф в имеет одну или две п-клики.

Теорема 2. Размерность многогранника квазиклик равна п(п+1 )/2.

Обозначим выпуклую оболочку точек (из многогранника квазиклик), соответствующих всем и-кликам полного л-дольного графа (7, Этот многогранник назовём многогранником клик.

Теорема 3. Выпуклая оболочка любых двух вершин многогранника клик является его ребром.

Теорема 4. Если существует недетерминированный алгоритм для распознавания сторон многогранника Qn клик за время, ограниченное полиномом от п, то выполняется равенство: соЫР = ИР.

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

Пусть А и В — некоторые кольца, а Я — конечный Л-5-6 и модуль из г элементов. Рассматривается произвольная система однородных линейных уравнений вида Уа^^,. = 0 над бимодулем Я. Множество решений системы из т таких уравнений, каждое от п переменных, образует подгруппу в пространстве Я которую обозначим Вт.

Теорема 5. Существует и ниже описан алгоритм, который для произвольной однородной линейной системы уравнений над Я образует систему порождающих в группе Вт всех её решений и указывает число всех решений, выполняя для этого Опт + п)1 -т-Ь-г4] операций в Я. Здесь т — чис-

ло уравнений, п - число переменных, Ь — число операций, необходимых для проверки выполнимости любого уравнения системы при любых значениях переменных, г - число элементов в Я.

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

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

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

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

В текущем графе С сначала исключаются вершины (и все инцидентные им рёбра), которые соединены хотя бы одним ребром с долями таким образом, что суммарное число этих долей строго меньше Затем исключаются рёбра, которые принадлежат строго меньшему, чем <?-2 числу 3-клик, или строго меньшему, чем (^-2)(^-3)/2 числу 4-клик. Такое исключение последовательно повторяется сначала для всех вершин и затем для всех рёбер текущего графа С до тех пор, пока это возможно.

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

Если вершина Я степени ровно д-1 не найдена, то одно ребро текущего графа, входящее в наименьшее число треугольников в нём, удаляется.

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

Каждая клика из списка <7-клик определяет свой сигнал, состоящий из слов, которые приписаны вершинам клики.

В разделе 1.4 приведены результаты тестирования алгоритма для поиска сигнала на примере известных сайтов связывания белка РигЛ с ДНК у кишечной палочки. Алгоритм нашёл три сигнала, содержащих 21 сайт в де-

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

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

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

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

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

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

Обозначения: "+" - сайт связывания белка с РНК найден, "-" — сайт не найден, "в" - соответствующий ген содержит интроны, "п" — соответствующий ген отсутствует у вида, указанного в строке.

Отдел Вид atpF clpP petB psaA psbA psbB

Euglenozoa Euglena gracilis -s -s -s -s -s

Bacillariophyta Odontella sinensis - - + + -

Cryptophyta Guillardia theta - - + + -

Rhodophyta Cyanidioschyzon merolae - - - - + -

Cyanidium caldarium

Porphyra purpurea - - - + + +

Gracilaria tenuistipitata - - - - + -

Chlorophyta Chlamydomonas reinhardtii - - - -s +s -

Nephroselmis olivacea - - - + + +

Streptophyta Chaetosphaeridium globosum - +s -s + + +

Mesostigma viride - - - + - -

Anthocerophyte Anthoceros formosae +s +s +s + + +

Hepatophyta Marchantía polymorpha +s +s +s + + +

Lycopodiophyti Huperzia lucidula +s +s +s + + +

Pteridophyta Adiantum capillus-venerii +s +s -s + + +

Psilophyta Psilotum nudum +s +s +s + + +

Pinophyta Pinus thunbergii +s + +s + +s +

Magnoliophyta (двудольные) Amborella trichopoda +s +s +s + - +

Arabidopsis thaliana +s +s +s + + +

Atropa belladonna +s +s +s + + +

Calycanthus floridus +s +s +s + + +

Cucumis sativus +s +s +s + + +

Epifagus virginiana n +s n n n n

Lotus corniculatus +s +s +s + + +

Nicotiana tabacum +s +s +s + + +

Nymphaea alba +s +s +s + + +

Panax ginseng +s +s +s + + +

Spinacia oleracea +s +s +s + + +

Magnoliophyta (однодольные' Oryza nivara, Oryza sativa +s +s +s + + +

Triticum aestivum +s +s +s + + +

Zea mays +S +s +s + + +

В разделе 2.2 рассмотрены системы регуляции экспрессии генов, кодирующих ферменты для биосинтеза аминокислот и аминоацил-тРНК син-

тетазы у актинобактерий. Применение того же алгоритма для поиска консервативных участков в 5'-нетранслируемых областях генов привело к выделению протяжённых участков с консервативной вторичной альтернативной структурой РНК. Кратко эти результаты приведены в табл. 2.

Таблица 2. Распределение предсказанных регуляторных структур РНК у актинобактерий.

Обозначения. "А" указывает на присутствие классической аттенюаторной регуляции, "R" - Rho-зависимой аттенюаторной регуляции, "LEU" - нового типа регуляции при участии LEU-элемента на уровне трансляции, "Т" - Т-боксовую регуляции на уровне трансляции.

Род триптофан цистеин лейцин изолейцин

trp cys cbs leuA leuS ileS

Actinomyces LEU T

Bifidobacterium R T

Corynebacterium А LEU T

Kineococcus LEU T

Leifsonia LEU

Mycobacterium R LEU T

Nocardia LEU T

Propion ibacterium R T

Rubrobacter T

Streptomvces А LEU А T

Thermobifida LEU

Биосннтез триптофана. Найдена классическая аттенюаторная регуляция оперонов биосинтеза триптофана у всех СогупеЬас1егшт Брр. и у Б1герютусе$ Брр. У С. (НрИМепае эта регуляция предсказана для двух оперонов 1грВ\ЕйОС и 1грВ2А. У 5. а\>еппШИ8 она предсказана для триптофа-нил-тРНК синтетазы 1грБ2.

Лидерные пептиды перед 1гр оперонами имеют двойной или тройной повтор регуляторного кодона 1ЮО. Все терминаторы содержат консервативную ОС-богатую шпильку, за которой следует участок остатков ураци-ла. Шпильки антитерминатора и терминатора во всех случаях содержат комплементарную тройку §ССС-К3 Су-СвСС, в которой абсолютно консервативные нуклеотиды показаны прописными буквами. Найденные здесь

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

Биосинтез цистеина. 5'-области оперонов cys у всех Mycobacterium spp., кроме М. smegmatis, у Р. acnes, и также оперона cbs у В. longum содержат открытую рамку считывания с последовательностью цистеиновых ко-донов непосредственно перед стоп кодоном. Возможно, регуляция транскрипции основана здесь на Rho-зависимой терминации. Эта ситуация аналогична той, которая известна для триптофаназы tna у Е. coli. 3'-нетранслируемая область предполагаемого лидерного пептида содержит UC-богатый мотив, характерный для связывания белка Rho с РНК. Итак, предполагаемая схема регуляции такова: при недостатке цистеина участок мРНК вокруг стоп кодоном лидерного пептида закрыт рибосомой столь долго, что РНК полимераза успевает уйти далеко и транскрипция не прерывается. При избытке цистеина рибосома быстро завершает трансляцию лидерного пептида, и в результате открывается следующий за ним UC-богатый участок РНК, характерный для Rho-зависимого терминатора. Транскрипция прерывается.

Биосинтез лейцина. Перед генами 1еиА 2-изопропилмалат синтазы у большинства актинобактерий (A. naeslundii, Corynebacterium spp., К. radiotolerans, L. xyli, Mycobacterium spp., N.farcinica, Streptomyces spp., T.fusca) в 5'-нетранслируемой области присутствует характерная консервативная структура, названная LEU-элементом. А именно, LEU-элемент имеет две конформации, включающие короткую открытую рамку считывания с участком лейциновых кодонов. Первая из них включает вторичную структуру РНК с псевдоузлом, плечи спиралей которой высоко консервативны по нуклеотидному составу. Пвсевдоузел лежит в петле спирали (называемой черенком), 5'-плечо которой перекрывает область лейциновых кодонов лидерного пептида, а З'-плечо перекрывает область Шайна-Дальгарно гена leuA. Вторая конформация альтернативна, не имеет псевдоузла и не перекрывает устойчиво область Шайна-Дальгарно этого гена.

Высокая консервативность участков, которые перекрывают область Шайна-Дальгарно, позволила уточнить положение инициирующего кодона гена leuA у С. efficiens и Т. fusca. Это уточнение хорошо согласуется с множественным выравниванием соответствующих белков.

Предполагается следующий механизм аттенюации, связанной с LEU-элементом. В первой конформации, случай псевдоузла, черенок стабилен, а во второй конформации черенок нестабилен и область Шайна-Дальгарно не перекрывается. LEU-элемент обнаружен также внутри открытой рамки считывания гипотетической транспосазы из В. longum. LEU-элемент содержит сравнительно мало консервативных нуклеотидов, хотя стабильность такой структуры должна избирательно зависеть от концентрации лейцина и не зависеть от концентраций изолейцина и валина. Возможно, в регуляции принимает участие белок, который, образуя комплекс с лейцином, формирует псевдоузел LEU-элемента. Филогенетический профиль, близкий к филогенетическому профилю LEU-элемента, имеют гомологи гипотетического белка ML1624 (596 остатков аминокислот) из М. leprae. Гомологи этого белка с качеством выравнивания меньшим, чем £=1СГ170, найдены у всех актинобактерий, которые имеют LEU-элемент перед геном leu А. У этого белка с помощью базы PFAM найден N-концевой домен (аминокислоты с 34 по 193), обычный для DEAD/DEAH бокса хеликаз. Этот домен характерен для многих белков, вовлечённых в метаболизм РНК, включая транскрипцию, трансляцию, распад РНК и образование рибосомальных РНК. Можно предположить, что этот белок участвует в образовании псевдоузла в LEU-элементе оперона leu А, и в результате перекрытие области Шайна-Дальгарно регулируется концентрацией лейцина.

Биосинтез разветвлённых аминокислот. 5'-нетранслируемые области генов ilvB, кодирующих большую субъединицу ацетолактат синтазы (часто в составе оперонов ilvBNC или ilvBHC, где ilvN и ilvH кодируют малую субъединицу ацетолактат синтазы, ilvC кодирует кетол-ацид редуктои-зомеразу), у видов из родов Corynebactecterium, Mycobacterium, Streptomyces содержат открытую рамку считывания с повтором кодонов

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

Биосинтез аминоацил-тРНК синтетаз. Для генов ileS изолейцил-тРНК синтетаз большинства актинобактерий (А. naeslundii, В. longum, Corynebacterium spp., К. radiotolerans, Mycobacterium spp., N. farcinica, P. acnes, R. xylanophüus, Streptomyces spp.) предсказана Т-боксовая регуляция трансляции. В отличие от обычной Т-боксовой регуляции на уровне транскрипции здесь отсутствует терминатор. Незагруженная тРНК стабилизирует структуру РНК, при которой область Шайна-Дальгарно открыта для инициации трансляции. В ином случае, сайт связывания рибосомы перекрывается длинной спиралью альтернативной структуры, предотвращая трансляцию гена ileS. Высокая консервативность участков, которые перекрывают область Шайна-Дальгарно, позволила уточнить положение инициирующего кодона гена ileS у С. ejjficiens. Это уточнение хорошо согласуется с множественным выравниванием соответствующих белков.

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

В разделе 2.3 описана потенциальная регуляция трансляции гена укоЕ ABC транспортёра посредством тиаминового рибопереключателя у актинобактерий. У актинобактерий Brevibacterium linens, Kineococcus radiotolerans., Leifsonia xyli, Propionibacterium acnes, Thermobifida fusca, Corynebacterium diphtheriae, Corynebacterium glutamicum найдена консервативная вторичная структура РНК, характерная для тиаминового рибопереключателя. Вероятно, найденная консервативная структура связана с регуляцией трансляции. При этом у В. linens, К. radiotolerans, L. xyli, Р. acnes и Т. fusca область связывания рибосомы перекрывается короткой дополни-

тельной спиралью, а у С. diphtheriae и С. glutamicum рибопереключатель примыкает непосредственно к области связывания рибосомы.

В разделе 2.4 рассмотрена потенциальная Т-боксовая регуляция трансляции гена alr3806 у цианобактерии Nostoc РСС7120. Предлагаемая структура имеет слово с правильным консенсусом (собственно Т-бокс) и шпильки, характерные для Т-бокса. Важно, что тРНК стабилизирует такую структуру РНК, которая не препятствует трансляции гена alr3806. В противном случае возникает спираль, перекрывающая область связывания рибосомы перед геном alr3806, препятствуя трансляции.

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

В разделе 3.2 описана проверка модели методом Монте-Карло. Цель моделирования состояла в численном определении зависимости р(с) вероятности терминации от концентрации с аминоацил-тРНК (или от концентрации с аминокислоты в клетке). Для построения зависимости р{с) при каждом значении с из сетки с некоторым шагом узлов процесс, указанный в модели, проигрывался определенное число раз (обычно 103-104 раз, что дает примерно одинаковый результат) и вычислялось р{с) как доля случаев, в которых происходила терминация.

В разделе 3.3 приведены результаты тестирования модели. В табл. 3 даны результаты вычисления вероятности терминации транскрипции в процессе атенюаторной регуляции оперонов, включающих ген антранилат синтазы, у актинобактерий Corynebacterium diphtheriae и Corynebacterium glutamicum, у альфа-протеобактерий Agrobacterium tumefaciens, Bradyrhizobium japonicum, Rhodopseudomonas palustris, Rhizobium

• leguminosarum, Sinorhizobium meliloti и у гамма-протеобактерий Escherichia coli и Vibrio cholerae. И также для гена trpS, кодирующего триптофанил-тРНК синтетазу, у Streptomyces avermitilis. Параметры модели подбирались так, чтобы у Е. coli и С. glutamicum, для которых аттенюаторные регуляции экспериментально подтверждены, при малой концентрации наблюдался рост частоты терминации с увеличением концентрации триптофанил-тРНК, а при больших концентрациях - насыщение и выход на константу.

Таблица 3. Вероятность терминации /?(с) в зависимости от концентрации с триптофанил-тРНК для различных видов бактерий.

Вид Концентрация с

0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50

С. diphtheriae 0.34 0.34 0.39 0.46 0.50 0.54 0.53 0.53 0.53 0.52 0.54

С. glutamicum 0.05 0.06 0.08 0.10 0.10 0.09 0.09 0.09 0.10 0.10 0.10

S. avermitilis, trpS 0.06 0.13 0.21 0.26 0.28 0.29 0.30 0.30 0.32 0.32 0.30

4. tumefaciens 0.49 0.50 0.62 0.70 0.74 0.78 0.77 0.78 0.82 0.80 0.79

В. japonicum 0.19 0.20 0.24 0.26 0.28 0.26 0.26 0.27 0.26 0.26 0.26

R. leguminosarum 0.23 0.30 0.42 0.55 0.60 0.65 0.67 0.70 0.71 0.71 0.71

R. palustris 0.01 0.22 0.40 0.48 0.56 0.59 0.60 0.60 0.63 0.61 0.62

S. meliloti 0.07 0.11 0.23 0.37 0.43 0.49 0.48 0.51 0.50 0.53 0.51

E. coli 0.34 0.46 0.54 0.68 0.70 0.70 0.71 0.73 0.75 0.75 0.74

V. cholerae 0.05 0.16 0.39 0.57 0.70 0.74 0.77 0.77 0.80 0.79 0.81

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

С помощью этих алгоритмов получены следующие новые потенциальные регуляторные структуры РНК. Найдены консервативные структуры РНК, которые обеспечивают потенциальную регуляцию трансляции шести генов у хлоропластов посредством взаимодействия белков с РНК. Предложена гипотеза о том, что зависимая от света регуляция трансляции гена psbA сформировалась на ранних стадиях эволюции, а именно: до появления интронов в генах белков и до расхождения зелёных и пурпурных водорослей. Найдена классическая аттенюаторная регуляция перед генами биосинтеза триптофана, триптофанил- и лейцил-тРНК синтетазами некоторых ак-тинобактерий. Перед геном leuA у многих актинобактерий найден регуля-торный элемент нового типа, названный LEU-элементом. Найдены консервативные структуры РНК, включающие Т-бокс, которые обеспечивают потенциальную регуляцию трансляции гена ileS у многих актинобактерий и гена alr3806 у Nostoc. Найдены ген лидерного пептида и консервативный участок РНК, которые обеспечивают потенциальную Rho-зависимую атте-нюаторную регуляцию на уровне транскрипции генов биосинтеза цистеина, и определена структура оперонов, содержащих эти гены у актинобактерий. Найдены новые тиаминовые рибопереключатели, вовлечённые в регуляцию трансляции некоторых атинобактерий.

Предложена математическая модель классической аттенюаторной регуляции экспрессии генов, кодирующих ферменты биосинтеза триптофана. Модельный счёт на регуляторных областях перед триптофановыми опе-ронами у Е. coli, С. diphtheriae, V. cholerae и у нескольких альфа-протеобактерий приводит к результатам, качественно согласными с экспериментальными данными.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Любецкий В.А., Селиверстов А.В. Регуляция экспрессии генов биосинтеза аминокислот и аминоацил-тРНК синтетаз у Актинобактерий // Молекулярная биология. Т. 39, № 6, 2005. С. 1072-1075.

2. Любецкий В.А., Рубанов Л.И., Селиверстов А.В., Пирогов С.А. Модель регуляции экспрессии генов у бактерий на основе формирования вторичных структур РНК // Там же. Т. 40, № 3, 2006. С. 497-511.

3. Любецкий В.А., Селиверстов А.В. Геометрический метод поиска клики в графе и его применение для выделения сигнала // Труды VI международной конференции Проблемы управления и моделирования в сложных системах, 14-17 июня 2004. Самара: изд. Самарского научного центра РАН, 2004. С.154-157.

4. Любецкий В.А., Селиверстов А.В. Регуляция трансляции у актинобактерий и цианобактерий с участием вторичных структур мРНК // Труды VII Международной конференции РАН Проблемы управления и моделирования в сложных системах, 27 июня - 1 июля 2005. Самара: изд. Самарского научного центра РАН, 2005. С. 216-221.

5. Lyubetsky V.A., Seliverstov A.V. Amino acid biosynthesis attenuation in bacteria // Proceedings of the fourth international conference on bioinformatics of genome regulation and structure, July 25-30, 2004. Новосибирск: ред.-изд. отдел ИЦиГ СО РАН, 2004. Т. 1. С. 307-310. (http://www.bionet.nsc.ru/meeting/bgrs2004)

6. Lyubetsky V.A., Seliverstov A.V. Modeling classic attenuation regulation of gene expression in bacteria // Proceedings of the fifth international conference on bioinformatics of genome regulation and structure, July 16-22, 2006. Новосибирск: ред.-изд. отдел ИЦиГ СО РАН, 2006. Т. 1. С. 102-105.

7. Seliverstov A.V., Lyubetsky V.A. Translation regulation in chloroplasts // Там же. Т. 1. С. 146-149. (http://www.bionet.nsc.ru/meeting/bgrs2006)

8. Seliverstov A.V., Lyubetsky V.A. RNA regulatory structures in Actinobacte-ria and Cyanobacteria // Proceedings of the International Moscow Conference on Computational Molecular Biology. July 18-21, 2005. M., 2005. C. 351-353.

9. Seliverstov A.V., Putzer H., Gelfand M.S., Lyubetsky V.A. Comparative analysis of RNA regulatory elements of amino acid metabolism genes in Actinobacteria // BMC Microbiology. V. 5, N 54, 2005. 14 p. (http://www.biomedcentral.eom/1471-2180/5/54).

Ю.Любецкий B.A., Селиверстов A.B. Некоторые алгоритмы, связанные с конечными группами // Информационные процессы. Т. 3, № 1, 2003. С. 3946. (http://www.jip.ru/Contents.htm).

11.Любецкий В.А., Селиверстов A.B. Многодольные графы с двумя вершинами в каждой доле // Там же. Т. 4, № 2, 2004. С. 127-132.

12. Lyubetsky V.A., Seliverstov A.V. Note on Cliques and Alignments // Там же. Т. 4, № 3, 2004. С. 241-246.

13. Селиверстов A.B., Любецкий В.А. Особенности синтеза цистеина у Corynebacterium, Mycobacterium и Propionibacterium И Там же. Т. 4, № 3, 2004. С. 247-250.

14. Селиверстов A.B., Любецкий В.А. Поиск консервативных участков в лидерных областях генов в случае известного дерева видов // Там же. Т. 5, № 4, 2005. С. 265-27Ó.

15. Любецкий В.А., Горбунов К.Ю., Пирогов С.А., Рубанов Л.И., Селиверстов A.B. Алгоритм и результаты счета для модели регуляции экспрессии генов у бактерий на основе формирования вторичных структур РНК // Там же. Т. 5, № 5, 2005. С. 337-366.

16. Селиверстов A.B., Любецкий В.А. Регуляция трансляции в хлоропластах // Там же. Т. 5, № 5, 2005. С. 400-404.

17. Селиверстов A.B., Любецкий В.А. Алгоритм поиска консервативных участков нуклеотидных последовательностей // Там же. Т. 6, № 1, 2006. С. 33-36.

18. Любецкий В.А., Селиверстов A.B. Вычисление эффективности регуляции биосинтеза триптофана у бактерий на основе модели классической ат-тенюации // Там же. Т. 6, № 1,2006. С. 55-57.

¿ц/1

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Цели работы

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

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

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

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

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

Публикации

Структура и объем работы

ВВЕДЕНИЕ

0.1 Обзор алгоритмических результатов, относящихся к 10 диссертационному исследованию

0.2 Обзор результатов по регуляции экспрессии генов у хлоропластов 17 и бактерий

0 3 Обзор результатов по моделированию кинетики образования 20 вторичной структуры РНК

ГЛАВА 1. Алгоритм поиска клики в многодольном графе

1.1. Алгоритм поиска клики в случае двух вершин в каждой доле и 22 доказательство корректности его работы за полиномиальное время

1 2 Алгоритм решения неявно заданной системы однородных 31 линейных уравнений над конечным бимодулем и нижняя оценка числа клик

1 3. Алгоритм поиска клики в многодольном графе в общем случае и 37 поиск консервативных участков в невыравненном наборе последовательностей на основе этого алгоритма, учет дерева видов

1 4. Тестирование алгоритма

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

ГЛАВА 2. Предсказание структур РНК, регулирующих экспрессию генов, у хлоропластов и бактерий на основе алгоритма поиска клики

2 1. Регуляция трансляции посредством взаимодействия белков с 47 РНК для различных генов у хлоропластов

2.2. Различные системы регуляции экспрессии генов биосинтеза 59 аминокислот и аминоацил-тРНК синтетаз у актинобактерий

2 3 Регуляция трансляции гена укоЕ ABC транспортера посредством 77 тиаминового рибопереключателя у актинобактерий 2.4. Регуляция трансляции гена alr3806 с участием Т-бокса у цианобактерии Nostoc РСС

ГЛАВА 3. Моделирование классической аттенюаторной регуляции биосинтеза триптофана у бактерий

3.1. Математическая модель классической аттенюаторной регуляции 81 3.2 Проверка модели методом Монте-Карло

3.3. Тестирование модели и обсуждение результатов 90 ОСНОВНЫЕ РЕЗУЛЬТАТЫ 94 СПИСОК ЛИТЕРАТУРЫ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

С помощью этого эвристического алгоритма найдены новые потенциальные сайты связывания белков с мРНК у хлоропластов в 5'-нетранслируемых областях генов atpF, clpP, petB и генов psaA, psbA, psbB, кодирующих белки фотосистем. Предложена гипотеза, объясняющая задержку начала трансляции до завершения сплайсинга у ряда этих генов за счет специального белок-РНКового связывания.

Потенциальные структуры классической аттенюаторной регуляции предсказаны для: оперонов, кодирующих ферменты биосинтеза триптофана, у Corynebacterium и Streptomyces; гена trpS, кодирующего триптофанил-тРНК синтетазу, у Streptomyces avermitilis, генов leuS, кодирующих лейцил-тРНК синтетазу, у Streptomyces; оперонов ilv у многих актинобактерий Предсказаны у многих актинобактерий- новый потенциальный тип регуляции трансляции гена leuA, кодирующего 2-изопропилмалат синтазу, Т-боксовая регуляция трансляции гена ileS, кодирующего изолейцил-тРНК синтетазу, потенциальная Rho-зависимая аттенюаторная регуляция биосинтеза цистеина.

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

Практическая значимость работы. Работа носит теоретический характер. В то же время, данное исследование представляет интерес, поскольку сравнительный анализ геномов позволяет лучше понять механизмы возникновения устойчивости бактерий к антибиотикам и найти пути создания более эффективных промышленных штаммов Компьютерный анализ проведен в части регуляции экспрессии перечисленных выше генов. К актинобактериям принадлежат индустриальные продуценты аминокислот (Corynebacterium glutamicum, Corynebacterium efficiens) и антибиотиков (Streptomyces spp.), симбионты человека (Bifidobacterium longum, Propionibactemm acnes), возбудители опасных инфекционных болезней (Corynebacterium diphtheriae,

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

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

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

Аппробация работы Результаты диссертации неоднократно излагались на семинаре Учебно-Научного центра «Биоинформатика» Института проблем передачи информации РАН, на семинаре «Алгоритмы в геномике» кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. Ломоносова, на Научном семинаре по биоинформатике Института проблем передачи информации РАН и на следующих четырех конференциях: шестая международная конференция РАН «Проблемы управления и моделирования в сложных системах» (14-17 июня 2004, Самара); четвертая международная конференция по биоинформатике, геномной регуляции и структуре генома (25-30 июля 2004, Новосибирск), седьмая международная конференция РАН «Проблемы управления и моделирования в сложных системах» (27 июня - 1 июля 2005, Самара); вторая международная московская конференция по вычислительной молекулярной биологии (18-21 июля 2005, Москва)

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

Структура и объём работы. Работа состоит из введения, трех глав, заключения и списка литературы. Список литературы содержит 60 наименований. Объем работы составляет 102 страницы, включая 24 таблицы и 8 рисунков.

ВВЕДЕНИЕ

0.1 Обзор алгоритмических результатов, относящихся к диссертационному исследованию

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

Рис 1. Полный 3-дольный граф

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

Теорема Фаркаша. Если система линейных неравенств от d переменных неразрешима, то в ней имеется неразрешимая подсистема из не более чем d 11 неравенства.

Длина двоичной записи положительного целого числа п обозначается Size(«) и равна округлению до большего целого числа величины log2(n > 1). Длина двоичной записи рационального числа, равного несократимой дроби п/т, определяется как Size(w/w)=l+Size(|w|)+Size([w|). Длина двоичной записи рациональной матрицы размера п*т определяется как Size(M)=ww + ISi ze(Af„).

Теорема Хачияна. Существует алгоритм Оля проверки совместности системы рациональных линейных неравенств за полиномиальное от размера записи время Более того, этот алгоритм выдает решение системы, если оно существует.

Литерал - это пропозициональная переменная или ее отрицание. 2-КНФ есть конъюнкция дизъюнкций пар литералов, 3-КНФ - конъюнкция дизъюнкций троек литералов КНФ позитивная, если каждый ее литерал является пропозициональной переменной Моделью для КНФ называется такая оценка пропозициональных переменных со значениями истина или ложь, при которой КНФ истинна.

Напомним, что класс NP состоит из множеств, распознаваемых недетерминированными алгоритмами за время, ограниченное полиномом от длины входа Эквивалентно, множество А принадлежит классу NP, если существует такое множество пар В, разрешимое за полиномиальное время, что х принадлежит множеству А тогда и только тогда, когда некоторая пара (дг, у), в которой длина записи у ограничена полиномом от длины записи х, принадлежит множеству В.

Множество А называется NP-трудным, если для любого множества В из класса NP существует такая функция f, вычислимая за полиномиальное время, что х принадлежит В тогда и только тогда, когда j{x) принадлежит множеству А. Множество А называется NP-полным, если оно принадлежит классу NP и является NP-трудным. Известными NP-полными множествами являются множество выполнимых 3-КНФ и множество «-дольных графов, имеющих «-клику, [Сэвидж, 1998]

Теорема Шефера. Множество позитивных 3-КНФ, имеющих такую модель, в которой каждая дизъюнкция содержит ровно один истинныи читерал, является NP-полным

Доказательство. [Schaefer, 1978] Пусть пропозициональная формула (р{Л,ц,у) истинна тогда и только тогда, когда ровно одна из переменных Л, /л или v истинна, а две другие ложны.

Формула Лм//vv равновыполнима формуле

Формула /л^-tv равновыполнима формуле <р{/л,.

Для любой 3-КНФ легко построить равновыполнимую коньюнкцию формул вида (р{Л,/л,у), где Л, ц и v - пропозициональные переменные.

Заменяя в ней подформулы вида ср{Л,/j,v) на дизъюнкции Лу juvv, получим позитивную 3-КНФ, которая имеет модель, в которой каждая дизъюнкция содержит ровно один истинный литерал, тогда и только тогда, когда исходная 3-КНФ выполнима. Так известная NP-полная проблема выполнимости 3-КНФ сводится за полиномиальное время к задаче распознавания рассматриваемого множества. Теорема доказана.

Отметим, что поиск «-клики в «-дольном графе с двумя вершинами в каждой доле сводится за полиномиальное время к поиску модели пропозициональной конъюнктивной нормальной формы с двумя литералами в каждой дизъюнкции (2-КНФ), которая в свою очередь может быть найдена за полиномиальное время, [Even, Itai, Shamir, 1976].

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

Если в «-дольном графе существует л-клика, то остается открытым вопрос о поиске других клик. Нижнюю оценку на число «-клик можно получить, вычислив группу автоморфизмов графа, сохраняющих разбиение множества вершин на доли. Поскольку для каждой перестановки вершин легко проверить, является ли она автоморфизмом графа, мы приходим к задаче о поиске скрытой подгруппы в группе перестановок, то есть такой подгруппы, для проблемы принадлежности к которой имеется распознающий алгоритм полиномиального времени, а требуется найти порождающие и порядок этой подгруппы. Эту задачу можно решить за полиномиальное время алгоритмом Симса [Симе, 1976]. Однако время его работы довольно велико. [Hoffmann, 1982]

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

Заметим, что поиск подгруппы решений явно заданной системы однородных линейных уравнений легко найти методом, являющимся обобщением алгоритма Гаусса, [Боревич, Шафаревич, 1985].

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

Системе попарно похожих слов (по одному слову в каждой из q последовательностей) соответствует g-клика в графе G.

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

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

Существует несколько подходов к поиску по набору нуклеотидных последовательностей сигнала - набора попарно похожих слов одинаковой длины по одному из каждой последовательности, выбранных из данной доли входных последовательностей В типичной ситуации нас интересует сигнал, включающий сайты из не менее чем 80% входных последовательностей, но заранее не известно какие последовательности не содержат сайтов

Оптимизационные алгоритмы строят последовательность сигналов, качество которых (то есть значение некоторого функционала) монотонно возрастает. Примером является алгоритм SeSiMCMC [Favorov, Gelfand, Gerasimova, Ravcheev, Mironov, Makeev, 2005] и алгоритм IRSA [Данилова, Горбунов, Гельфанд, Любецкий, 2001]. Комбинаторные алгоритмы, например MITRA [Eskin, Pevzner, 2002], основаны на поиске консенсуса, то есть слова или в общем случае весовой матрицы, который близок к некоторым словам из большинства входных последовательностей.

Задача поиска сигнала тесно связана с задачей множественного выравнивания В действительности, набор сигналов, состоящих из сайтов маленькой длины можно объединить в общее множественное выравнивание. И наоборот, зная множественное выравнивание легко выделить наиболее консервативные участки. Однако популярные программы множественного выравнивания, например, CLUSTAL [Thompson, Higgs, Gibson, 1994] нестабильно работают при добавлении невыравниваемых последовательностей, а также при поиске коротких сигналов. Поэтому множественное выравнивание выполнялось для тех участков, на которых обнаружены консервативные слова с помощью алгоритма на основе поиска клики.

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

Для поиска вторичной структуры РНК, согласованной с множественным выравниванием, и для выравнивания белков автором использовалась программа множественного выравнивания MultAlign, реализованная А.А. Мироновым. А также применялась программа, реализующая алгоритм из работы [Горбунов, Миронов, Любецкий, 2003].

Таблица 1 Алфавиты нуклеотидных и аминокислотных последовательностей.

Нуклеотиды

G Гуанин S G или С

А Аденин W А или U

С Цитозин Н А или С или U

Т Тимин В G или U или С и Урацил V G или С или А

R Пурин (А или G) D G или U или А

Y Пиримидин (С или U) N G или А или U или С

М А или С * Делеция

К G или U

Таблица 1. (Продолжение)

Аминокислоты

F Фенилаланин Phe Н Гистидин His

М Метионин Met К Лизин Lys

Р Пролин Pro С Цистеин Cys

Y Тирозин Туг G Глицин Gly

N Аспарагин Asn I Изолейцин Не

Е Глютаминовая кислота Glu S Серии Ser

R Аргинин Arg А Алании Ala

L Лейцин Leu Q Глютамин Gin

V Валин Val D Аспарагиновая кислота Asp

Т Треонин Thr W Триптофан Тгр

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

Качество выравнивания Е двух белков оценивается обычным S\ способом и вычисляется по формуле Е = Ктпехр — , где числа тип ч равны длинам выравниваемых аминокислотных последовательностей, К и Я - некоторые константы, S - величина, зависящая от относительных частот аминокислотных замен и от частот делеций на выравнивании. При этом вес замены аминокислот вычисляется в соответствии с матрицей BLOSUM62.

0.2 Обзор результатов по регуляции экспрессии генов у хлоропластов и бактерий

Транскрипция происходит от 5' к 3' концу возникающей РНК, трансляция от N к С концу соответствующего белка РНК часто образует сложную вторичную структуру, состоящую из спиралей; каждая спираль состоит из пары участков РНК, которые называются плечами спирали. Длины плеч спирали равны, и к-й нуклеотид от 5'-конца левого плеча комплементарен к-му нуклеотиду от 3'-конца правого плеча. Линейно вложенные друг в друга спирали образуют шпильку.

Рис. 2. Вторичная структура РНК без псевдоузла.

Две спирали, у которых плечо одной лежит между плечами другой, образуют псевОоузел

Образование вторичной структуры РНК может прерывать транскрипцию (в этом случае обычно образуется длинная спираль, к которой примыкает U-богатый участок) или препятствовать инициации трансляции В этом случае спирали перекрывают сайт связывания

3' 5'

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

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

Белок-мРНК взаимодействие в хлоропластах Экспрессия многих генов хлоропластов водорослей и растений регулируется белками, кодируемыми ядерной ДНК, которые связывают мРНК хлоропластов, [Nickelsen, 2003] Эти белки влияют на редактирование (editing) и инициацию трансляции мРНК Детальные экспериментальные исследования по поиску соответствующих сайтов известны для одной водоросли Chlamydomonas remhardtu [Hauser, Gillham, Boynton, 1996] и небольшого числа растений [Nickelsen, 2003] и [Zerges, 2000].

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

Ранее экспериментально показана классическая регуляция генов синтеза триптофана у двух актинобактерий у Corynebactermm glutamicum [Heery, Dunican, 1993] и у Stryptomyces venezuelae [Lin, Pradkar, Vining, 1998]. Предсказано несколько новых аттенюаторов

При другом механизме рибосома непосредственно перекрывает сайт связывания белка Rho. В этом случае терминация не связана с образованием шпильки Такой механизм регуляции транскрипции для гена катаболизма триптофана подробно описан в статьях [Konan, Yanofsky, 2000] и [Gong, Yanofsky, 2003] Для оперонов синтеза цистеина аналогичный механизм предсказан впервые.

Регуляторная структура с участием Т-бокса. Хорошо известен механизм регуляции транскрипции с участием тРНК [Grundy, Henkin, 2003] Незагруженная тРНК стабилизирует структуру мРНК, которая включает терминатор транскрипции Таким образом, уровень экспрессии зависит от концентрации загруженных тРНК. Ниже впервые предсказаны Т-боксы, связанные с регуляцией трансляции.

Рибопереключатели Регуляция, как транскрипции, так и трансляции часто связана с образованием характерной структуры РНК, которая стабилизируется небольшой молекулой-лигандом. [Rodionov, Vitreschak, Mironov, Gelfand, 2003], [Mandal, Breaker, 2004], [Vitreschak, Rodionov, Mironov, Gelfand, 2004].

0.3 Обзор результатов по моделированию кинетики образования вторичной структуры РНК

Моделирование классической аттенюации позволяет предсказывать эффективность регуляции транскрипции по одной нуклеотидной последовательности Важно, что при этом можно предсказать не только наличие регуляции, но и получить количественные оценки Такой механизм регуляции у кишечной палочки хорошо известен [Сингер, Берг, 1998]. История исследований классической аттенюаторной регуляции и результаты массового поиска такой регуляции у протеобактерий изложена в [Vitreschak, Lyubetskaya, Shirshin, Gelfand, Lyubetsky, 2004].

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

В работах [Миронов, Кистер, 1985], [Миронов, Кистер, 1989], [Mironov, Lebedev, 1993] и [Danilova, Pervouchme, Favorov, Mironov, 2006] рассматривается моделирование методом Монте-Карло кинетики сворачивания вторичной структуры РНК на уровне микросостояний и поставлена задача моделирования этого процесса на уровне макросостояний В работе [Xayaphoummine, Bucher, Isambert, 2005] метод вероятностного моделирования Монте-Карло применяется для изучения процесса формирования псевдоузлов у вторичной структуры РНК. В них предлагается оригинальный прием для ускорения процедуры Монте-Карло, который позволяет исключить повторение пройденных состояний марковской цепи. В модели используется другая, но также исключающая повторения и быстрая организация процедуры Монте-Карло В работе [Elf, Ehrenberg, 2005] вероятность антитерминации вычисляется по явной формуле, как сумма двух слагаемых: первое из них - вероятность того, что рибосома находится на одном из регуляторных кодонов и происходит формирование антитерминатора в то время, как полимераза доходит до U-богатого участка, а второе из них - умноженная на 0 5 вероятность того, что рибосома покинет стоп-кодон, когда антитерминатор еще не сформировался Коэффициент 0 5 мотивируется тем, что в такой ситуации с вероятностью 0.5 формируется что-то одно - терминатор или антитерминатор

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

С помощью этих алгоритмов получены следующие новые потенциальные регуляторные структуры РНК. Найдены консервативные структуры РНК, которые обеспечивают потенциальную регуляцию трансляции шести генов у хлоропластов посредством взаимодействия белков с РНК Предложена гипотеза о том, что зависимая от света регуляция трансляции гена рчЬА сформировалась на ранних стадиях эволюции, а именно: до появления интронов в генах белков и до расхождения зеленых и пурпурных водорослей. Найдена классическая аттенюаторная регуляция перед генами биосинтеза триптофана, триптофанил- и лейцил-тРНК синтетазами некоторых актинобактерий Перед геном leuA у многих актинобактерий найден регуляторный элемент нового типа, названный LEU-элементом. Найдены консервативные структуры РНК, включающие Т-бокс, которые обеспечивают потенциальную регуляцию трансляции гена ileS у многих актинобактерий и гена alr3806 у Nostoc. Найдены ген лидерного пептида и консервативный участок РНК, которые обеспечивают потенциальную Rho-зависимую аттенюаторную регуляцию на уровне транскрипции генов биосинтеза цистеина, и определена структура оперонов, содержащих эти гены у актинобактерий. Найдены новые тиаминовые рибопереключатели, вовлеченные в регуляцию трансляции некоторых атинобактерий.

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

1. Боревич 3 И, Шафаревич И Р. Теория чисел М ■ Наука, 1985

2. Горбунов К Ю, Миронов А А, Любецкий В А. Поиск консервативных вторичных структур РНК // Молекулярная биология. Т. 37, 2003. С. 850860.

3. Данилова JI.B , Горбунов К Ю, Гельфанд М С , Любецкий В.А Алгоритм выделения регуляторных сигналов в последовательностях ДНК // Информационные процессы. Т 1, 2001. С. 56-63.

4. Леонтьев Л А, Селиверстов А.В., Любецкий В.А. Алгоритм массового поиска у бактерий вторичных структур, включающих Т-бокс // Молекулярная биология Т 39, 2005. С. 1076-1078

5. Любецкий В.А, Горбунов К Ю., Пирогов С А, Рубанов Л И, Селиверстов А В. Алгоритм и результаты счета для модели регуляции экспрессии генов у бактерий на основе формирования вторичных структур РНК // Информационные процессы. Т. 5, 2005. С. 337-366.

6. Любецкий В А, Рубанов Л И, Селиверстов А В , Пирогов С.А. Модель регуляции экспрессии генов у бактерий на основе формирования вторичных структур РНК // Молекулярная биология. Т. 40, № 3, 2006. С. 497-511.

7. Любецкий В А., Селиверстов А.В. Вычисление эффективности регуляции биосинтеза триптофана у бактерий на основе модели классической аттенюации // Информационные процессы Т 6, 2006 С. 5557

8. Любецкий В А., Селиверстов А.В. Многодольные графы с двумя вершинами в каждой доле // Информационные процессы. Т. 4, 2004. С. 127— 132.

9. Любецкий В.А., Селиверстов А В. Некоторые алгоритмы, связанные с конечными группами // Информационные процессы. Т. 3, 2003. С. 39-46.

10. Любецкий В.А., Селиверстов А В. Регуляция экспрессии генов биосинтеза аминокислот и аминоацил-тРНК синтетаз у Актинобактерий // Молекулярная биология Т. 39, 2005. С. 1072-1075.

11. Миронов А А, Кистер АЭ. Теоретический анализ кинетики образования вторичной структуры РНК в процессе транскрипции и трансляции. Учет дефектных спралей // Молекулярная биология. Т. 19, 1985.С 1350-1357

12. Миронов А А, Кистер А.Э Теоретический анализ структурных перестроек в процессе образования вторичных структур РНК // Молекулярная биология. Т. 23, 1989. С. 61-71.

13. Селиверстов А.В, Любецкий В.А. Алгоритм поиска консервативных участков нуклеотидных последовательностей // Информационные процессы Т. 6,2006 С. 33-36

14. Селиверстов А В., Любецкий В А Особенности синтеза цистеина у Corynebacterium, Mycobacterium и Propionibacterium II Информационные процессы Т. 4, 2004. С. 247-250

15. Селиверстов А В, Любецкий В А Поиск консервативных участков в лидерных областях генов в случае известного дерева видов // Информационные процессы Т 5, 2005 С. 265-270

16. Селиверстов АВ, Любецкий В А Регуляция трансляции в хлоропластах // Информационные процессы. Т. 5, 2005. С 400-404.

17. Симе Ч.К Вычислительные методы в изучении групп перестановок // Вычисления в алгебре и теории чисел. М.: Мир, 1976 С 129-147.

18. Сингер М., Берг П. Гены и геномы. М/ Мир, 1998.

19. Схрейвер А. Теория линейного и целочисленного программирования. М. Мир, 1991

20. Damlova L.V., Pervouchine D.D., Favorov A.V, Mironov A.A RNAKINETICS- A web server that models secondary structure kinetics of an elongating RNA // Journal of Bioinformatics and Computational Biology. V 4, 2006. P. 589-596.

21. Das A, Crawford IP , Yanofsky С Regulation of tryptophan operon expression by attenuation in cell-free extracts of Escherichia coli II The Journal of Biological Chemistry V 257, No 15, 1982 P 8795-8798

22. Even S, Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems // SIAM Journal on Computing. V. 5, 1976. P. 691-703.

23. Gong F, Yanofsky C. Rho's role in transcription attenuation in the tna operon of E coh // Methods Enzymol V 371, 2003. P. 383-391.

24. Grundy F.J., Henkin T.M The T box and S box transcription termination control systems // Front Biosci. V. 8, 2003. P d20-31.

25. Hauser С R, Gillham N.W., Boynton J E. Translation regulation of chloroplast genes//The Journal of Biological Chemistry V 271,1996 P 1486— 1497.

26. Heery D.M, Dunican LK. Cloning of the trp gene cluster from a tryptophan-hyperproducing strain of Corynebacterium glutamicum. Identification of a mutation in the trp leader sequence // Applied and Environmental Microbiology. V. 59, 1993 P. 791-799.

27. Henkin T M., Glass В L, Grundy F.J. Analysis of the Bacillus subtilis tyrS gene, conservation of a regulatory sequence in multiple tRNA synthetase genes // J Bacterid. V. 174, 1992. P. 1299-1306.

28. Lin C., Pradkar A S, Vining L.C. Regulation of an antramlate synthase gene in Streptomyces venezuelae by trp attenuator // Microbiology. V. 144, 1998. P. 1971-1980

29. Lyubetsky V.A, Seliverstov A.V. Note on cliques and alignments // Информационные процессы. Т. 4, 2004, С. 241-246.

30. Mandal М, Breaker R R. Gene regulation by nboswitches // Nat Rev Mol Cell Biol V. 5,2004. P 451-463.

31. Mathews D H., Disney M.D, Childs J L, Schroeder S J , Zuker M, Turner D.H. Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure // PNAS. V. 101, 2004. P. 7287-7292.

32. Mathews D H, Sabina J, Zuker M., Turner D.H. Expanded Sequence Dependence of Thermodynamic Parameters Improves Prediction of RNA Secondary Structure // J. Mol. Biol. V. 288, 1999. P. 911-940.

33. Mironov A A, Lebedev V F. A kinetic model of RNA folding // BioSystems V. 30, 1993. P. 49-56.

34. Nickelsen J Chloroplast RNA binding proteins // Current Genet. V 43, 2003. P. 392-399

35. Rodionov D.A., Vitreschak A A, Mironov A.A, Gelfand M S Computational analysis of thiamin regulation in bacteria: Possible mechanisms and new THI-element-regulated genes // J Biol. Chem V. 277, 2003. P. 4894948959

36. Schaefer T J The Complexity of Satisfability Problems // Proceedmgs of the 10th Annual ACM Symposium on Theory of Computing, 1978, NY: ACM Press, 216-226.

37. Seliverstov A.V., Lyubetsky V.A. RNA regulatory structures in Actinobacteria and Cyanobactena // Proceedings of the International Moscow Conference on Computational Molecular Biology July 18-21, 2005 M, 2005 C. 351-353.

38. Seliverstov A.V, Putzer Н., Gelfand M.S , Lyubetsky V.A Comparative analysis of RNA regulatory elements of amino acid metabolism genes in Actinobacteria // BMC Microbiology. V. 5 N 54, 2005. 14 p.

39. Thompson J.D., Higgs D G, Gibson T J CLUSTAL W Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties, and weight matrix choice // Nucl Acids Res. V. 22,1994. P. 4673-4680.

40. Uptam S M, Chamberlin M.J. Escherichia coli RNA polymerase terminates transcription efficiently at rho-independent terminators on single-stranded DNA templates // Proc. Natl. Acad. Sci. USA V 94, 1997. P 1354813553.

41. Vitreschak A.G., Lyubetskaya E.V., Shirshin M A., Gelfand M S, Lyubetsky V.A. Attenuation regulation of amino acid biosynthetic operons m proteobacteria. comparative genomics analysis // FEMS Microbiology Letters V 234, 2004. P 357-370.

42. Vitreschak A.G, Rodionov D A, Mironov A.A, Gelfand M.S. Riboswitches- the oldest mechanism for the regulation of gene expression? // Trends in Genetics. V. 20, 2004. P 44-50.

43. Wilson К, von Hippel P. Transcription termination at intrinsic terminators: the role of the RNA hairpin // Proc Natl Acad. Sci. USA V 92 1995. P. 87938797.

44. Xayaphoummine A., Bucher Т., Isambert H. Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots // Nucleic Acids Res V 33, 2005. P. W605-610.

45. Yin H , Artsimovitch I, Landick R., Gelles J. Nonequilibrium mechanism of translation termination from observations of single RNA polymerase molecules//PNAS. V. 96, 1999. P. 13124-13129.

46. Zerges W Translation m chloroplasts // Biochimie. V. 82, 2000. P. 583601.

47. Zuker M. Mfold web server for nucleic acid folding and hybridization prediction//Nucleic Acids Res. V. 31, 2003. P.3406-3415.