Бесплатный автореферат и диссертация по биологии на тему

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

ВАК РФ 03.00.28, Биоинформатика

Автореферат диссертации по теме "Компьютерные методы массового анализа регуляции транскрипции в бактериях"

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

Ставровская Елена Дмитриевна

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

03 00 28 - биоинформатика

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

Москва-2008

003449134

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

Научный руководитель кандидат физико-математических наук, доктор биологических наук, профессор Миронов Андрей Александрович

Официальные оппоненты доктор физико-математических наук, профессор Туманян Владимир Гаевич

Институт молекулярной биологии имени В А Энгельгардта Российской академии наук

кандидат физико-математических наук Ройтберг Михаил Абрамович

Институт математических проблем биологии Российской академии наук

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

Защита диссертации состоится¿'¿у (/^и^ 2008 года в ^/'часов на заседании диссертационного совета Д 002 007 02 при Учреждении Российской академии наук Институте проблем передачи информации им А А Харкевича РАН по адресу 127994, г Москва, ГСП-4, Большой Каретный переулок, д 19, стр 1

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

Автореферат разослан ЪС 2008 года

Ученый секретарь диссертационного совета ^ Рожкова Г И

доктор биологических наук, профессор

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

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

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

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

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

Алгоритм выделения регуляторных мотивов в наборе областей перед ортологичными генами позволяет найти мотив, но не сам белок-регулятор Как правило,

\ *

1 7

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

Цели и задачи работы

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

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

2 Разработка методики и создание на ее основе программы для оценки статистической значимости экспериментально найденного дополнительного элемента основного промотора в геноме Thermus aquaticus

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

4 Создание программного конвеера для поиска регуляторных мотивов в рамках функциональных подсистем

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

Создание программных приложений на языке Java в среде программирования Eclipse Тестирование эффективности алгоритмов на различных искусственных и биологических данных с последующим применением к биологическим задачам выделения регуляторных мотивов

Научная новизна и практическая ценность

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

2

Программное приложение встроено в конвеер выделения регуляторных мотивов в рамках функциональных подсистем

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

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

1 3rd International Conference on Biomformatics ot Genome Regulation and Structure (BGRS'2002), 14-20 July 2002, Novosibirsk, Russia

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

3 4th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2004), 25-30 July 2004, Novosibirsk, Russia

4 International conference Bioinformatics Italian Society (BITS'2005), 2005, Milan, Italy

5 ХИ Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», 12-16 апреля 2005, Москва, Россия

6 2nd Moscow Conference on Computational Molecular Biology (MCCMB'05), 18-21 July 2005, Moscow, Russia

7 5lh International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2006), 16-22 July 2006, Novosibirsk, Russia

8 5"1 European Conference on Computational Biology (ECCB'2006), 21-24 January 2007, Eilat, Israel

9 3rd Moscow Conference on Computational Molecular Biology (MCCMB'07), 27-31 July 2007, Moscow, Russia

10 Информационные технологии и системы (ИТиС'07), 18-21 сентября 2007, Звенигород, Россия

11 Научном семинаре Учебно-научного Центра "Биоинформатика" ИППИ РАН, 15 октября 2007, Москва, Россия

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

Диссертационная работа содержит 98 страниц, в том числе 19 рисунков, 8 таблиц и список цитируемой литературы из 97 наименований Текст диссертации включает введение, содержащее постановку задач, обзор литературы, и 4 главы, в которых дано решение поставленных задач и обсуждение результатов, и список цитированной литературы

Содержание диссертации

В начале диссертационной работы приводится введение

В главе 1 представлен обзор литературы по теме диссертации

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

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

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

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

Мутация выбираем случайный ген в случайном геноме и меняем его аллель на другой случайным образом

Отбор исключается один геном с самым плохим качеством

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

Определение генома в Алгоритме ]• Каждый ген соответствует фрагменту ДНК из исходного набора, а каждый аллель - позиции в этом фрагменте (стартовой позиции сайта) Конкретный геном есть набор аллелей, то есть геном соответствует набору сайтов, по одному из каждого исходного фрагмента ДНК Специфическое значение аллели (NAN)

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

/ = Х Т /('.*)1оМ /('Д)/0.25] 0)

*-1 /шЛ.С.а.Т

