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

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

ЛЮБЕЦКАЯ Елена Васильевна

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2004

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

Российской Академии наук

Научный руководитель: член-корреспондент РАН, доктор биологических наук, профессор Л.М. ЧАЙЛАХЯН

Официальные оппоненты: доктор физико-математических наук, профессор В.Г. ТУМАНЯН, доктор физико-математических наук, профессор П.В. ГОЛУБЦОВ.

Ведущая организация: Федеральное государственное унитарное предприятие Государственный научный центр Государственный научно-исследовательский институт генетики и селекции промышленных микроорганизмов.

Защита диссертации состоится «_»_2004 г. на заседании диссертационного совета Д.002.077.01 в Институте проблем передачи информации РАН по адресу: 127994, Москва, ГСП-4, Б. Каретный переулок, 19.

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

РАН.

Автореферат разослан «_»_2004 г.

Ученый секретарь диссертационного совета: доктор тех. наук., профессор

С.Н. Степанов

о ¿1

ВВЕДЕНИЕ. ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМЫ

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

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

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

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

Цель работы. Создание алгоритмов и программы для массового поиска аттенюаторной ре-

гуляции экспрессии генов. Тестирование эффективности алгори ных

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

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

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

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

Основные результаты. В диссертации получены следующие основные результаты.

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

• Показана практическая эффективность и надежность созданной программы ИХМ на основе ее детального тестирования на искусственных и биологических нуклеотидных последователь! ностях.

I • Проведен массовый поиск и во многих случаях найдены потенциальные сигналы аттенюа-

| торной регуляции (а в иных случаях алгоритм указал на предположительную причину их отсутст-I вия) у гамма-, альфа- и бета-протеобактерий (биосинтез разветвленных и ароматических амино-| кислот, гистидина и треонина, фенилаланил-тРНК-сиитетазы), а также и у грамположительных бактерий: из групп ВасНЫеэ, ЬасЮЬасПЫез, С1о$(п<Иа1с5, Вас1егоМе1ез/СЫогоЫ и ТЬегто^а!ез (биосинтез гистидина); описана эволюционная динамика аттенюаторной регуляции транскрипции.

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

• Предсказано новое семейство гистидиновых транспортеров - ортологов yuiF у В. subiilis (например, HI0325 у Н. Influenzae) и два гистидиновых транспортера ВС0629 у В. cereus (ортолог yvsH у В. subtilis) из белкового семейства АРА и ген у L. lactis (ортолог lysQ у Е. coll) из семейства АРС.

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

- гену ygeA у Pasteurella multocida приписана функция рацемазы разветвленных аминокислот;

- не ортологичные гены vat В, actX2 и actX3, соответственно, у Pasteurella multocida, Mann-

heimia haemolytica, Polaribacter Jilamenlus кодируют ацетилтрансферазы, участвующие в метаболизме гистидина.

• Показано, что биосинтез изолейцина у Xanthomonadales использует треонин дегидратазу TdcB, в отличие от IlvA у Е. coli.

• Показано, что у Pasteurellales бифункциональный ген thrA аспартат киназы/гомосерин дегидрогеназы регулируется не только треонинином и изолейцином (как это имеет место у Е. coli), но и метионином.

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

® Предсказано, что оперон his биосинтеза гистидина регулируется гистидин-зависимыми аттенюаторами у Bacillus cereus и Clostridium difficile, но и в тоже время регулируется гнстидиновы-ми Т-боксами у Lactococcus lactis и Streptococcus mutans.

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

Теоретическая и практическая ценность. До недавнего времени алгоритмы для поиска потенциальных альтернативных структур в одной регу/тторной области не предлагались (наши алгоритмы излагаются в Главе 1). Публикации автора по таким алгоритмам были одними из первых работ, сравнение наших алгоритмов с немногочисленными другими, см.1, приводится в тексте диссертации. Исследование аттенюаторной регуляции в классе протеобактерий начато сравни-

Gorodkin J„ Stricklin S.L., Stormo G.D. (2001) Discovering common stem-loop motifes in unligneted RNA sequences. Nucleic Acids Reseach, Vol. 29, No. 10, p. 2135-2144. Lathe W.C., Suyama M., Bork P. Identification of attenuation and anti-termination regulation in prokaryotes. Genome Biology 2002, 3: prepr. 3. p. 1-60. Eddy S.R. (2002) A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure. BMC Bioinformatics. 3:13. p. 1-16.

тельно недавно, см., например, работы2^; проведенный нами массовый поиск в классе грамполо-жительных бактерий является первым. Нами предсказаны (Глава 3) новые регуляторные сигналы этого типа (включая лидерные пептиды и регуляторные кодоны) у гамма-, альфа- и бета-протеобактерий, у фирмикутов из групп Bacillales, Lactobacillales и Clostridiales, у бактерий из групп Bacteroidetes/Chlorobi и Thermotogales. Соответствующие выравнивания нуклеотидных участков исходных последовательностей показали хорошую согласованность между собой предсказанных нами регуляторных сигналов. В Главе 2 приводятся результаты систематического тестирования наших алгоритмов для аттенюаторных и Т-бокс структур. В частности, были независимо найдены все ранее известные случаи аттенюаторной регуляции в классе гамма-протеобактерий2,3.

Апробация. Результаты диссертации докладывались на:

3-ей международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 4-9 сентября 2001.

3rd International Conference on Bioinformatics of Genome Regulation and Structure, BGRS'2002,14-20 July 2002, Novosibirsk, Russia.

Moscow Conference on Computational Molecular Biology (MCCMB'03), 22-25 July 2003, Moscow, Russia.

Научном семинаре по биоинформатике Института проблем передачи информации РАН под руководством профессора, члена-корреспондента РАН J1.M. Чайлахяна.

Научном семинаре по алгоритмам в геномике Московского государственного университета им. Ломоносова (механико-математический факультет) под руководством профессора В.А. Любецкого.

Московском семинаре по компьютерной генетике Института молекулярной биологин им. В.А. Энгельгардта РАН.

Публикации. По теме диссертации опубликовано б печатных работ.

Структура и объем работы. Диссертация состоит из 3 глав и 3 приложений; последние содержат основные результаты работы предложенных нами алгоритмов. Объем работы 110 страниц машинописного текста, в том числе, 13 таблиц и 26 рисунков.

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

Panina, EM., Vitreschak, A.G., Mironov, A.A. and Gelfand, M.S. (2001) Regulation of aromatic amino acid biosynthesis in gamma-proteobacteria. J. Mol. Microbiol. Biotechnol. 3,529-543.

3 Landick, R„ Tumbough, C.L. and Yanovsky, C. (1994) Transcriptional attenuation. In: Escherichia coli and Salmonella. Cellular and molecular biology (Ncidhardt, F.C., Ed.), p. 1263-1286. American Society for Microbiology, Washington, DC.

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

В главе 3 последовательно рассматриваются результаты массового поиска потенциальных сигналов аттенюаторной регуляции у протеобактерий и фирмикутов, у бактерий из групп Вас(его1с)е1е5/СЫогоЫ и ТЬсгтоЮе^еэ для случаев биосинтеза разветвленных и ароматических аминокислот, гистидина и треонина. Для каждого из этих случаев приводится и кратко комментируется соответствующая потенциальная оперонная структура. Затем приводятся выравнивания найденных РНК-структур.

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

СОДЕРЖАНИЕ РАБОТЫ

ГЛАВА 1. Два алгоритма и компьютерная программа поиска потенциальных аттснюаторных регуляторных структур мРНК

Рассматривается задача поиска аттенюаторной регуляции в лидерной области гена. Условимся обозначать плечи паузной шпильки 1 и 2, плечи терминатора 3 и 4, а плечи антитерминатора 2'иЗ'.

Первый алгоритм применяется для исследования вопроса о наличии аттенюаторной регуляции в одной данной лидерной области: в ней ищется сама аттенюаторная структура или обоснование ее отсутствия (т.е. ищется алгоритмическое указание на отсутствующий элемент такой структуры). Нами обычно рассматривались случаи, когда лидерная область имеет длину в 450-800 нуклеотидов, Алгоритм ищет структуру, состоящую из следующих элементов в исходной нук-леотидной последовательности: рамки считывания, кодирующей лидерный пептид с набором регуляторных кодонов в нем; тройки слов з/, которые служат «основой» для построения плеч: 5/ плеч 2 и 2', плеч 3 и 3', ^ плеча 4; и трех шпилек - терминатора, антитерминатора и паузной (в соответствии с этими плечами); участок остатков урацила.

В алгоритме используются следующие основные параметры: минимальная длина лидерного пептида (обычно, 30 нуклеотидов); длина участка, содержащего остатки урацила (обычно 7); минимальное количество самих остатков урацила (обычно 5) в этом участке; длина каждого из слов л'/, ¿г, ^ (обычно 8); максимальное расстояние (разница между началом первой буквы следующего слова и последней буквой предыдущего слова) между словами я/ и и (обычно 100); максимальное число различных (в паре и и некомплементарных (в парах 5/ и я;, х; и нуклеотидов (обычно 2); максимальная расстояние между началом слова ^ и концом слова (обычно 30); максимальное число отбираемых алгоритмом троек слов ^ (обычно 15); максимальное рас-

стояние между началом участка остатков урацила и концом слова (обычно 9); минимальное отношение числа пар СС к числу пар АТ в словах и 5} (обычно 1.3); интервальное значение длины фрагмента до начала петли антитерминатора - паузная шпилька ищется в этом фрагменте (обычно от 100 до 50).

Первый алгоритм последовательно находит:

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

2) Для каждого найденного' кандидата в лидерные пептиды ищутся все подходящие участки остатков урацила.

3) Для каждой пары таких объектов ищутся тройки слов S2, зд тройки сортируются в порядке увеличения расстояния между и Бз, из них отбирается заданное число первых.

4) Затем последовательно по 5? и ^ строится терминатор из условия минимума энергии, и аналогично - антитерминатор и паузная шпилька (при заданных параметрах).

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

Итак, терминатор образуется спариванием слов «г и и продолжением спаривания в обе стороны. Альтернативность терминатора и антитерминатора поддерживается за счет слова 5г: антитерминатор - это шпилька, включающая спаривание $/ и с изменением свободной энергии сворачивания, меньшим некоторого параметра (например, -10 ккал/моль, что обеспечивает возможность сворачивания антитерминатора).

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

1. При нашем выравнивании для многих оперонов и независимо от алгоритма определяются слова S|, я?, SJ и они оказываются консервативными. Так, для /гр-оперона эти слова выровнялись даже у гамма-, альфа- и бета-протеобактерий. Для каждого из 8 изученных оперонов у организмов из одной группы эти слова оказывались одинаковыми с точностью до нескольких букв (см. рисунки З-б в Приложении 2).

2. Для многих оперонов (например, ¡ИгА ВС у гамма-протеобшсгерий) антитерминаторы, полученные алгоритмом для разных организмов, имели сходную структуру: близкие значения числа

отрезков и их длин, близкие значения длин выпячиваний и их типов (односторонние или двусторонние), и т.д.

Алгоритм обеспечивает следующие условия:

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

2. Пересечение терминатора и антитерминатора.

3. Отсутствие пересечения паузной шпильки и терминатора.

4. Расстояние от конца поля регуляторных кодонов до начала левого плеча антитерминатора более 5 нуклеотидов.

Кроме того, алгоритм проверяет полученные им ответы на выполнение условия, которое наблюдалось во многих известных случаях аттешоаторной регуляции: расстояние от конца лидерного пептида до начала левого плеча антитерминатора от -3 до +3 нуклеотидов.

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

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

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

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

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

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

4 Верещагин Н.К., Любеикнй В.А. Алгоритм определения вторичной структуры РНК. Труды научно-исследовательского семинара логического центра ИФ РАН, выпуск 14, Москва, Издательство РАН, 2000, с. 99-109.

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

Этап 2: построение самой аттенюаторной структуры, который состоит из следующих двух шагов.

1. В множестве всех локально оптимальных шпилек отбираются те внешние петли (этих шпилек), начала и концы (В,С) которых повторяются более чем р~ 9 раз. Такие пары (В,С) будем называть частыми.

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

Построение терминатора для данных (В,С) и участка остатков урацила и происходит «вытягиванием» отрезков от (В,С), т.е. последовательным спариванием как можно большего числа нуклеотидов в 1-2 отрезка.

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

Итак, для поиска антитерминатора при уже полученном терминаторе берется частая пара (В|,С|) слева и ближайшая к петле (В,С) терминатора. Рассмотрим все локально оптимальные шпильки с данной парой (ВьСО , включая и их подшпильки; и среди них в качестве актктермина-тора отберем все те, у которых плечо С^ имеет не менее 5 общих нуклеотидов с плечом АВ, и также А> В|, С > Если таким образом нашлось пустое множество, то в качестве антитерминатора возьмем все ядра, построенные для множества всех локально оптимальных шпилек с данным (ВьС,).

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

Алгоритмы реализованы на языке Object Pascal в среде5 Delphi 5; вспомогательные алгоритмы - на языке Perl.

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

Сравнение результатов работы первого и второго алгоритмов. Отметим общие результаты сравнения их работы.

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

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

3. Если в исходной последовательности отсутствует лидерный пептид или антитерминатор неканонический, то первый алгоритм не находит структуру, но она может успешно быть найденной вторым алгоритмом. Например, в случае регуляции гена pheA в организме Y. pestis перед аттенюа-торной структурой встраивается мобильный элемент, и лидерный пептид хотя, конечно, существует, но находится на большом расстоянии от вторичной структуры и фактически не попадает в исходную последовательность разумной длины. В этом примере, антитермииатор также не содержит в последнем от его петли отрезке комплементарных слов si и sj, что рассматривается нами как случай неканонического антитерминатора, и первый алгоритм его не находит.

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

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

1 Алгоритмы также реализованы на языке ANSI С для параллельной вычислительной архитектуры с протоколом MPI - этот результат не включается в диссертационную работу. Часть вычислений велась на суперкомпьютере МВС-1000М (в МСЦ Миннауки, РАН, МГУ и РФФИ).

В качестве этих тестовых брались лидериые области, в которых аттенюация известна6; в случаях Е. соН_ИчВИ{\\ £. со/;_0) она получена экспериментально'. Таблица 1.

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

Y. pesiisjrpE да нет

Y.peslis_pheAl нет да

Y.pestis _pheA2 нет нет

E. coliJlvBN да нет

ГЛАВА 2. Тестирование алгоритмов

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

1) Второй алгоритм: тестирование на случайных последовательностях. На вход алгоритма подавалась случайная бернуллиевская последовательность длины 450 (порождаемая с помощью генератора случайных чисел стандартной библиотеки языка Perl). На выходе появлялось сообщение вида <Терминатор, Антитерминатор или -, Пауза или Участок U или ->, в котором знак «-» говорит об отсутствии соответствующего элемента, (или сообщение об ее отсутствии). Участком U считались фрагменты последовательности длины 7, в которых нуклеотид U встречался не менее 5 раз и допускались разрывы: два из одной буквы или один из двух букв. Найденными считались структуры, содержащие терминатор из не менее, чем трех пар комплементарных нуклеоти-дов, в то время как антитерминатор и/или паузная шпилька, участок U могли отсутствовать.

Было проведено 67 запусков алгоритма с указанными выше параметрами. Результаты приведены в таблице 2.1.1 Приложения 1. Из них видно, что в случайной последовательности, по крайней мере, терминатор находится почти в 40% случаев.

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

Атгенюаторная структура в случайной последовательности: Число соответствующих случаев:

Найдена (с участком U) 29

6 Panina, E.M., Vitrcschak, A.G., Mironov, A.A. and Gelfand, M.S. (2001) Regulation of aromatic amino acid biosynthesis in gamma-proteobacteria. J. Mol. Microbiol. Biolcchnol. 3,529-543.

7 Landick, R., Turnbough, C.L. and Yanovsky, C. (1994) Transcriptional attenuation. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 1263-1286. American Socicty for Microbiology. Washington, DC.

Не найдена {но участок и имеется) 21

Не найден даже участок II 17

Рассмотрим число пар (В,С), повторяющихся более чем р раз в множестве локально оптимальных шпилек, которое образовано вторым алгоритмом по исходной нуклеотидной последовательности. Такую пару (В,С) мы назвали частой. Число частых пар при значении порога р= 9 для тех же случайных и 20 тестовых биологических последовательностей приводятся в таблице 2.1.2 Приложения 1, третий столбец. Из нее и других наших вычислений видно, что число различных пар (В,С) в множествах локально оптимальных шпилек примерно на порядок меньше длины исходной последовательности, и число частых пар примерно в 4 раза меньше числа всех пар (В,С). 2) Второй алгоритм: тестирование на случайных последовательностях с участком и. На вход алгоритма подавались 20 бериуллиевских случайных последовательностей, использованных в пункте 1 тестирования, в которые дополнительно в случайных местах вставлялись 1-2 фрагмента из 5 нуклеотидов и, которые находились от начала последовательности на расстоянии не менее 100 нуклеотидов (с тем, чтобы алгоритм имел возможность построить структуру перед участком I)). На выходе появлялось такое же как выше сообщение <Терминатор мощности не менее 3, Антитерминатор или -, Пауза или -, Участок и или -> или сообщение об отсутствии такого терминатора.