/(/,*) = (й('Д) + 0.35 л/ЛГ)/(^ + 4* 0.35л/ЛГ) (2)

где/(/, к) - частота встречаемости нуклеотида / в позиции А, 0,35 и4*0.35л/м"" -псевдоотсчеты. Значение коэффициента 0.35 подобрано эмпирическим путем.

Определение генома в Алгоритме 2: Здесь под геномом будем понимать слово, представляющее собой потенциальный мотив. Каждая позиция в этом слове является геном, а нуклеотид, стоящий в этой позиции, аллелем. Качество генома определяется следующим образом:

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

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

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

математическое ожидание

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

-250 -1000

-250 -1000

0 100000 200000 количество итераций

0 100000 200000 количество итераций

Рисунок 1. Графики поведения математического ожидания и среднего квадратичного отклонения функции качества для Алгоритма 1 на искусственной выборке (для популяций размером 250 и 1 ООО геномов).

математическое ожидание

количество итераций

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

-4

t Л

---

О £00 tooo 15Ш 3X0 2ЯЮ количество итераций

Рисунок 2 Графики поведения математического ожидания и среднего квадратичного отклонения функции качества для Алгоритма 2 на искусственной выборке (для попутций размером 50 и 150 геномов)

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

Оба алгоритма были протестированы на искусственной выборке Тестирование показало, что Алгоритм 2 более эффективен, чем Алгоритм 1 Алгоритм 2 был также протестирован на двух реальных выборках из генома ЕсоЬ (кишечной палочки) Для каждой выборки были известны положения сайтов в исходных последовательностях При составлении тестов мы вырезали один за другим сайты из последовательностей выборки Таким образом, все меньшее число последовательностей в тесте содержало искомый мотив Каждый раз мы убирали самый сильный сайт, то есть сайт, имеющий наибольший вес относительно матрицы позиционных весов мотива Результаты представлены па рисунках 3 и 4 Для сравнения, мы применили к тем же выборкам алгоритм БеБМСМС' Для оценки полученных результатов был использован следующий критерий

'FaiomfA V Gelfaiul M S Gerasimova A V, Ravcheev D A , Mnonov A A , Makeev V J A Gibbs sampler tor identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length // Bioinformatics-2005 -Vol 21(10)-Pp 2240-2245

Опр. Истинный сайт (real) называется найденным (found), если существует предсказанный, который перекрывает его не менее, чем на половину.

Опр. Предсказанный сайт (predicted) называется хитом (hit), если существует истинный, перекрывающий его не менее, чем на половину. Далее вычисляются две функции Sr= found/real и Sh = hit/predicted.

1,2 1 0,8 В 0,6 0,4 0,2 0

Ж

°> Л ъ

в GeneticAig □ SeSiMCMC

количество последовательностей с сайтом

о GeneticAig □ SeSiMCMC

количество последовательностей с сайтом

Рисунок 3. Значения функций ЭГ и ЭЬ для пуринового теста для Алгоритма 2 и 8е81МСМС

0,8 0.7

0,6

0.5

0,4

0,3

0,2

0,1

П

о GeneticAig □ SeSiMCMC

количество последовательностей с сайтом

0,8 0,7 0,6 0,5 0,4 0,3 -0,2 0,1 -0

О GeneticAig □ SeSiMCMC

количество последовательностей с сайтом

Рисунок 4. Значения функци функций БГ и вЬ для аргининового теста для Алгоритма 2 и 8е81МСМС

В главе 3 рассказывается об оценке статистической значимости эксперимента, в результате которого был найден дополнительный элемент базального промотора в геноме ТлИегторЫ1т. Вначале дается краткое описание эксперимента. Целью эксперимента было установить участки ДНК ТИегтиз ¡ИегторкНиз, которые связываются с базальным сигма-

фактором и, тем самым, важны для инициации транскрипции. Применялся метод рандомизации двух цепей исходной ДНК с последующей выборкой тех участков, которые хорошо связываются с белком (SELEX, systematic evolution of ligands by exponential evolution). Были выделены одноцепочечные аптамеры ДНК, которые связываются с сигма-субъединицей с высокой аффинностью. Эти аптамеры содержали мотив, подобный боксу «-10» промотора, за которым следовал новый дополнительный мотив из 4-х нуклеотидов. Далее было показано, что мотив дополнительного аптамера работает как элемент базального промотора и допускает узнавание промотора РНК-полимеразой T.aquaticus в отсутствие бокса «-35» промотора.

Из литературы и открытых баз данных известно мало последовательностей промоторов бактерий рода Thermits, большая часть этих последовательностей принадлежит геному T.thermophilus. На рисунке 13 представлены все известные -35/-10 последовательности промоторов из T.thermophilus.

Sequent

А

dnaK ТССС TTGACAAAA;

trpAB CGAC. TT."ло ' '/'■>".:■ i G2 CC CC ТС. :GD£

S 20 A AG !1 lGGCGCAGGÍ

rpsO CTGG; iggggaggac ;gg< ::c-

dnaA 'i'CC'C. : сд : : 'agcgggtc;

trpZ CCCC f.GfAS^GGGC •ccccgtgt; ЗС-

16S RNA AGCCi JTîS&ÇMAAA I?TC

pyr Tccq TTGCIgggac 'GGGOOAGCK :g-

arg GCCC ttgcataac: . TG- .GGCCACG' 3GC

ORF4(arg) CCAC -itgacaggt: 'TTGATTCT;

sip CCCC: TTGAC k*-.- ¡CGCGTGAGÍ

leu AAGG: TTGÀÇrcrr - 'aggcctcg; ¡c¡

4 . 5S RNA CCTC; îïCctsckc-c. ;gcttc;cat( ;ggtg(

23S RNA G CGC ÏTGACAAAGC XT; ¡G;

В

P35 CTGG' п-слс-

P3i mm ti taca;•л : 'CCCCGCCCC ro;

P39 GCCC: тттсп'- jr.- iGGAGGCAA;

P211 rr~ IACACCCCTC

P215 GCACj ■aaagtgct:

P43 GGTC: ïTGTp.A.-,îf .A.GCTCAGC" PAT'

P7 GGGG ÎÏGTCAGA7 ; ;aagaaaaa- :CG'

P37 GGOO гг-злеелте: 'Ccctgctt:

P214 GGGC ÏIVCfcAT ОС :gcgcct?ac

GGCCCTT TGCGCGG

¡GAGCG7

(Osiphik and Jouchimiak, 1997)

(Koyama and Furukawa. 1990: Faraldo et al„ 1992)

(Leontiadouel al.. 2001)

(Serganov et al., 1997)

(Nurdmann and Mcsscr, 2000)

(Salo et al.. 1988)

(Hartmann and Erdmann, 1989)

(Van de Casleele el al.. 1997)

(Sanchez « al., 2000)

(Sanchez et al., 2000)

(fitraído et а!., 19921

(Croft et al.. 1987)

(SmicketaL 1988)

(Hartmann et al., 1987)

(Maseda and (Maseda and (Maseda and (Maseda and (Maseda and (Maseda and (Maseda and (Maseda and (Maseda and

Hoshino. 1995) Hoshino. 1995) Hoshino, 1995) Hoshino, 1995) Hoshino, 1995) Hoshino, 1995) Hoshino. 1995) Hoshino. 1995) Hoshino, 1995)

Рисунок 5. Последовательности промоторов T.thermophilus

Из рисунка видно, что два промотора содержат участок GGGA, найденый в аптамерах базального а-фактора. Существенная часть промоторов (7 из 22) содержат последовательность GGG перед боксом «-10» промотора. Для контроля, только один промотор содержит последовательность ССС. Ограниченное количество анализируемых промоторов не позволяет сделать статистически значимых выводов, но все же эти данные демонстрируют, что GGGA-подобные мотивы играют важную роль при распознавании

естественных промоторов Т ihermophúus Для дальнейшего анализа встречаемости GGGA-подобных мотивов в промоторах Т thermophilus был проведен биоинформатический анализ промоторов в данном геноме

Для предсказания последовательностей промоторов были построены позиционные весовые матрицы (профили) для консервативных блоков -35-го и -10-го боксов промотора, основываясь на 22 промоторах из Taquattcus и Т thermophilus, известных из литературы Полученными профилями просматривались две выборки межгенных участков всего генома Т thermophilus Первая выборка состояла из областей между генами, которые транскрибируются дивергентно (дивергоны), а вторая - из генов, которые тринскрибируются конвергентно (конвергоны) Дивергоны должны содержать промоторы, которые используются при транскрипции в обоих направлениях, а конвергоны не должны содержать промоторов и, таким образом, служат контрольной выборкой В итоге, была составлена выборка из 308 дивергонов длиной в среднем 135 нуклеотидов и 404 конвергона длиной в среднем 133 нуклеотида

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

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

Затем мы проверили, присутствует ли в предсказанных промоторах сразу после -10-го бокса мотив GGG (мы не искали полный мотив GGGA, поскольку ранее было показано, что последний нуклеотид А менее важен для промотора, чем первые GGG) Мы также подсчитали количество потенциальных промоторов, у которых по крайней мере два из трех нуклеотидов сразу после -10-го бокса были G В качестве контроля, мы посчитали количество потенциальных промоторов, имеющих по крайней мере два С в этих позициях Результат показал, что 33% промоторов в дивергонах содержат две или более G сразу после -10-го бокса, в то время как лишь 19% содержат два или более С Для сравнения, в

2RobiíonK McGuireAM Church GМ A comprehensive library of DNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K-12 genome// J Mol Biol - 1998-Vol 284(2)-Pp 241254

контрольной выборке промоторов в конвергонах 24% содержат два или более G и 22% два или более С Таким образом, мы показали, что предсказанные промоторы в дивергонах Т thermophilus насыщены GGG-подобными мотивами сразу после -10-го бокса по сравнению с контрольной выборкой Аналогичный анализ 197 промоторов Ecoh из базы данных DPlnteract3 показал, что только 7% из них содержат GGG-подобный мотив и 11% ССС-подобный мотив, что подтверждает специфичность GGG-подобных мотивов после -10 бокса для генома Г thermophilus

В главе 4 описывается алгоритм кластеризации регуляторных мотивов ClusterTree-RS Алгоритм состоит из двух частей - построение бинарного дерева и его обход На стадии обхода алгоритм выделяет узлы дерева, которые соответствуют кластерам

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

Функция сходства между поддеревьями (т е между соответствующими им мотивами) вычисляется по формуле

I (/,(«, к) - /, (*))(/, (<Д) - Л (*))

о = --. О)

ст

где 1к - информационное содержание в позиции к для общего набора сайтов, //¡, к) -частота встречаемости нуклеотида ; в позиции к для набора сайтов поддерева), / (к) -

среднее значение частоты в столбце к, 0 25алрГ1 и а^ТУ, - псевдоотсчеты Чем больше

Д тем ближе поддеревья

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

1 Robiwrt K, MtGuireA M, Chmih G M A comprehensive library ofDNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K-l 2 genome //J Mol Biol -1998-Vol 284(2)-Pp 241-254

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

(ЛГ, +¿-1)4^ +1-\)Щп[(а) + п2{1,к)У

(ь-щы,+ыг+£-1)1П(л1(а))'Щм<.£))'

(4)

где Ь - размер алфавита (Ь = 4), п/г.к) количество нуклеотидов типа / в позиции к в дочернем узле, Л^ - количество сайтов в дочернем узле Узел соответствует кластеру, если логарифм отношения правдоподобия является положительным для этого узла и отрицательным для его родительского узла

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

Алгоритм С1и$1егТгее накладывает сравниваемые мотивы друг на друга со всеми допустимыми смещениями и выбирает такое наложение, при котором функция £) сходства между мотивами принимает максимальное значение (т е мотивы наиболее скоррелированы) При выравнивании мотивов алгоритм С\1ШегТгее-113 дополняет все сайты до длины объединения, подгружая необходимые участки из генома Таким образом, мы восполним недостающую информацию в случае, если мотив был найден не точно К тому же, теперь мы вычисляем сходство между мотивами одинаковой длины

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

Для того, чтобы сравнить алгоритм CIusterTree-RS с другими существующими методами кластеризации, он был протестирован на искусственной выборке, описанной в (Qin et al 2003)4 Для построения тестовой выборки были выбраны 43 транскрипционных фактора Е coh из базы данных DPInteract и соответствующие им регуляторные сайты (общим числом 356) Частотная матрица для каждого фактора обрезалась справа до длины 15 и дополнялась справа и слева 3 случайными позициями Для каждой матрицы порождались искусственные регуляторные мотивы с таким же распределением частот нуклеотидов, количество таких мотивов совпадало с числом известных сайтов для этого регулятора Таким образом, каждый тестовый файл содержал 356 (по числу сайтов) искусственных регуляторных мотивов Число сайтов в мотиве выбиралась случайным образом в трех диапазонах 2-4, 2-10 и 5-10 сайтов Для каждого диапазона было создано по 100 тестовых файлов Результаты тестирования представлены в Таблице 1

Таблица 1 Сравнение средних значений ошибки для различных существующих методов

кластеризации

Размер Ошибка" км" нс-г НС-2" ВМС-Г ВМС-2' CIusterTree-

мотива RS8

2-4 Частота ошибок, 32,9 (5,2) 26,3 (6,1) 63,7 (1,7) 9,0(1,7) 5,8 (0,2) 10,7 (2,0)

сайтов % (Е, о)

Кол-во 43 43 250 (4,2) 34,4 38,0 49,8 (2,2)

кластеров, (Е, о) (1.5) (1,3)

2-10 Частота ошибок, 33,4 (3,9) 14,1 (3,1) 25,7 (2,4) 3,3(1,0) 2,5 (0,1) 5,7 (1 0)

сайтов % (Е, о)

Кол-во 43 43 118,9(6,7) 40,6 41,6 46,8 (1,7)

кластеров, (Е, а) (1,2) (0 6)

5-10 Частота ошибок, 31,6 (4,6) 3,9(1,1) 11,0 (1,5) 2,6 (0,4) 2,2 (0,0) 3,6 (0,7)

сайтов % (Е, о)

Кол-во 43 43 66,0 (3,9) 41,4 42,0 43 2 (1 0)

кластеров, (Е, о) (0,7) (0,1)

'Величина ошибки определяется как среднее число неправильно определенных в кластер, усредненное по 100 тестам и данное в процентах

ьМетод К-средних выполнен с помощью функции kmeans из пакета программ Splus Для подсчета матрицы расстояний использовалось расстояние Кульбака-Лейбера Количество кластеров к=43 полагалось известным

'Иерархическая кластеризация с помощью программ СошрагеАСЕ и Tree5 Значение порога выбрано таким образом чтобы получилось правильное число кластеров (43)

4 Qui 7. S , McC ucLA, Thompson W, Maierhojer L, Lawi cncc C £ IiuJS Identification of co-regulated genes through Bayesian clustering of predicted regulatory bmdmg sites // Nat Biotechnol -2003 - Vol 2I(4)-Pp 435439

5 Hughe1, J D, Estep P IV, Tavazoie S, Church G M Computational identification of cis-regulatory elements associated with groups of functionally related genes in Saccharomyces cerevisiae IIJ Mol Biol - 2000 - Vol 296(5) -Pp 1205-1214

''Иерархическая кластеризация теми же методами, но пороговое значение фиксировано и равно рекомендованному значению 0 7

'Сокращенная версия алгоритма ВМС6 (без выбора ширины мотива)

гПолная версия алгоритма ВМС

'а^егТгее-ЯЗ

Из таблицы видно, что алгоритм дает неплохие результаты, уступая только алгоритму ВМС, который определяет мотивы в кластеры в соответствии с апостериорным распределением вероятностей Однако, наш алгоритм работает существенно быстрее алгоритма ВМС (выборку из 215 мотивов программа ВМС обрабатывает за время порядка 2,5 часов, программа С1ш1егТгее-К8 за время порядка 5 минут), поскольку не переопределяет многократно мотивы в кластеры, а строит единую иерархическую структуру Когда мы пытаемся осуществить кластеризацию всех потенциальных регуляторных мотивов для одного генома (группы родственных геномов), мы имеем выборку из нескольких тысяч мотивов Наш алгоритм является кубическим по времени и обработает такую выборку за несколько часов, в то время как алгоритм ВМС экспоненциален по времени и будет работать несколько недель

Алгоритм был применен к выборкам потенциальных регуляторных мотивов из гамма-протеобактерий (ЕС выборка) и фирмикутов (ВЗ выборка) Потенциальные регуляторные мотивы были получены путем применения программы поиска регуляторных мотивов 5е57МСА/С к наборам областей, выделенных перед ортологичными генами7 Были найдены кластеры, соответствующие известным мотивам, которые содержали новые сайты (то есть были найдены новые гены для известных регулонов) Были также обнаружены новые мотивы (то есть новые потенциальные регулоны), которые перечислены в Таблице 2

6 Qui Z S McCue LA , Thompson W, Maierhoftr L , Lowttnce C E, Liu J S Identification of co-regulated genes through Bayesian clustering ofpiedicted regulatory binding sites //Nat Biotechnol - 2003 - Vol 21(4)- Pp 435439

7 Damlova L V, Lyubenky VA, Gelfand MS An algorithm for identification of regulatoiy signals in unaligned DNA sequences, its testing and parallel implementation // 111 Silico Biol - 2003 - Vol 3(1-2) - Pp 33-47

Таблица 2. Потенциальные новые регулоны, найденные при применении алгоритма О^егТгее-КЗ

к выборкам ES и BS.

выборка N Гены функция logo

EC 1 nrdD фермент; метаболизм 2'-деоксирибонуклеотидов

nrdA фермент; метаболизм V-деоксирибонуклеотидов

UbiE фермент; биосинтез кофакторов, переносщики; менахинон, убихинон

proS фермент; аминоацил-тРНК-синтетаза, модификация тРНК

BS 2 pyrR аттенюация (антитерминация) пиримидинового опрерона (ругРВСАОРЕ) в присутствии иМР (биосинтез пиримидина) 3" л тЛ1 ,9? Ш ? LV

pyrP биосинтез пирримидинов

pyrF биосинтез пирримидинов биосинтез пиримидинов

BS 3 ylpC (fapR) Неизвестная функция МшШ :=гз8Баяая8йяая;;йЯЯ3 8з

yhfB (yhfC) Неизвестная фенкция

Указано имя гена ВлиЬн7к, соответствующее мотиву, однако сайт непосредственно перед геном ВлиЫШз не найден или удален из кластера как ложный. Кластер содержит сайты, найденные перед ортологичными генами в родственных организмах.

Был произведен анализ геномов альфа-протеобактерий. Ортологические ряды были получены из базы данных Р1ю§з8. Потенциальные регуляторные сигналы были выделены с помощью программы 81§па1Х9. Было получено 9 потенциальных новых регулонов: центральный метаболизм, транспортеры азотсодержащих кислот, кислород-индуцируемая регуляция фиксации азота, биосинтез тиамина, биосинтез рибосомальных белков, метаболизм ДНК и РНК, метаболизм цинка, защита от кислорода и Метаболизм марганца.

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

8 Merkeev I. K, Novichkov P.S., Mimnov A A PHOG: a database of supergenomes built from proteoine complements // BMC Evol Biol - 2006 - Vol. 22 - Pp. 6-52

' Mironov A.A., Vinokurovu N.P., Gel'falnd M.S. Software for analyzing bacterial genomes // Mol Biol (Mosk). -2000 - Vol. 34(2) - Pp. 253-262.

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

Конвеер включает в себя процедуру, которая убирает слишком близкие геномы из исходной группы Для определения расстояний между геномами мы использовали филогенетическое дерево организмов, которое построено по множественному выравниваю высококонсервативных белков из 74 кластеров ортологичных генов из базы данных COGs" Нами было выбрано пороговое значение 0,01 Геномы, расстояние между которыми меньше порога, считаются слишком близкими Пороговое значение подобрано так, что близкими геномами считаются штаммы и некоторые близкие виды (например, Neisseria gonoi rhoeae и Neisseria meningitidis) Поскольку функциональная подсистема может содержать гены не из всех запрашиваемых геномов, отсев близких геномов производится после проецирования группы геномов на исследуемую подсистему

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

Для поиска мотива в наборе областей перед генами мы использовали алгоритм SignalX

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

Каждый найденный мотив характеризуется функциями оценки качества мотива -информационным содержанием и p-value Об истинности мотива можно судить по

10 Ovtrbeek R el al The Subsystems Approach to Genome Annotation and its Use in the Project to Annotate 1000 Genomes//Nucleic Acids Research - 2005 - Vol 33(17) - Pp 5691-5702

" Talmov R L , Koomn L V, Lipmart D J A genomic perspective on protein families//Science - 1997-Vol 278(5338)-Pp 631-637

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

В областях перед генами встречаются так называемые участки низкой сложности, состоящие из нуклеотидов двух (реже одного) типов (например, в и С), повторяющихся с некоторой периодичностью Такие участки могут иметь функциональное значение, однако они редко являются сайтами связывания факторов транскрипции Если эти области встречаются перед несколькими генами выборки, то при поиске эти участки в силу искаженного нуклеотидного состава определяются как консервативный потенциальный мотив Причем, если область низкой сложности длиннее искомого мотива, то в силу периодичности будет считаться, что она содержит несколько перекрывающихся сайтов Например, в последовательности ОСОСОСССОСОСОСССОСОС (20 нуклеотидов) содержится 3 консервативных сайта длины 16 со сдвигом 2 Такие ложные мотивы составляют большую часть перепредсказаний

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

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

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

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

диаграмм — характеристики качества мотивов: к^(р_уа1ие) и информационное содержание (¡пО- Из сопоставления диаграмм а) и б) видно, что при добавлении комплементарных сайтов области черных и серых точек перекрываются меньше. При добавлении фильтра областей низкой сложности количество перепредсказаных мотивов сильно сократилось. На диаграмме можно выделить область, которая содержит все подтвержденные мотивы (^(р_уа1ие)<-100 и тГ>10), и область, которая практически не содержит неподтвержденных мотивов (^(р_уа!ие)<-200 и ¡пР>12.5).

з -300-о.' -400

6 8 10 12 14 16 18 |ПГ

а) базовая модель