В этом случае структуры находились чаще, чем в пункте 1, что, конечно, нежелательно. Поэтому было предложено указанное ниже дополнительное ко второму алгоритму условие, которое позволяет отличить последовательность, случайную даже с вставленным в нее (как выше) участком I), от биологической последовательности, содержащей атгешоацию. Таким образом, второй алгоритм, дополненный этим условием, может применяться и для решения задачи различения случайной последовательности от биологической, содержащей атгешоацию. Численные значения указанных ниже параметров соответствуют рассмотренному нами случаю последовательностей длины 450. Это условие состоит в следующем. Биологическая последовательность, содержащая ат-тенюаторную регуляцию, отличается от случайной последовательности с вставленными в нее 1-2 участками II, если для структур, найденных в ней вторым алгоритмом, выполняется одно из трех следующих свойств 1-3.

1. Ответ содержит ровно одну структуру и она «хорошая» в смысле:

а) участок и около терминатора найденной структуры содержит не менее б нуклеотидов подряд;

б) найденная структура имеет пересекающиеся (не менее чем на 5 нуклеотидов) терминатор и антитерминатор, а также паузную шпильку;

в) терминатор имеет не менее 5 пар комплементарных нуклеотидов.

2. Среди двух или трех найденных структур хотя бы одна удовлетворяет условиям I б и 1 в.

3. Найдено не менее 4 структур с различными парами (В,С) координат петли терминатора.

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

3) Второй алгоритм: тестирование на случайных последовательностях, содержащих биологически значимые терминаторы. На вход алгоритму подавались случайные бернуллиевские последовательности, использованные в пункте 2 тестирования, в которые перед участком U на расстоянии в 3 нуклсотида помещался фрагмент, содержащий биологически значимый терминатор из регуля-ториой области гена trpE организма Е. coli, а именно, фрагмент cagcccgcctaatgagcgggc. На выходе алгоритм выдавал такое же как выше сообщение.

На таких последовательностях второй алгоритм не дает удовлетворительных результатов: он не может систематически отличать такие последовательности от биологически значимых. Это видно из таблицы 2.3 Приложения 1.

4) Второй алгоритм: тестирование на биологических последовательностях, содержащих атте-нюаторную структуру. На вход алгоритму подавались регуляторные области длины 450, содержащие уже известную аттенюаторную регуляцию. На выходе алгоритма выдавалось такое же сообщение. Результаты тестирования приводятся в таблице 2.4 Приложения 1, из которой видно, что алгоритм находит атгешоацию с высокой точностью. Естественно, что он находит терминатор с более высокой точностью, чем антитерминатор, и последний с более высокой точностью, чем паузу.

5) Первый алгоритм: тестирование на биологических последовательностях, содержащих аттенюаторную структуру. На вход алгоритму подавались регуляторные области длины 450 из предыдущего пункта, содержащие аттенуаторную регуляцию. На выходе алгоритм выдавал четверку <Лидерный пептид, Терминатор, Антитерминатор, Пауза> или сообщение об ее отсутствии. В подавляющем большинстве случаев алгоритм нашел ответ с высокой точностью, что видно из таблицы 2.5 Приложения 1.

6} Второй алгоритм: тестирование на биологических последовательностях, содержащих альтернативные структуры типа Т-бокс. На вход алгоритма подавались регуляторные области длины 350-550, содержащие альтернативную регуляцию типа Т-бокс. На выходе алгоритм выдавал нары шпилек вида <антитерминатор, терминатор> или сообщение об их отсутствии. В этом случае терминаторы нашлись с точностью до 1-2 нуклеотидов; точность нахождения антнтерминагора указана в таблице 2.6 Приложения 1 и обычно она была весьма высокой.

7) Второй алгоритм: тестирование на биологических последовательностях, не содержащих аттенюаторов по результатам работы первого алгоритма. На вход второму алгоритму подавались лидериые области генов, в которых первый алгоритм не нашел атгенюзторной регуляции (а частности, не нашел лидериого пептида). Из таблицы 2.7 Приложения 1 видно, что примерно в 80% случаев второй алгоритм также не нашел в них аттенюаторной регуляции.

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

В этой главе разработанная нами компьютерная программа LLLM, реализующая два выше описанных и тестированных алгоритма, применялась для массового поиска аттенюаторной регуляции у протеобактерий, у фирмикутов и у бактерий из групп Bacteroidetes/Chlorobi и Thermotogales.

Процедура поиска заключалась в следующем: полные и частично секвенированные последовательности бактериальных геномов выгружались из базы данных Gcnbank (института NCBI). Список рассмотренных нами геномов приводятся в таблице 1 Приложения 2. Похожесть белков определялась с помощью алгоритма Смита-Уотермана, реализованного программой GenomeExplorer8. Ортологичные белки находились как наилучшие двунаправленные хиты9 сразу для нескольких геномов. В некоторых случаях приходилось дополнительно строить филогенетические деревья белков. Например, у P. midiocida был найден ген, высоко гомологичный двум генам ilvG и ilvB из К соИ, и только филогенетическое дерево построенное для данного семейства белков позволило аннотировать его как ilvG. Филогенетические деревья строились методом максимального правдоподобия, реализованного в пакете10 Phylip, множественные выравнивания выполнялись программой" CLUSTAL W. Для аннотации генов также применялась программа поиска трансмембранных сегментов (TMpred, http://www.ch.embnet.org/software/TMPRED_form.html) и использовались базы, содержащие функциональную и структурную аннотацию белков, в частности9'12 COG и InterPro. Затем, с учетом найденных сигналов регуляции, были получены оперонные

8 Mironov, А.А., Vinokurova, N.P. and Gelfand, M.S. (2000) GenomeExplorer: software for analysis of complété bacterial genomes. Mol. Biol. 34,222-231.

9 Talusov, R.L., Natale, D.A., Garkavtsev, I.V., Tatusova, T.A., Shankavaram, U.T., Rao, B.S., Kiryutm, В., Galperin, M.Y., Fedorova, N.D. and Koonin, H.V. (2001) The COG database: new developments in phylogenetic classification of proteins from complete genomes. Nucleic Acids Res. 29,22-28.

10 Felsenstein, J. (1981) Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol. 17,368-376.

11 Thompson, J.D., Gibson, T.J., Plewniak, F., Jeanmougin, F. and Higgins, D.G. (1997) The CLUSTAL_X windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools. Nucleic Acids Res. 25,4876-4882.

12 Mulder, N.J., Apweiler, R., Attwood, Т.К., Bairoch, A., Bateman, A., Binns, D., Bisv/as, M., Bradley, P., Bork, P., Bûcher, P., Copley, R„ Courcellc, E., Durbin, R., Falquet, L., Fleischmann, W„ Gouzy, J., Griffith-Jones, S., Haft. D., Hermjakob, H., Hulo, N.. Kahn, D., Kanapin, A., Krestyaninova, M., Lopez, R., Letunic, I., Orchard, S., Pagni, M., Peyruc, D., Ponting, C.P., Servant, F. and Sigrist, С J. (2002) InterPro: an integrated documentation resource for protein families, domains and functional sites. Brief Bioinform. 3,225-235.

структуры для рассмотренных нами организмов и генов биосинтеза аминокислот (приведены в таблицах 2-S Приложения 2).

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

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

Биосинтез шолсйцина, лейцина и валяна (сокращенно ILV). Новые возможные транскрипционные аттенюаторы найдены у гамма-, альфа-, бета-протеобактсрий. Возможные аттенюаторы оперонов ilvGMEDA найдены у энтеробактерий, у Pasteurellales (только в Р. multocida), у Vibrionales, Alteromonadales (в S. oneidensis), у Xanthomonadales. У Pseudomonadalcs найдена возможная атгенюация отдельно лежащего гена ilvA. У энтеробактерий найдена аттешоаторная регуляция оперона ilvBN, содержащего гены, кодирующие один из изозимов ацетолакгат-синтазы. Гены лидерных пептидов оперона ilvG содержат регуляторные кодоны трех аминокислот - изолей-цин, лейцин и валин (как и в экспериментально изученном случае Е. coli), а оперона ¡IvBN регуляторные кодоны только двух аминокислот - лейцина и валина.

Структура потенциальных оперонов биосинтеза 1LV весьма разнообразна. Например, у энтеробактерий и Vibrionales она имеет классический вид ilvGMEDA, а у Xanthomonadales - вид ilvCGM-tdcB-leuA. Здесь ген tdcB предположительно регулируется вместе с этим опероном и кодирует треонин дегидратазу, которая участвует в биосинтезе изолейцина.

У Р. multocida отмечен ген с неизвестной функцией (гомологичный гену ygeA у Е. coli), который локализуется в í/v-опероне HvGM-ygeA-ihDA. Ген ygeA слабо похож на аспартат рацемазу гасХ из В. subtllusx весьма вероятно, что он кодирует новый тип рацемазы разветвленных аминокислот.

Среди гамма-протеобактерий оперон leu регулируется атгенюацией у энтеробактерий. Pasteurellales, Vibrionales, Alteromonadales, но не у Pseudomonadales и других видов. Регуляторны-ми во всех этих случаях являются лейшшовые кодоны.

13 Данилова Л.В., Горбунов К.Ю., Гельфанд М.С., Любешшй В.А. (2001) Алгоритм выделения регулятормых сигналов в последовательностях ДНК. Мол. биол.. том 35, № 6, с. 987-995.