б) модель с добавлением комплементарных сайтов

в) модель с добавлением комплементарных сайтов и фильтра областей низкой сложности.

6 8 10 1г 14 16 18 го 22

Рисунок 14. Сопоставление характеристик качества (1о§(р_уа1ие) и информационного содержания) найденных мотивов.

Выводы.

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

2. Разработана и применена методика для проверки статистической значимости результатов эксперимента, показавшего новый дополнительный элемент основного промотора в геноме Г/ге/таг«' ациайсив.

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

4 Создан и тестирован программный конвеер для поиска регуляторных мотивов в рамках функциональных подсистем, в который встроена процедура кластеризации

Список публикаций по теме диссертации.

1 Stavrovskaya Е D, Mironov A A Two genetic algorithms for identification of regulatory signals//In Silico Biol 2003 Vol 3(1-2) P 49-56

2 Stavrovskaya E D, Mironov A A Clustering regulatory signals by binary trees // Biophysics (Moscow) 2003 Vol 48 Suppl 1 P S17-S20

3 Ставровская E Д, Макеев В Ю, Миронов A A ClusterTree-RS алгоритм кластеризации регуляторных сигналов с помощью бинарного дерева // Молекулярная биология 2006 Т 40 №3 С 465-473

4 Fekhstov А , Bar ¡nova N, Sevostyanova А , Heyduk Е, Bass I, Vvedenskaya I, Kuznedelov К, Merkiene E, Stavrovskaya E, Khmasauskas S, Nikiforov V, Heyduk T, SeverinovK, Kulbachmskiy A A basal promoter element recognized by free RNA polymerase sigma subumt determines promoter recognition by RNA polymerase holoenzyme // Mol Cell 2006 Vol 23 № 1 P 97-107