В группе альфа-протеобактерий впервые обнаружена потенциальная аттенюаторная регуляция единственной ацетолактат синтетазы ilvIH у Rhizobiales (Sinorhisobium meliloti, Agrobacte-rium tumefaciens, Mesorhizobium loti, Bradyrhizobium japonicum, Rhodopseudomonas palustris, Brucella melitensis), у Rhodobacter spp., Magnetospirillum magnetotacticum и у Caulobacter crescentus. Регуляторными кодонами этой аттенюации являются кодоны изолейцина, лейцина и валина. Заметим, что у гамма-протеобактерий опероны, участвующие в биосинтезе двух ацетолактат синтетаз IIvGM и IlvBN (у энтеробактерий), но не IlvIH, регулируются аттенюацией.

Группа ортологов гена lenA изопрошшмалат синтазы из Е. coli обнаружена у гамма-протеобактерий (исключая Pseudoraonadales) и у некоторых альфа-протеобактерий. Группа генов, названная нами 1еш12, которые похожи на гены, кодирующие изопропилмалат синтазу у Corynebacterium glutamicum, была найдена у альфа-протеобактерий, у некоторых бета-протеобактерий и у Pseudomonadales. В апьфа-протеобактериях оба типа 2-изопропилмалат синтазы LeuA и LeuA2 имеют потенциальные аттенюаторы. Эти предполагаемые аттенюаторы имеют лидерные пептиды с лейциновыми регуляторными кодонами, но их терминаторы слабые и не имеют участков остатков урацила. Эта ситуация кажется подобной регуляции оперонов trpE и trpGDC у Pseudomonadales, где имеется аттенюаторная регуляция в отсутствие ро-независнмой терминаторной структуры.

Биосинтез гистиднна. Потенциальные аттенюаторы были найдены у многих гамма-протеобактерий, у фирмикутов и у бактерий из групп Bacteroidetes/Chlorobi, и Thermoiogaies. В большей части гамма-протеобактерий (энтеробактерии, Pasteurellales, Vibrionales, Alteromonadales) имеется единый Aw-оперон, предположительно регулируемый аттенюаторами с гистидиновыми регуляторными кодонами, и имеется выраженная терминатор/антитерминаторная структура. Ат-тешоация не была найдена для his-генов у Pseudomonadales, Xanthomonadales и у некоторых других гамма-протео-бактерий.

У Bacillus/Clostridium, Bacteroidetes/Chlorobi, Thermotogales гистидиновые регулоны включают большую часть обычных Aw-генов и также ген hisZ или hisS гистидил-тРНК-синтетазы; они регулируются аналогично.

Отметим разнообразие механизмов регуляции his-генов. Например, у Lactococcus ¡actis и Streptococcus mutans his-оперон регулируется с помощью антитерминаторного механизма с образованием структуры Т-бокса14, а у Bacillus cereus и Clostridium difficile он предположительно регулируется классической аминокислотной аттенюацией; в тоже время, другие Streptococcus spp., а также Entrerococcus spp. лишены Лиг-генов.

Что касается гистияил-тРНК-синтетазы, то у Bacillus cereus имеются три кодирующие ее гена hisZ, hisZ2 и hisS. Оба гена hisZ и hisZ2 регулируются аттенюацией: один в составе his-

14 Delorme, С., Ehrlich, S.D. and Renault, Р. (1999) Regulation of expression of the Lactococcus lactis histidine Operon. J. Bacieriol. 181,2026-2037. Втрешак А.Г. Частное сообщение.

оперона, другой как отдельный ген. Третий ген hisS, как и его ортологи у Bacillus spp., Listeria spp., Enterococcus spp. и Lactococcus lactis, (предположительно) регулируется с помощью антитер-минаторного механизма с образованием структуры Т-бокса15.

Показана регуляция гистидином следующих генов. У Н. influenzae ген Ш0325 кодирует возможный транспортер (с 10 трансмембранными сегментами) и имеет потенциальный аттенюатор. В ряде геномов (в частности, у Fusobacterium nucleatum и Bacillus halodurans) этот ген кластеризуется с генами утилизации гистидина (hut локус). Возможно, этот ген и его ортологи (например, yuiF у В. subtilis) образуют новое семейство гистидиновых транспортеров.

У В. ceretis ген ВС0629, возможно, регулируется аттенюатором с гнстиднновымн регуля-торными кодонами. Этот ген ортологичен yvxH у В. ¿ublilii, гомологичен аргннин:орнитин антипортеру arcD у Pseudomonas aeruginosa и люипопому транспортеру lysî у Corinobacterium glutamicum. Эти белки относятся к семейству АРА антипортеров аминокислот и полиаминов.

У В. cereus имеются два паралога yvsH (BCÛ629 и ВС0865), из которых первый имеет атге-нюаторную регуляцию с гистидиновыми регуляторными кодонами, а второй (предполагаемый ли-зиновый транспортер) регулируется лизином с помощью лизин-специфичного регуляторного элемента16. Подобная ситуация наблюдается у L. lactis, где видны два паралогических транспортера LysP и LysQ. Оба белка подобны (более, чем на 50%) экспериментально подтвержденной лизино-вой пермеазе LysP из Е. coli. У L. laclis ген lysP регулируется LyS-элсментом (и, по видимому, участвует в транспорте лизина), а ген lysQ предположительно регулируется аттенюатором с гистидиновыми регуляторными кодонами. Таким образом, эти два транспортера могут иметь различное сродство к лизину и гистидину, и потому по разному регулироваться.

Все гены гистидинового регулона были найдены во всех анализируемых бактериях, за исключением гистидинол фосфатазы HisB у Pseudomonas spp.

Найдены три негомологичных гена с неизвестной функцией {actX2, vatB, actX3 соответственно у Mannheimia haemolytica, Pasteurella multocida, Polaribacter fllamentus), возможно кодирующих ацетилтрансферазы и регулируемые совместно с /гм-генами. Эти белки могли бы катализировать превращение гистамина в 4-бета-ацетиламиноэтил-имидазол (ЕС 2.3.1.-).

Биосинтез треонина. В опероне биосинтеза треонина у энтеробактерий, Pasteurellales, Vi-brionales, Alteromonadales и Xanthomonadalcs наблюдается обычный порядок генов thrABC. У Pseudomonadales и еще у некоторых бактерий гены треонинового биосинтеза разбросаны по геному. Более того, у энтеробактерий, Pasteurellales, Vibrionales, Alteromonadales и Xanthomonadaeis ген thrA кодирует бифункциональный белок - аспартат киназу/гомосерин депщрогеназу, а у

15 Chopin, A., Biaudet, V. and Ehrlich. S.D. (1998) Analysis of the Bacillus subtilis genome sequence reveals nine new T-box leaders. Mol. Microbiol. 29,662-664. Внтрешак А.Г. Частное сообщение.

16 Rodionov, D.A., Vitreschak, A.G., Mironov, A.A. and Gelfand, M.S. (2003) Regulation of lysine biosynthesis and transport genes in bacteria: yet another RNA riboswitch? Nucleic Acids Res. 31,6748-6757.

Pseudomonadales и у некоторых других гамма-протеобактерий thrA2 (аспартат киназа) и Ьот (го-мосерин дегидрогеназа) расположены в разных локусах. У Pseudomonadales наблюдались два гена гомосерин киназы thrB2 и thrH, которые не гомологичны ihrB из К colt.

Треониновые опероны регулируются аттенюацией у энтеробактерий, Pasteurellales, Vibrion-ales, Alteromonadales и Xanlhomonas campestris. Все предполагаемые аттенюаторы имеют треониновые и изолейциновые регуляторные кодоны, а также выраженные терминаторы и антитерминаторы.

Нами установлено, что у Pasteurellales (Haemophylus influenzae, Pasteurella multocida, Acti-nobacillus actinomycetemcomitans и Mannheimia haemolytica) регуляторными кодонами служат не только треонин и изолейцин, но и метионин. В самом деле, предполагаемая регуляция /йг-оперона у Pasteurellales концентрациями треонина, изолейцина и метионина может быть обоснована наличием у Pasteurellales только одной аспартат киназы/гомозерин дегидрогеназы, вместо двух изози-мов ТЬгА и MetL у других гамма-протеобактерий, которая входит в метаболические пути синтеза этих трех аминокислот.

Третья монофункциональная аспартат киназа LysC имеется у трех из пяти Pasteurellales, а именно, у P. multocida, Haemophylus ducrei и М. Haemolytica; и экспрессия гена lysC предположительно регулируется лизином посредством ¿KS-элемснтов (как у Е. coli).

Биосинтез ароматических аминокислот (триптофана, феиилалаиина) и фенилаланил-тРНК-сшггегазы. Были найдены предполагаемые trp-, pheA- и pheST-опероны у альфа-, бета- и у многих новых гамма-протеобактерий.