5 Миронов A A, Ставровская E Д, Макеев В Ю Способ исследования совместной регуляции генов бактерий и прогнозирования содержания новых регулонов и функций генов 2006 регистрационный номер 2006127264

6 Stavrovskaya Е D, Mironov A A A genetic algorithm for identification of regulatory signals // Proc 3d International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2002) 2002 Vol 1 P 26-27

7 Stavrovskaya E D, Mn onov А А В inary tree for clusterization of regulatory signals // Proc Moscow Conference on Computational Molecular Biology (MCCMB'03) 2003 P 218-219

8 Stavrovskaya E D, Mironov A A Binary tree for clustering of regulatory signals // Proc 4th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2004) 2004 Vol 1 P 195-199

9 Stavrovskaya E D, Mironov A A Binary tree for clustering of regulatory signals // Proc International conference BITS'2005 2005 P 85

10 Ставровская Е Д, Миронов A A ClusterTree программа кластеризации регуляторных сигналов с помощью бинарного дерева // Материалы XII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов» 2005 С 36-37

11 Stavrovskaya Е D, Makeev V J, Mironov A A ClusterTree-RS The binary tree algorithm for identification of co-regulated genes by clustering regulatory signals // Proc Moscow Conference on Computational Molecular Biology (MCCMB'05) 2005 P 385