Атгешоаторная регуляция trp была показана для энтеробактерий, Vibrionales, Alteromonadales с регуляторными кодонами триптофана и при наличии сильных терминаторов и антятер-минаторов, Ген trp(E/G), возникший в результате слияния и кодирующий две компоненты антра-нилат синтазы (первый шаг триптофанового биосинтеза), возможно, регулируется аттенюацией во всех проанализированных нами альфа-протеобактериях из группы Rhizobiales кроме Brucella те-litensis.

Оперон pheA, возможно, регулируется аттенюаторами (с регуляторными кодонами фенила-ланина) у энтеробактерий, Vibrionales, Alteromonadales, а оперон pheST регулируется таким же образом только у энтеробактерий.

Опероны trpE и trpGDC у Pseudomonadales имеют некоторые особенности: несмотря на экспериментальные данные об атгенюаторной регуляции этих оперонов17, нами найдены только потенциальные лидерные пептиды с парой близких триптофановых кодонов, которые хорошо выравниваются для пяти Pseudomonadales, но наша программа не нашла для них ро-нсзависимых

17 Olekhnovich, I. and Gussin, G.N. (2001) Effects of mutations in the Pseudomonas putida miaA gene: regulation of the trpE and trpGDC Operons in P. putida by attenuation. J. Bacteriol. 183,3256-3260.

терминаторов. Возможно, это объясняется тем, что в этих случаях имеются менее выраженные и стабильные терминаторы и антитерминаторы.

ПРИЛОЖЕНИЯ

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

Затем содержит Приложение 2, примыкающее к материалу Главы 3, в которое включены таблицы оперонных структур и выравнивания сигналов регуляции биосинтеза аминокислот. А именно, таблица 1 содержит список геномов, в которых алгоритмом LLLM нами искалась атте-нюаторная регуляция, с указанием таксономических групп. Таблица 2 содержит предсказанные нами оперонные структуры и регуляции для ILV генов (биосинтез разветвленных аминокислот). Таблица 3 содержит предсказанные оперонные структуры и регуляции для HIS генов (биосинтез гистидина). Таблица 4 содержит предсказанные оперонные структуры и регуляции для THR генов (биосинтез треонина). Таблица 5 содержит предсказанные оперонные структуры и регуляции для trp, pheA и phuST генов (биосинтез триптофана и фенилаланина).

Кроме того, в Приложении 2 приводится рисунок 1, показывающий типичную («классическую») аттенюацию. И рисунок 2, содержащий пути биосинтеза аминокислот у гамма- и альфа-протеобактерий для четырех случаев: (a) ILV (изолейцина, лейцина, валина), (b) HIS (гистидина), (с) THR (треонина), (d) ароматических аминокислот (триптофана, тирозина, фенилаланина).

В Приложении 2 также приводятся важные для нас рисунки, примыкающие к материалу Главы 3: выравнивание предсказанных структур транскрипционной аттешоации биосинтеза разветвленных аминокислот у гамма- и альфа-протеобактерий (рис. 3). Затем выравнивание предсказанных структур транскрипционной аттешоации биосинтеза гистидина у гамма-, альфа-, фнрмикут и других бактерий (рис. 4). Выравнивание предсказанных структур транскрипционной аттенюации биосинтеза треонина у гамма-протеобактерий (рис. 5). Выравнивание предсказанных структур транскрипционной аттешоации trp, pheA and phc-ST оперонов у гамма- и альфа-протеобактерий (рис. 6).

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

ВЫВОДЫ

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

2. Предсказано IOS предполагаемых аттенюаторных структур для оперонов биосинтеза разветвленных и ароматических аминокислот, гистидина и треонина у протеобактерий, у фирмикут и у бактерий из групп Bacteroidetes/Chlorobi и Thennotogales. В некоторых из этих групп аттенюация обнаружена впервые.

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

- теку ygeA у Pasteurella multocida приписана функция рацемазы разветвленных аминокислот;

- не ортологичные гены vatB, actX2 и actX3, соответственно, у Pasteurella multocida, Mannheimia haemolytica, Polaribacter filamentus кодируют ацетилтрансферазы, участвующие в метаболизме гистидина.

4. Показано, что биосинтез изолейцииа у Xanthomonadales использует треонин дсгидратазу TdcB, в отличие от IlvA у Е coli.

5. Предсказано новое семейство гистидиновых транспортеров - ортологов yu'tF у В. subtilis (например, HW325 у Н. Influenzae) и два гистидиновых транспортера ВС0629 у В. cereus (ортолог yvsH у В. subtilis) из белкового семейства АРА и ген у L. Iactis (ортолог lysQ у Е. coli) из семейства АРС.

6. Предсказано, что оперон his биосинтеза гистидина регулируется гистидин-зависнмыми аттенюаторами у Bacillus cereus и Clostridium difficile, и в тоже время регулируется гистидиновыми Т-боксами у Lactococcus lactis и Streptococcus mutans.

7. Показаны следующие особенности аттенюаторной регуляции:

тем Ihr А аспартат киназы/гомосерин дегидрогеназы у Pasteurellales регулируется не только трео-нинипом и изоленцином (как у Е. colt), но и метионином;

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

ПУБЛИКАЦИИ автора по теме диссертации 1. Горбунов К.Ю., Любецкая Е.В., Любецкий В.А. О двух алгоритмах поиска альтернативной вторичной структуры РНК. Информационные процессы, РАН, том 1, №2,2001, стр. 178-187.

2. Леонтьев Л.А., Любецкая Е.В., Любецкий В.А. Модифицированный алгоритм поиска альтернативных вторичных структур РНК и результаты счета. Информационные процессы, РАН, 2002, том

2.№1,с. 100-105.

3. Lyubetsky E.V., Lyubetsky V.A. Algorithm for searching alternative secondary RNA structures. Proceedings of the third international conference of bioinformatics of genome regulation and structure, BGRS'2002, Novosibirsk, Russia, July 14-20,2002, v. 3, p. 15-17.

4. Любецкая E.B., Леонтьев Л.А., Гельфанд M.C., Любецкий В.А. Поиск альтернативных вторичных структур РНК, регулирующих экспрессию бактериальных генов. Молекулярная биология, том 37, №5,2003. с. 834-842.

5. Любецкая Е.В., Леонтьев Л.А., Любецкий В.А. Поиск альтернативных вторичных структур в классе гамма-протеобактерий. Информационные процессы, РАН, том 3, №1,2003, с. 23-38.

6. Lyubetskcya Е. К, Leontiev L.A., Lyubetsky V.A. Algorithm for detecting alternative secondary RNA structures and mass analysis attenuator regulation in proteobacteria, MCCMB'03, 2003, p. 144-145.

РНБ Русский фонд

2007-4

I4939"

1 5 MAP 2004

ВВЕДЕНИЕ. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

ГЛАВА 1. ДВА АЛГОРИТМА И КОМПЬЮТЕРНАЯ ПРОГРАММА ПОИСКА ПОТЕНЦИАЛЬНЫХ АТТЕНЮАТОРНЫХ РЕГУЛЯТОРНЫХ СТРУКТУР мРНК.

§1.1. Первый алгоритм

§ 1.2. Второй алгоритм

§1.3. Сравнение результатов работы первого и второго алгоритмов

ГЛАВА 2. ТЕСТИРОВАНИЕ АЛГОРИТМОВ.

§2.1. Второй алгоритм: тестирование на случайных последовательностях

§2.2. Второй алгоритм: тестирование на случайных последовательностях с участком остатков урацила U

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

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

§2.5. Второй алгоритм: тестирование на биологических последовательностях, содержащих альтернативные структуры типа Т-бокс

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

ГЛАВА 3. МАССОВЫЙ ПОИСК АТТЕНЮАТОРНОЙ РЕГУЛЯЦИИ.

§3.1. Особенности аттенюаторной регуляции биосинтеза гистидина, треонина, разветвленных и ароматических аминокислот

§3.2. Метаболические пути, оперонные структуры и выравнивания аттенюаторов изученных оперонов

§3.3. Характерные аттенюаторные структуры, найденные алгоритмом

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

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

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

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

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

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

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

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

Основные результаты. В диссертации получены следующие основные результаты:

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

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

• Проведен массовый поиск и во многих случаях найдены потенциальные сигналы аттенюаторной регуляции (а в иных случаях алгоритм указал на предположительную причину их отсутствия) у гамма-, альфа- и бета-протеобактерий (биосинтез разветвленных и ароматических аминокислот, гистидина и треонина, фенилаланилтРНК-синтетазы), а также и у грамположительных бактерий: из групп Bacillales, Lactobacillales, Clostridiales, Вacteroidetes/Chlorobi и Thermotogales (биосинтез гисти-дина); описана эволюционная динамика аттенюаторной регуляции транскрипции.

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