12 Slavrovskaya E D, Makeev VJ, Merkeev 1 V, Mironov A A Tool for automatic aetection of co-regulated genes // Proc 5'th European Conference on Computational Biology (ECCB'2006) 2007

13 Stavrovskaya E D, Makeev VJ, Merkeev I V, Mironov A A Tool for automatics detection ot co-regulated genes // Proc 5th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2006) 2006 Vol 1 P 172-175

14 Stavrovskaya E D, Ctpriano M, Dubchak IL, Mironov A A , Gelfand MS Automated search for regulatory motifs in upstream regions of genes from the functional subsystems // Proc Moscow Conference on Computational Molecular Biology (MCCMB'07) 2007 P 283

15 Ставровская E Д, Сиприано M, Дубчак И Л, Миронов А А , Гечьфанд М С Автоматический поиск регуляторных сигналов перед генами в рамках функциональных подсистем // Труды конференции Информационные технологии и системы (ИТиС'07) 2007 С 330-331

Благодарности. Автор выражает искреннюю благодарность своим научным руководителям, Андрею Александровичу Миронову и Михаилу Сергеевичу Гельфанду, за руководство, помощь и поддержку при выполнении диссертации, а также Роману Сутормину, Всеволоду Юрьевичу Макееву, Ольге Калининой и Дмитрию Виноградову, за участие, ценные советы и продуктивное обсуждение

Ставровская Елена Дмитриевна

КОМПЬЮТЕРНЫЕ МЕТОДЫ МАССОВОГО АНАЛИЗА РЕГУЛЯЦИИ ТРАНСКРИПЦИИ В БАКТЕРИЯХ Работа посвящена разработке эффективных методов, алгоритмов и программных приложений для анализа регуляции транскрипции в геномах прокариот Исследовалась возможность применения генетических алгоритмов к задачи поиска регуляторных мотивов в наборе областей, взятых перед ортологичными генами в группе близкородственных геномов Разработаны генетические алгоритмы с различным способом выбора параметров и целевой функции и произведено их сравнения Показано, что генетический алгоритм, использующий алгебраический способ описания мотива, является более эффективным

Разработана и применена методика для оценки статистической значимости экспериментально найденного дополнительного элемента основного промотора в геноме Thermus aquaticus

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

Stavrovskaya Elena Dmitrievna

COMPUTATIONAL METHODS FOR THE LARGE-SCALE ANALYSIS OF TRANSCRIPTIONAL REGULATION IN BACTERIAL GENOMES

Eificient methods, algorithms and applications for the analysis of transcription regulation in procariotic genomes were developed Genetic algorithms were applied to identification of the regulatory motifs in a set of orthologous upstream regions from closely related genomes We developed and compared genetic algorithms with different selection of parameters and criterion function and demonstrated that the genetic algorithm with an algebraical motif mterpritation is more efficient

We developed and applied technique to estimate the statistical significance of an additional basal promoter element experimentally found in the Thermus aquaticus genome

We devepoled a new motif similarity measure Based on this measure we developed a fast and efficient algorithm for clustering regulatory motifs Using this algorithm we predicted new potential members of known regulons and new potential regulons in the genomes of the gamma-proteobactena, firmicutes and alpha-proteobactena

We developed and tested a pipeline searching for regulatory motif upstream of genes from functional subsystems This pipeline utilizes the developed clustering procedure

\

Заказ № 225/09/08 Подписано в печать 26 09 2008 Тираж 100 зкз Уел пл 1,25

/ ООО "Цифровичок", тел (495) 797-75-76, (495) 778-22-20

' ^ \ www cfr ru, e-mail info@cfr ru

Введение Диссертация по биологии, на тему "Компьютерные методы массового анализа регуляции транскрипции в бактериях"

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

Цели и задачи работы.4

Методика исследования.5

Научная новизна и практическая ценность.5

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

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

Публикации.7

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

Заключение Диссертация по теме "Биоинформатика", Ставровская, Елена Дмитриевна

выводы

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

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

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

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

Благодарности: Автор выражает искреннюю благодарность своим научным руководителям, Андрею Александровичу Миронову и Михаилу Сергеевичу Гельфанду, за руководство, помощь и поддержку при выполнении диссертации, а также Роману Сутормину, Всеволоду Юрьевичу Макееву, Ольге Калининой и Дмитрию Виноградову, за участие, ценные советы и продуктивное обсуждение.

Список работ, опубликованных по теме диссертации

1. Stavrovskaya E.D., Mironov A. A. Two genetic algorithms for identification of regulatory signals // In Silico Biol. — 2003. — Vol. 3(1-2). — P. 49-56.

2. Stavrovskaya E.D., Mironov A. A. Clustering regulatory signals by binary trees // Biophysics (Moscow). — 2003. — Vol. 48 Suppl. 1. — P. S17-S20.

3. Ставровская Е.Д., Макеев В.Ю., Миронов A.A. ClusterTree-RS: алгоритм кластеризации регуляторных сигналов с помощью бинарного дерева // Молекулярная г биология,— 2006,— Т. 40. №3. — С. 465-473.

4. Feklistov A., Barinova N., Sevostyanova A., Heyduk Е., Bass I., Vvedenskaya I., Kuznedelov K., Merkiene E., Stavrovskaya E., Klimasauskas S., Nikiforov V., Heyduk Т., Severinov K., Kulbachinskiy A. A basal promoter element recognized by free RNA polymerase sigma subunit determines promoter recognition by RNA polymerase holoenzyme//Mol Cell. — 2006,— Vol. 23. №1,— P. 97-107.

5. Миронов А.А., Ставровская Е.Д., Макеев В.Ю. Способ исследования совместной регуляции генов бактерий и прогнозирования содержания новых регулонов и функций генов // 2006. — Патент, регистрационный номер 2006127264.

6. Stavrovskaya E.D., Mironov A.A. A genetic- algorithm for identification of regulatory signals. // Proc. 3d International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2002). — Novosibirsk, Russia, 2002. Vol. 1. P. 26-27.

7. Stavrovskaya E.D., Mironov A.A. Binary tree for clusterization of regulatory signals // Proc. Moscow Conference on Computational Molecular Biology (MCCMB'03). — Moscow, Russia, 2003. P. 218-219.

8. Stavrovskaya E.D., Mironov A.A. Binary tree for clustering of regulatory signals // Proc. 4th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2004). — Novosibirsk, Russia, 2004. Vol. 1. P.195-199.

9. Stavrovskaya E.D., Mironov A.A. Binary tree for clustering of regulatory signals. // Proc. International conference BITS'2005. — Milan, Italy, 2005. P. 85.

10. Ставровская Е.Д., Миронов A.A. ClusterTree: программа кластеризации регуляторных сигналов с помощью бинарного дерева // Материалы XII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов». — Москва, Россия, 2005. С. 36-37.

11. Stavrovskaya E.D., Makeev V.J., Mironov A.A. ClusterTree-RS: The binary tree algorithm for identification of co-regulated genes by clustering regulatory signals // Proc. Moscow Conference on Computational Molecular Biology (MCCMB'05). — Moscow, Russia, 2005. P. 385.

12. Stavrovskaya E.D., Makeev V.J., Merkeev I.V., Mironov A.A. Tool for automatic aetection of co-regulated genes. // Proc. 5'th European Conference on Computational Biology (ECCB'2006). — Eilat, Israel, 2007.

13. Stavrovskaya E.D., Makeev V.J., Merkeev I.V., Mironov A.A. Tool for automatics detection of co-regulated genes // Proc. 5th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2006). —Novosibirsk, Russia, 2006. Vol.1.

P.172-175.

14. Stavrovskaya E.D., Cipriano M., Dubchak I.L., Mironov A.A., Gelfand M.S. Automated search for regulatory motifs in upstream regions of genes from the functional subsystems // Proc. Moscow Conference on Computational Molecular Biology (MCCMB'07). — Moscow, Russia, 2007. P. 283.

15. Ставровская Е.Д., Сиприано M., Дубчак И.JI., Миронов А.А., Гельфанд М.С. Автоматический поиск регуляторных сигналов перед генами в рамках функциональных подсистем. // Труды конференции Информационные технологии и системы (ИТиС'07). — Звенигород, Россия, 2007. С. 330-331.

Библиография Диссертация по биологии, кандидата физико-математических наук, Ставровская, Елена Дмитриевна, Москва

1. Bailey Т. L., Elkan С. Fitting a mixture model by expectation maximization to discover motifs in biopolymers // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 1994. — Vol. 2. — P. 28-36.

2. Bailey T. L., Elkan C. The value of prior knowledge in discovering motifs with MEME // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 1995. — Vol. 3. — P. 21-29.

3. Bailey T. L., Elkan C. Unsupervised learning of multiple motifs in biopolymers using expectation maximization // Machine Learning J. — 1995. — Vol. 21. — P. 51-83.

4. Berg O.G., von Hippel P.H. Selection of DNA binding sites by regulatory proteins: Ststistical-mechanical theory and application to operators and promoters // J. Mol. Biol. — 1987. — Vol. 193(4) . — P. 723-750.

5. Buhler J., Tompa M. Finding motifs using random projections // J Comput Biol. — 2002.1. Vol. 9(2). — P. 225-42.

6. Bulyk M. L. Computational prediction of transcription-factor binding site locations // Genome Biol. — 2003. — Vol. 5(1). — P. 201.

7. Bulyk M. L., Gentalen E., Lockhart D. J., Church G. M. Quantifying DNA-protein interactions by double-stranded DNA arrays // Nat Biotechnol. — 1999. — Vol. 17(6).1. P. 573-577.

8. Bulyk M. L., Huang X., Choo Y., Church G. M. Exploring the DNA-binding specificitics of zinc fingers with DNA microarrays // Proc. Natl. Acad. Sci. USA. — 2001. — Vol. 98(13).— P. 7158-7163.

9. Cardon L. R., Stormo G. D. Expectation maximization algorithm for identifying protein-binding sites with variable lengths from unaligned DNA fragments // J. Mol. Biol. — 1992,— Vol. 223(1).— P. 159-170.

10. Danilova L.V., Lyubetsky V.A., Gelfand M.S. An algorithm for identification of regulatory signals in unaligned DNA sequences, its testing and parallel implementation // In Silico Biol. — 2003,— Vol. 3(1-2).— P. 33-47.

11. Eskin E., P. Pevzner A. Finding composite regulatory patterns in DNA sequences // Bioinformatics. — 2002. — Vol. 18. Suppl 1. — P. S354-63.

12. Fraenkel Y. M., Mandel Y., Friedberg D., Margalit H. Identification of common motifs in unaligned DNA sequences: application to Escherichia coli Lrp regulon // Comput. Appl. Biosci.— 1995,— Vol. 11(4).— P. 379-387.

13. Freeh K., Herrmann G., Werner T. Computer-assisted prediction, classification, and delimitation of protein binding sites in nucleic acids // Nucleic Acids Res. — 1993. — Vol. 21(7).— P. 1655-1664.

14. Frishman D., Mironov A., Gelfand M. Starts of bacterial genes: estimating the reliability of computer predictions // Gene. — 1999. — Vol. 234(2) . — P. 257-65.

15. Gelfand M. S., Koonin E. V., Mironov A. A. Prediction of transcription regulatory sites in Archaea by a comparative genomic approach // Nucleic Acids Res. — 2000. — Vol. 28(3) . — P. 695-705.

16. Geman S., Geman D. Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1984. — Vol. 6,— P. 621-641.

17. Gold L., Brown D., He Y., Shtatland T., Singer B. S., Wu Y. From oligonucleotide shapes to genomic SELEX: novel biological regulatory loops // Proc. Natl. Acad. Sci. USA. — 1997. — Vol. 94(1) . — P. 59-64.

18. Grundy W. N., Bailey T. L., Elkan C. P. ParaMEME: a parallel implementation and a web interface for a DNA and protein motif discovery tool // Comput Appl Biosci. — 1996. — Vol. 12(4).— P. 303-310.