• Предсказано новое семейство гистидиновых транспортеров - ортологов yuiF у В. subtilis (например, Ш0325 у Я. Influenzae) и два гистидиновых транспортера ВС0629 у В. cereus (ортолог yvsH у В. subtilis) из белкового семейства АРА и новый ген у L. lactis (ортолог lysQ у Е. coif) из семейства АРС.

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

- гену ygeA у Pasteurella multocida приписана функция рацемазы разветвленных аминокислот;

- не ортологичные гены vatB, actX2 и actX3, соответственно, у Pasteurella multocida, Mannheimia haemolytica, Polaribacter filamentus кодируют ацетилтрансферазы, участвующие в метаболизме гистидина.

• Показано, что биосинтез изолейцина у Xanthomonadales использует треонин дегидратазу TdcB, в отличие от IlvA у Е. coli.

• Показано, что у Pasteurellales бифункциональный ген thrA аспартат кина-зы/гомосерин дегидрогеназы регулируется не только треонинином и изолейцином (как это имеет место у Е. coli), но и метионином.

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

• Предсказано, что оперон his биосинтеза гистидина регулируется гистидин-зависимыми аттенюаторами у Bacillus cereus и Clostridium difficile, но и в тоже время регулируется гистидиновыми Т-боксами у Lactococcus lactis и Streptococcus mutans.

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

Теоретическая и практическая ценность. До недавнего времени алгоритмы для поиска потенциальных альтернативных структур в одной регуляторной области не предлагались (наши алгоритмы излагаются в Главе 1). Публикации автора по таким алгоритмам были одними из первых работ, сравнение наших алгоритмов с немногочисленными другими приводится в следующем пункте. Исследование атгенюа-торной регуляции в классе протеобактерий начато сравнительно недавно, см., например, работы1,3; а проведенный нами массовый поиск в классе грамположительных бактерий является первым. Нами предсказаны (Глава 3) новые регуляторные сигналы этого типа (включая лидерные пептиды и регуляторные кодоны, терминаторы и часто антитерминаторы и паузные шпильки) у гамма-, альфа- и бета-протеобактерий, у фирмикутов из групп Bacillales, Lactobacillales и Clostridiales, у бактерий из групп Bacteroidetes/Chlorobi и Thermotogales. Соответствующие выравнивания нуклеотид-ных участков исходных последовательностей показали хорошую согласованность между собой предсказанных нами регуляторных сигналов. В Главе 2 приводятся результаты систематического тестирования наших алгоритмов для аттенюаторных и Т-бокс структур. В частности, нами были независимо найдены все ранее известные случаи аттенюаторной регуляции в классе гамма-протеобактерий1,2. Работы, содержащие алгоритмы или методы поиска аттенюаторных сигналов. В работе [1] рассмотрен метод поиска консервативной вторичной структуры РНК с помощью двух программ FOLDALIGN и COVE, описание которых дано в предыдущих статьях этих авторов. Для выравнивания нуклеотидных последовательностей без учё

1 Panina, Е.М., Vitreschak, A.G., Mironov, А.А. and Gelfand, M.S. (2001) Regulation of aromatic amino acid biosynthesis in gamma-proteobacteria. J. Mol. Microbiol. Biotechnol. 3,529-543. 2

Landick, R., Turnbough, C.L. and Yanovsky, C. (1994) Transcriptional attenuation. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), p. 1263-1286. American Society for Microbiology, Washington, DC. та вторичной структуры РНК ими использовалась программа CLUSTALW. Однако, такой метод часто не позволяет выделить одно выравнивание среди многих вариантов, близких по качеству. С другой стороны, существуют программы для поиска консервативных вторичных структур РНК в наборе последовательностей, заранее выровненных по нуклеотидному составу. Одна из таких программ - COVE. Она основана на методе представления вторичных структур с помощью стохастических контекстно-свободных грамматик SCFG. Особенностью этого метода является то, что алгоритм ищет общее (глобальное) выравнивание на всём протяжении исходных последовательностей. В действительности, консервативная структура, имеющая биологическое значение может располагаться лишь на небольших, но неизвестных участках исходных РНК. Поэтому применение алгоритмов, основанных на стохастических контекстно-свободных грамматиках эффективно лишь после предварительной обработки данных. Хотя теоретически такое выравнивание можно искать в любом данном наборе РНК, ответ обычно не удовлетворителен с биологической точки зрения.

Программа FOLDALIGN является расширением программы типа CLUSTALW. Она позволяет выравнивать последовательности с учётом как нуклео-тидного состава, так и вторичной структуры РНК. Программа FOLDALIGN сначала проводит попарное выравнивание последовательностей, используя метод динамического программирования. Затем проводится поиск множественного выравнивания, при котором множество выровненных последовательностей постепенно увеличивается, а новые последовательности сравниваются с консенсусом уже построенного выравнивания. Но программа FOLDALIGN учитывает лишь локальную структуру последовательностей. Поэтому найденная FOLDALIGN консервативная вторичная структура РНК может оказаться неудачной в целом. Результаты «локального» выравнивания программой FOLDALIGN и «глобального» программой COVE могут значительно отличаться. Локальный характер работы программы FOLDALIGN связан с тем, что она работает очень медленно и не пригодна для больших объёмов данных.

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

В работе [2] описан алгоритм для поиска вторичной структуры одной РНК, если она аналогична уже известной вторичной структуре некоторой РНК без псевдоузлов. Алгоритм основан на методе представления вторичных структур с помощью стохастических контекстно-свободных грамматик SCFG. Емкостная сложность этого алгоритма равна 0(N2*log N). Его проверка была проведена на большой выборке рибо-сомальных РНК.

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

Автору был доступен неопубликованный алгоритм множественного выравнивания Миронова, описание которого выполненное автором приводится ниже для полноты картины. Пусть дан набор нуклеотидных последовательностей. Фиксируем некоторое число I.

Колонкой ширины I в этом наборе назовем выборку, содержащую не более одного подслова длины I в каждой из этих последовательностей. Представителем колонки С в какой-то одной из этих последовательностей назовем подслово из этой последовательности, входящее в С (если его нет, то говорим, что представитель пустой). Качеством колонки назовем какую-то фиксированную меру того, насколько её слова попарно похожи друг на друга, а также, возможно, и того, сколь велико число слов в ней (например, это - взятая со знаком минус сумма энтропий вероятностных распределений на буквах, задаваемых столбцами этой колонки). Сходством двух колонок назовём какую-то фиксированную меру того, насколько слова одной колонки похожи на слова другой (например, это - взятая со знаком минус сумма информационных дивергенций распределений на соответствующих столбцах; фактически нам понадобится лишь случай, когда одна из этих двух колонок состоит из одного и того же слова). Скажем, что в последовательности «одно подслово лежит левее другого подслово» той же длины, если начало первого подслова строго левее начала второго полслова. Скажем, что «колонка Ci расположена целиком левее колонки Сг», если в любой последовательности, где обе эти колонки имеют непустых представителей, представитель для С/ лежит левее представителя для Сг (таким образом, два представителя могут перекрываться, но не могут совпадать). Расстоянием между подслова-ми одной последовательности назовём расстояние между их началами. Расстоянием между двумя колонками, одна из которых лежит целиком левее другой, назовём среднее расстояние между их представителями по тем последовательностям, в которых оба представителя непустые. Согласованностью упорядоченной пары <С/,Сг> колонок назовём какую-то фиксированную меру, отражающую, насколько мал разброс расстояний между их представителями в тех последовательностях, где представитель С/ лежит левее представителя С г (например, взятую со знаком минус дисперсию этих расстояний).

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

Дан набор Si, ., Sn нуклеотидных последовательностей. Найти упорядоченный слева направо такой набор С/,., Ст колонок ширины / (напомним, что / задаётся в качестве параметра, а т не фиксировано и не задано), что:

Для любых 1</ колонка Q лежит целиком левее колонки Cj, и качества колонок и согласованности пар соседних колонок как можно больше (здесь возможны разные формальные уточнения).

Теперь опишем основные этапы этого алгоритма. Этап 1. Построение начального множества колонок. По каждого подслову w (длины /) из какой-то последовательности 5,- строим колонку, в которую сначала включаем слово w из Si, а из каждой последовательности Sj (jri) включаем наиболее похожее на w слово (если сходство больше некоторого порога). Полученное начальное множество колонок обозначим М0.

Этап 2. Итерационное уточнение колонок. Каждую колонку С из Мо уточняем следующим образом. В каждой последовательности Si находим слово w(i), у которого максимальное сходство с колонкой С (если это сходство меньше некоторого порога, то полагаем w(i) пустым). Затем для каждого i заменяем представителя колонки С в 5, на слово w(i). Получаем новую колонку, для которой применяем ту же процедуру уточнения. После заданного числа итераций отберём из всех рассматривавшихся колонок наилучшую, или несколько наилучших (скорее всего процесс будет сходиться к наилучшей колонке). Среди всех отобранных (при разных С) колонок, оставим лишь те, качество которых не меньше порога. Их множество обозначим М/. Этап 3. Построение ориентированного графа на колонках. Строим ориентированный граф G, вершины которого — колонки из М/. Из колонки Су в колонку Сг проводим ребро, если количество последовательностей, где представитель Сг лежит левее представителя Си не превосходит е*п, где е— заданное достаточно малое число. Дополнительно возможна разметка вершин числами, отражающими качества соответствующих колонок, и разметка рёбер числами, отражающими согласованность пар соответствующих колонок.