19. Gurkiewicz M., Korngreen A. Free in PMC A numerical approach to ion channel modelling using whole-cell voltage-clamp recordings and a genetic algorithm // PLoS Comput. Biol. — 2007. — Vol. 3(8). — P. 169.

20. Hartigan J. A., Wong M. A. A K-means clustering algorithm // Applied Statistics. — 1979.— Vol. 28(1).— P. 100-108.

21. Hertz G. Z., Stormo G. D. Identifying DNA and protein patterns with statistically significant alignments of multiple sequences // Bioinformatics. — 1999. — Vol. 15(7-8) .1. P. 563-577.

22. Hertz G. Z., Hartzell G. W. 3rd, Stormo G. D. Identification of consensus patterns in unaligned DNA sequences known to be functionally related // Comput. Appl. Biosci. — 1990. — Vol. 6(2). — P. 81-92.

23. Horak C. E., Mahajan M. C., Luscombe N. M., Gerstein M., Weissman S. M., Snyder M. GATA-1 binding sites mapped in the beta-globin locus by using mammalian chip-chip analysis // Proc. Natl. Acad. Sci.U S A. — 2002. — Vol. 99(5). — P. 2924-2929.

24. Hsieh S.Y., Tseng C.L., Lee Y.S., Kuo A.J., Sun C.F., Lin Y.H., Chen J.K. Abstract Highly efficient classification and identification of human pathogenic bacteria by MALDI-TOF MS // Mol. Cell. Proteomics. — 2008. — Vol. 7(2) . — P. 448-56.

25. Hu Y. J., Sandmeyer S., McLaughlin C., Kibler D. Combinatorial motif analysis and hypothesis generation on a genomic scale // Bioinformatics. — 2000. — Vol. 16(3). — P. 222-32.

26. Hubert L. Approximate Evaluation Techniques for the Single-Link and Complete-Link Hierarchical Clustering Procedures // Journal of the American Statistical Association. — 1974. — Vol. 69(347). — P. 698-704.

27. Hughes J.D., Estep P.W., Tavazoie S., Church G.M. Computational identification of cis-regulatory elements associated with groups of functionally related genes in Saccharomyces cerevisiae//J. Mol. Biol. — 2000. — Vol. 296(5) . — P. 1205-1214.

28. Iyer V. R., Horak C. E., Scafe C. S., Botstein D., Snyder M., Brown P. O. Genomic binding sites of the yeast cell-cycle transcription factors SBF and MBF.// Nature. 2001. Vol. 409(6819). P. 533-538.

29. Jain A.K., Murty M.N., Flynn P.J. Data Clustering: A Review.// ACM Computing Surveys (CSUR). 1999. Vol. 31(3). P. 264-323.

30. Jensen L. J., Knudsen S. Automatic discovery of regulatory patterns in promoter regions based on whole cell expression data and functional annotation // Bioinformatics. — 2000. — Vol. 16(4).— P. 326-333.

31. Johnson DS, Mortazavi A, Myers RM, Wold B. Genome-wide mapping of in vivo proteinDNA interactions // Science. — 2007. — Vol. 316(5830). — P. 1497-1502

32. Jonassen I. Efficient discovery of conserved patterns using a pattern graph // Comput. Appl. Biosci. — 1997. — Vol. 13(5). — P. 509-522.

33. Kel-Margoulis O.V., Ivanova T.G., Wingender E., Kel A.E. Automatic annotation of genomic regulatory sequences by searching for composite clusters // Pac. Symp. Biocomput.— 2002,— P. 187-198.

34. Kielbasa S. M., Korbel J. O., Beule D., Schuchhardt J., Herzel H. Combining frequency and positional information to predict transcription factor binding sites // Bioinformatics. —2001,— Vol. 17(11).— P. 1019-1026.

35. Kullback S. Information theory and statistics // Mineola, N.Y., Dover Publications. ■— 1997.

36. Lawrence C. E., Reilly A. A. An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences // Proteins. — 1990. — Vol. 7(1) . — P. 41-51.

37. Lawrencc C. E., Altschul S. F., Boguski M. S., Liu J. S., Neuwald A. F., Wootton J. C. Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment // Science. — 1993,— Vol. 262(5131) . — P. 208-214.

38. Lee H.G., Lee H.S., Jeon S.H., Chung T.H., Lim Y.S., Huh W.K. High-resolution analysis of condition-specific regulatory modules in Saccharomyces cerevisiae // Genome Biol. — 2008. — Vol. 9. — P. R2.

39. Lee Z.J. An integrated algorithm for gene selection and classification applied to microarray data of ovarian cancer // Artif. Intell. Med. — 2008. — Vol. 42(1) . — P. 81-93.

40. Liu X., Brutlag D. L., Liu J. S. BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes // Pac. Symp. Biocomput. — 2001. — P. 127-138.

41. Liuni S., Prunella N., Pesole G., D'Orazio T., Stella E., Distante A. SIMD parallelization of the WORDUP algorithm for detecting statistically significant patterns in DNA sequences // Comput. Appl. Biosci. — 1993. — Vol. 9(6). — P. 701-707. •

42. Lukashin A. V., Engelbrccht J., Brunak S. Multiple alignment using simulated annealing: branch point definition in human mRNA splicing // Nucleic Acids Res. — 1992. — Vol. 20(10).— P. 2511-2516.

43. Makita Y., Nakao M., Ogasawara N., Nakai K. DBTBS: database of transcriptional regulation in Bacillus subtilis and its contribution to comparative genomics // Nucleic Acids Res. — 2004. — Vol. 32. — P. 75-77.

44. Marsan L., Sagot M. F. Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification // J. Comput. Biol.2000. — Vol. 7(3-4) . — P. 345-62.

45. McClure W.R. Mechanism and control of trancription initiation in prokaryotes // Ann. Rev. Biochem.— 1985.— Vol.54. — P. 171-204.

46. Merkeev I.V., Novichkov P.S., Mironov A.A. PHOG: a database of supergenomes built from proteome complements // BMC Evol. Biol. — 2006. — Vol. 22. — P. 6-52.

47. Metropolis N., Rosenbluth M.N., Teller A.H., Teller E. Equations of state calculations by fast computing machines// J. Chem. Phys.— 1953.— Vol.21. — P. 1087-1092.

48. Mironov A.A., Vinokurova N.P., Gel'falnd M.S. Software for analyzing bacterial genomes // Mol. Biol. (Mosk) . — 2000. — Vol. 34(2) . — P. 253-262.

49. Overbeek R. et al. The Subsystems Approach to Genome Annotation and its Use in the Project to Annotate 1000 Genomes // Nucleic Acids Research. — 2005. — Vol. 33(17). — P. 5691-5702.

50. Pesole G., Prunella N., Liuni S., Attimonelli M., Saccone C. WORDUP: an efficient algorithm for discovering statistically significant patterns in DNA sequences // Nucleic Acids Res.— 1992.— Vol. 20(11).— P. 2871-2875.