Этап 4. Поиск максимального пути в орграфе. Ищем в G максимальный путь (в случае неразмеченного графа максимизируем число рёбер, составляющих путь, в случае размеченного - сумму числовых пометок на вершинах и рёбрах пути).

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

Этап 5. Удаление противоречивых представителей. Для каждого представителя w каждой колонки из Мг подсчитаем уровень его противоречивости U(w). Это - число других представителей в той же последовательности, расположение которых относительно w не соответствует отношению линейного порядка на колонках. Затем удаляем представителя с максимальным уровнем противоречивости и пересчитываем функцию U. Продолжаем так до тех пор, пока все представители не будут иметь нулевой уровень противоречивости. Теперь линейный порядок на полученном множестве Мз соответствует отношению «одна колонка целиком лежит левее другой». Мощность множества Мз обозначим через т.

Этап 6. Итерационное уточнение набора колонок. Смысл одной итерации в том, чтобы для каждой последовательности Si решить, нет ли в ней лучшего набора представителей, чем текущий. Для этого строим ориентированный граф G, вершины которого - все подслова из 5,- длины I. Проводим ребро из вершины w/ в вершину wz, если слово wj лежит левее слова W2 (заметим, что в G нет циклов). Каждую вершину w помечаем набором <с/, ст>, где q - число, отражающее сходство слова w с j-ой слева колонкой из Мз- Каждое ребро помечаем набором <du dm.j>, где dj - число, отражающее отклонение расстояния между wi и и>2 от расстояния между j-ой и (]'+1)-ой колонками (взятое со знаком минус).

Ищем в G максимальный путь, содержащий ровно т вершин. Точнее, максимизируем сумму пометок C](l)+di(l)+C2(2)+d2(2)+.+cm.j(m-l)+dm.1(m-l)+cm(m), где в скобках указаны номера вершин и рёбер на пути (от его начала), в которых берутся соответствующие компоненты разметки. Легко видеть, что поиск такого пути может быть проведён простой модификацией стандартной процедуры поиска максимального пути в ориентированном графе. Найденному пути соответствует новый набор представителей колонок в 5,-.

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

Из окончательного набора колонок выбрасываем представителей, у которых сходство со «своими» колонками ниже порога.

Этап 7 (дополнительный). Слияние близких колонок. Просматривая пары соседних колонок, производим слияние двух соседних колонок в одну, если расстояние между этими колонками мало, а их согласованность велика. Получившиеся в результате слияния колонки будут, конечно, нестандартными, так как их представители могут иметь разную длину (больше /)•

Итак, описан алгоритм поиска колонок. Укажем его возможные применения. Применение 1. Алгоритм может служить основой для поиска консервативных вторичных структур. А именно, для каждой спирали из каждой последовательности S записываем информацию о том, как расположены плечи этой спирали относительно писываем информацию о том, как расположены плечи этой спирали относительно представителей колонок в 5 (достаточно, видимо, указывать номера колонок, ближайших к плечу слева и справа представителей и расстояния до них). После этого каким-либо алгоритмом выделяем в (объединённом) множестве всех спиралей кластеры - подмножества спиралей с похожей информацией (например, можно использовать процедуру, аналогичную этапам 1 и 2 описанного алгоритма). Естественно ожидать, что спирали из одного кластера (возможно, после отбрасывания некоторого числа лишних спиралей) составят набор консервативных однотипных спиралей искомой структуры.

Применение 2. Алгоритм даёт процедуру множественного выравнивания последовательностей, состоящих из объектов произвольной природы. Действительно, замена подслов длины / на другие объекты не препятствует работе алгоритма. Его можно применять, например, при выравнивании последовательностей из плеч и боксов в алгоритме поиска консервативных вторичных структур из [4].

Применение 3. Найденные алгоритмом колонки из боксов могут поступать на вход описанного в [4] алгоритма.

Апробация. Результаты диссертации докладывались на:

• 3-ей международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 4-9 сентября 2001.

• 3rd International Conference on Bioinformatics of Genome Regulation and Structure, BGRS'2002,14-20 July 2002, Novosibirsk, Russia.