51. Pevzner P. A., Sze S. H. Combinatorial approaches to finding subtle signals in DNA sequences // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 2000. — Vol. 8. — P. 269-278.

52. Prasad P.A., Kanagasabai V., Arunachalam J., Gautham N. Exploring conformational space using a mean field technique with MOLS sampling // J. Biosci. — 2007. — Vol. 32(5). — P. 909-920.

53. Qin Z.S., McCue L.A., Thompson W., Mayerhofer L., Lawrence C.E., Liu J.S. Identification of co-regulated genes through Bayesian clustering of predicted regulatory binding sites // Nat Biotechnol. — 2003. — Vol. 21(4) . — P. 435-439.

54. Quandt K., Freeh K., Karas H., Wingender E., Werner T. Matlnd and Matlnspector: new fast and versatile tools for detection of consensus matches in nucleotide sequence data // Nucleic Acids Res. — 1995.— Vol. 23(23) . — 4878-4884.

55. Reid J. L., Iyer V. R., Brown P. O., Struhl K. Coordinate regulation of yeast ribosomal protein genes is associated with targeted recruitment of Esal histone acetylase // Mol. Cell. — 2000. — Vol. 6(6) . — P. 1297-1307.

56. Ren B., Cam H., Takahashi Y., Volkert T., Terragni J., Young R. A., Dynlacht B. D. E2F integrates cell cycle progression with DNA repair, replication, and G(2)/M checkpoints // Genes Dev. — 2002. — Vol. 16(2) . — P. 245-256.

57. Rigoutsos I., Floratos A. Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm // Bioinformatics. — 1998. — Vol. 14(1) . — P. 55-67.

58. Robison K., McGuire A.M., Church G.M. A comprehensive library of DNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K-12 genome // J. Mol. Biol.— 1998.— Vol. 284(2).— P. 241-254.

59. Rocke E., Tompa M. An algorithm for finding novel gapped motifs in DNA sequences // Proceedings of the second annual international conference on Computational molecular biology RECOMB '98. — 1998. — P. 228-233.

60. Rodionov D.A., Gelfand M.S. Identification of a bacterial regulatory system for ribonucleotide reductases by phylogenetic profiling // Trends Genet. — 2005. — Vol. 21(7).— P. 385-389.

61. Rosenbluth J.M., Mays D.J., Pino M.F., Tang L.J., Pietenpol J.A. A Gene Signature-Based Approach Identifies mTOR as a Regulator of p73 // Molecular and Cellular Biology. — 2008. — Vol. 28(19) . — P. 5951-5964.

62. Roth F. P., Hughes J. D., Estep P. W., Church G. M. Finding DNA regulatory motifs within unaligned noncoding sequences clustered by whole-genome mRNA quantitation // Nat. Biotechnol. — 1998.— Vol. 16(10).— P. 939-945.

63. Rouchka E.C. A Brief Overview of Gibbs Sampling // Washington University Institute for Biomedical Computing Statistics Study Group. — 1997.

64. Sattath S., Tversky A. Additive similarity trees // Psychometrika. — 1977. — Vol. 42(3) .1. P. 19-345.

65. Schujman G.E., Paoletti L., Grossman A.D., de Mendoza D. FapR, a bacterial transcription factor involved in global regulation of membrane lipid biosynthesis // Dev. Cell. — 2003.1. Vol. 4(5) . — P. 663-672.

66. Shannon C. E., Weaver W. The mathematical theory of communication // Urbana, University of Illinois Press. — 1949.

67. Stormo G. D., Hartzell G. W. 3rd. Identifying protein-binding sites from unaligned DNA fragments // Proc. Natl. Acad. Sci. USA.— 1989. — Vol. 86(4). — P. 1183-1187.

68. Stormo G. D. DNA binding sites: representation and discovery // Bioinformatics . — 2000 .— Vol. 16(1).— P. 16-23.

69. Tatusov R.L., Koonin E.V., Lipman D.J. A genomic perspective on protein families // Science.— 1997.— Vol. 278(5338) . — P. 631-637.

70. Thijs G., Marchal K., Lescot M., Rombauts S., De Moor B., Rouze P., Moreau Y. A Gibbs sampling method to detect overrepresented motifs in the upstream regions of coexpressed genes.// J Comput Biol. 2002. Vol. 9(2). P. 447-464.

71. Tompa M. An exact method for finding short motifs in sequences, with application to the ribosome binding site problem // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 1999. — P. 262-271.

72. Tompa R., McCallum C. M., Delrow J., Henikoff J. G., van Steensel B., Henikoff S. Genome-wide profiling of DNA methylation reveals transposon targets of CHROMOMETHYLASE3 // Curr. Biol. — 2002. — Vol. 12(1). — P. 65-68.

73. Vinogradov D.V., Mironov A.A. SiteProb: yet another algorithm to find regulatory signals in nucleotide sequences // Proceedings of the third international conference BGRS'2002. — 2002. — Vol. 1. — P. 30-32.

74. Wade J.T., Struhl K., Busby S.J., Grainger D.C. Genomic analysis of protein-DNA interactions in bacteria: insights into transcription and chromosome organization // Mol. Microbiol. — 2007. — Vol. 65(1). — P. 21-26.

75. Waterman M. S. Multiple sequence alignment by consensus // Nucleic Acids Res. — 1986,— Vol. 14(22) . — P. 9095-9102.

76. Weinmann A. S., Yan P. S., Oberley M. J., Huang T. H., Farnham P. J. Isolating human transcription factor targets by coupling chromatin immunoprecipitation and CpG island microarray analysis // Genes Dev. — 2002. — Vol. 16(2) . — P. 235-244.

77. Wolfertstetter F., Freeh K., Herrmann G., Werner T. Identification of functional elements in unaligned nucleic acid sequences by a novel tuple search algorithm // Comput. Appl. Biosci.— 1996,— Vol.— 12(1).— P. 71-80.

78. Wolfsberg T. G., Gabrielian A. E., Campbell M. J., Cho R. J., Spouge J. L., Landsman D. Candidate regulatory sequence elements for cell cycle-dependent transcription in Saccharomyces cerevisiae // Genome Res. — 1999. — Vol. 9(8) . — P. 775-792.

79. Wyrick J. J., Young R. A. Deciphering gene expression regulatory networks // Curr. Opin. Genet. Dev. — 2002,— Vol. 12(2).— P. 130-136.

80. Xu X., Wang L., Ding D. Learning module networks from genome-wide location and expression data // FEBS Lett. — 2004. — Vol. 578(3). — P. 297-304.

81. Zhang H., Switzer R.L. Transcriptional pausing in the Bacillus subtilis pyr operon in vitro: a role in transcriptional attenuation? // J. Bacteriol. — 2003. — Vol. 185(16) . — P. 4764-4771.

82. Миронов А. А., Гельфанд М.С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах // Молекулярная Биология (Москва) . — 1999. — 33(5) . — С. 772-778.