• Moscow Conference on Computational Molecular Biology (MCCMB'03), 22-25 July 2003, Moscow, Russia.

• Научном семинаре по биоинформатике Института проблем передачи информации РАН под руководством профессора, члена-корреспондента РАН JI.M. Чайлахяна.

• Научном семинаре по алгоритмам в геномике Московского государственного университета им. Ломоносова (механико-математический факультет) под руководством профессора В.А. Любецкого.

• Московском семинаре по компьютерной генетике Института молекулярной биологии им. В.А. Энгельгардта РАН.

Публикации. По теме диссертации опубликовано 6 печатных работ.

Структура и объем работы. Диссертация состоит из 3 глав и 3 приложений; последние содержат основные результаты работы предложенных нами алгоритмов. Объем работы 110 страниц машинописного текста, в том числе, 13 таблиц и 26 рисунков.

ЗАКЛЮЧЕНИЕ

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

2. Предсказано 108 предполагаемых аттенюаторных структур для оперонов биосинтеза разветвленных и ароматических аминокислот, гистидина и треонина у протео-бактерий, у фирмикут и у бактерий из групп Bacteroidetes/Chlorobi и Thermotogales. В некоторых из этих групп аттенюация обнаружена впервые.

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

- гену ygeA у Pasteurella multocida приписана функция рацемазы разветвленных аминокислот;

- не ортологичные гены vat В, actX2 и actX3, соответственно, у Pasteurella multocida, Mannheimia haemolytica, Polaribacter filamentus кодируют ацетилтрансферазы, участвующие в метаболизме гистидина.

4. Показано, что биосинтез изолейцина у Xanthomonadales использует треонин де-гидратазу TdcB, в отличие от IlvA у Е. coli.

5. Предсказано новое семейство гистидиновых транспортеров - ортологов yuiF у В. subtilis (например, HI0325 у Н. Influenzae) и два гистидиновых транспортера ВС0629 у В. cereus (ортолог yvsH у В. subtilis) из белкового семейства АРА и ген у L. lactis (ортолог lysQ у Е. coli) из семейства АРС.

6. Предсказано, что оперон his биосинтеза гистидина регулируется гистидин-зависимыми аттенюаторами у Bacillus cereus и Clostridium difficile, и в тоже время регулируется гистидиновыми Т-боксами у Lactococcus lactis и Streptococcus mutans.

7. Показаны следующие особенности аттенюаторной регуляции: ген thrA аспартат киназы/гомосерин дегидрогеназы у Pasteurellales регулируется не только треонинином и изолейцином (как у Е. coli), но и метионином; ацетолактат синтаза IlvIH у альфа-протеобактерий имеет регуляторные кодоны лейцина, изолейцина и валина.

1. Горбунов К.Ю., Любецкая Е.В., Любецкий В.А. О двух алгоритмах поиска альтернативной вторичной структуры РНК // Информационные процессы, РАН, том 1, №2,2001, стр. 178-187.

2. Леонтьев Л.А., Любецкая Е.В., Любецкий В.А. Модифицированный алгоритм поиска альтернативных вторичных структур РНК и результаты счета // Информационные процессы, РАН, 2002, том 2, №1, с. 100-105.

3. Любецкая E.B., Леонтьев Л.А., Гельфанд M.C., Любецкий В.А. Поиск альтернативных вторичных структур РНК, регулирующих экспрессию бактериальных генов // Молекулярная биология, том 37, № 5,2003, с. 834-842.

4. Любецкая Е.В., Леонтьев Л.А., Любецкий В.А. Поиск альтернативных вторичных структур в классе гамма-протеобактерий // Информационные процессы, РАН, том 3, № 1,2003, с. 23-38.

5. Lyubetskaya E.V., Leontiev L.A., Lyubetsky V.A. Algorithm for detecting alternative secondary RNA structures and mass analysis attenuator regulation in proteobacteria, MCCMB'03,2003, p. 144-145.

6. Gorodkin, J., Stricklin, S.L., Stormo, G.D. (2001) Discovering common stem-loop motifes in unligneted RNA sequences // Nucleic Acids Reseach, Vol. 29, No. 10, p. 21352144

7. Eddy, S.R. (2002) A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure // BMC Bioinformatics, 3:18, p. 116

8. Lathe, III, W.C., Suyama, M., Bork, P. (2002) Identification of attenuation and anti-termination regulation in prokaryotes. Genome Biology, 3: preprint 0003.1-0003.60.

9. Ю.Горбунов, К.Ю., Миронов, А.А., Любецкий, В.A. (2003) Поиск консервативных вторичных структур РНК // Молекулярная биология, том 37, № 5, с. 850-860.

10. Gollnick, Р and Babitzke, P. (2002) Transcription attenuation. Biochim. Biophys. Acta. 1577,240-250.

11. Vitreschak, A.G., Rodionov, D.A., Mironov, A.A. and Gelfand, M.S. (2004) Ri-boswitches: the oldest mechanism for the regulation of gene expression? Trends in Genetics. (in press, private letter).

12. Landick, R., Tumbough, C.L. and Yanovsky, C. (1994) Transcriptional attenuation. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 1263-1286. American Society for Microbiology, Washington, DC.

13. Gelfand, M.S. (1999) Recognition of regulatory sites by genomic comparison // Res. Microbiol. 150,755-771.

14. Osterman, A. and Overbeek, R. (2003) Missing genes in metabolic pathways: a comparative genomics approach// Curr. Opin. Chem. Biol. 7,238-251.

15. Koonin, E.V. and Galperin, M.Y. (2003) Sequence Evolution - Function: Computational approaches in comparative genomics, Kluwer Academic Publishers, Boston.

16. Umbarger, H.E. (1994) Biosynthesis of branched chain amino acids. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 442-458. American Society for Microbiology, Washington, DC.

17. Lawther, R.P., Lopes, J.M., Ortuno, MJ. and White, M.C. (1990) Analysis of regulation of the ilvGMEDA operon by using leader-attenuator-galK gene fusions // J. Bacterid. 172,2320-2327.

18. Bartkus, J.M., Tyler, B. and Calvo, J.M. (1991) Transcription attenuation-mediated control of leu operon expression: influence of the number of Leu control codons // J. Bacterid. 173,1634-1641.

19. Wek, R.C. and Hatfield, G.W. (1988) Transcriptional activation at adjacent operators in the divergent-overlapping ilvY and ilvC promoters of Escherichia coli // J. Mol. Biol. 203,643-663.

20. Jafri, S., Chen, S. and Calvo, J.M. (2002) ilvIH operon expression in Escherichia coli requires Lrp binding to two distinct regions of DNA // J. Bacterid. 184, 5293-5300.

21. Rhee, K.Y., Parekh, B.S. and Hatfield G.W. (1996) Leucine-responsive regulatory protein DNA interactions in the leader region of the ilvGMEDA operon of Escherichia coli // J. Biol. Chem. 271,26499-26507.

22. Winkler, M.E. (1996) Biosynthesis of histidine. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 485-505. American Society for Microbiology, Washington, DC.

23. Blasi, F. and Brum, C.B. (1981) Regulation of the histidine operon: translation-controlled transcription termination (a mechanism common to several biosynthetic oper-ons) // Curr. Top. Cell. Regul. 19,1-45.

24. Patte, J.C. (1994) Biosynthesis of threonine and lysine. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 528-541. American Society for Microbiology, Washington, DC.

25. Green, R.C. (1994) Biosynthesis of methionine. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 542-561. American Society for Microbiology, Washington, DC.

26. Rodionov, D.A., Vitreschak, A.G., Mironov, A.A. and Gelfand, M.S. (2003) Regulation of lysine biosynthesis and transport genes in bacteria: yet another RNA riboswitch? // Nucleic Acids Res. 31,6748-6757.

27. Grundy, F.J., Lehman, S.C. and Henkin, T.M. (2003) The L box regulon: lysine sensing by leader RNAs of bacterial lysine biosynthesis genes // Proc. Natl. Acad. Sci. U S A. 100,12057-12062.

28. Sudarsan, N., Wickiser, J.K., Nakamura, S., Ebert, M.S. and Breaker, R.R. (2003) An mRNA structure in bacteria that controls gene expression by binding lysine // Genes Dev. 17,2688-2697.

29. Pittard, A.J. (1996). Biosynthesis of aromatic amino acids. In: Escherichia coli and Salmonella. Cellular and molecular biology (Neidhardt, F.C., Ed.), pp. 458-484. American Society for Microbiology, Washington, DC.

30. Somerville, R. (1992) The Trp repressor, a ligand-activated regulatory protein // Prog. Nucleic Acid Res. Mol. Biol. 42,1-38.

31. Landick, R., Yanofsky, C., Choo, K. and Phung, L. (1990) Replacement of the Escherichia coli trp operon attenuation control codons alters operon expression // J. Mol. Biol. 216,25-37.

32. Springer, M., Mayaux, J.F., Fayat, G., etc (1985) Attenuation control of the Escherichia coli phenylalanyl-tRNA synthetase operon // J. Mol. Biol. 181,467-478.

33. Gavini, N. and Davidson, B.E. (1991) Regulation of pheA expression by the pheR product in Escherichia coli is mediated through attenuation of transcription // J. Biol. Chem. 266,7750-7753.

34. Bae, Y.M. and Stauffer, G.V. Genetic analysis of the attenuator of the Rhizobium meliloti trpE(G) gene // J Bacterid. 1991 Jun; 173(11): 3382-3388.

35. Panina, E.M., Vitreschak, A.G., Mironov, A.A. and Gelfand, M.S. (2001) Regulation of aromatic amino acid biosynthesis in gamma-proteobacteria. J // Mol. Microbiol. Biotechnol. 3, 529-543.

36. Benson, D.A., Karsch-Mizrachi, I., Lipman, D.J., Ostell, J. and Wheeler, D.L. (2003) GenBank // Nucleic Acids Res. 31,23-27.

37. Overbeek, R., Larsen, N., Walunas, Т., etc (2003) The ERGO genome analysis and discovery system // J. Bacteriol. 185, 5673-5684.

38. Mironov, A.A., Vinokurova, N.P. and Gelfand, M.S. (2000) GenomeExplorer: software for analysis of complete bacterial genomes // Mol. Biol. 34,222-231.

39. Tatusov, R.L., Natale, D.A., Garkavtsev, I.V., etc (2001) The COG database: new developments in phylogenetic classification of proteins from complete genomes // Nucleic Acids Res. 29,22-28.

40. Felsenstein, J. (1981) Evolutionary trees from DNA sequences: a maximum likelihood approach // J. Mol. Evol. 17,368-376.

41. Thompson, J.D., Gibson, T.J., Plewniak, F., Jeanmougin, F. and Higgins, D.G. (1997) The CLUSTALX windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools // Nucleic Acids Res. 25,4876-4882.

42. Mulder, N.J., Apweiler, R., Attwood, Т.К., Bairoch, A., Bateman, A., etc (2002) In-terPro: an integrated documentation resource for protein families, domains and functional sites // Brief Bioinform. 3,225-235.

43. Popham, D.L. and Setlow, P. (1993) Cloning, nucleotide sequence, and regulation of the Bacillus subtilis pbpE operon, which codes for penicillin-binding protein 4 and an apparent amino acid racemase // J. Bacteriol. 175,2917-2925.

44. Okada, H., Yohda, M., Giga-Ham,a Y., Ueno, Y., Ohdo, S. and Kumagai, H. (1991) Distribution and purification of aspartate racemase in lactic acid bacteria // Biochim. Bio-phys. Acta. 1078,377-382.

45. Tarleton, J.C., Malakooti, J. and Ely, B. (1994) Regulation of Caulobacter crescen-tus ilvBN gene expression // J. Bacteriol. 176,3765-3774.

46. Patek, M., Krumbach, K., Eggeling, L. and Sahm, H. (1994) Leucine synthesis in Corynebacterium glutamicum: enzyme activities, structure of leuA, and effect of leuA inac-tivation on lysine synthesis // Appl. Environ. Microbiol. 60, 133-140.

47. Casalone, E., Barberio, C., Cavalieri, D. and Polsinelli, M. (2000) Identification by functional analysis of the gene encoding alpha-isopropylmalate synthase II (LEU9) in Sac-charomyces cerevisiae // Yeast. 16, 539-545.

48. Olekhnovich, I. and Gussin, G.N. (2001) Effects of mutations in the Pseudomonas putida miaA gene: regulation of the trpE and trpGDC operons in P. putida by attenuation // J. Bacteriol. 183,3256-3260.

49. Delorme, C., Ehrlich, S.D. and Renault, P. (1999) Regulation of expression of the Lactococcus lactis histidine operon // J. Bacteriol. 181,2026-2037.

50. Chopin, A., Biaudet, V. and Ehrlich, S.D. (1998) Analysis of the Bacillus subtilis genome sequence reveals nine new T-box leaders // Mol. Microbiol. 29,662-664.

51. Steffes, C., Ellis, J., Wu, J. and Rosen, B.P. (1992) The lysP gene encodes the ly-sine-specific permease // J. Bacterid. 174,3242-3249.

52. Patte, J.C., Clepet, C„ Bally, M., Borne, F., Mejean, V. and Foglino, M. (1999) ThrH, a homoserine kinase isozyme with in vivo phosphoserine phosphatase activity in Pseudomonas aeruginosa // Microbiology. 4, 845-853.