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

Поиск участков специфического связывания белков-регуляторов транскрипции с ДНК методом Монте-Карло Марковскими цепями

ВАК РФ 03.00.02, Биофизика

Автореферат диссертации по теме "Поиск участков специфического связывания белков-регуляторов транскрипции с ДНК методом Монте-Карло Марковскими цепями"

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

УДК 533.9

Фаворов Александр Владимирович

Поиск участков специфического связывания белков • регуляторов транскрипции с ДНК методом Монте-Карло Марковскими цепями

АВТОРЕФЕРАТ

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

03.00.02. - биофизика

Москва 2005

Работа выполнена в лаборатории Биоинформатики Государственного исследовательского института генетики и селекции промышленных микроорганизмов «Генетика».

научно-ГосНИИ

Научный руководитель:

кандидат физико-математических наук, Макеев Всеволод Юрьевич

Официальные оппоненты:

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

Ведущая организация: Институт теоретической и экспериментальной биофизики РАН (Пущино)

Защита диссертации состоится 17 ноября 2005 г. в 10 часов на заседании Диссертационного совета К 212.156.03 при Московском физико-техническом институте (141700, Московская обл., г. Долгопрудный, Институтский пер. 9, МФТИ).

С диссертацией можно ознакомиться в библиотеке МФТИ.

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

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

кандидат физико-математических наук

В.Е. Брагин

ел

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

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

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

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

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

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

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

Цель и задачи исследования

Целями настоящей работы являлись'

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

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

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

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

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

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

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

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

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

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

Всё вышесказанное составляет практическую значимость работы.

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

Результаты работы представлялись на международных конференциях: 3-я конференция "Bioinformatics of Genome Regulation and Structure" (BGRS, Новосибирск, 2002); 1-я конференция "Moscow Conference on Computational Molecular Biology" (MCCMB, Москва, 2003); 4-я конференция "Bioinformatics of Genome Regulation and Structure" (BGRS, Новосибирск, 2004), а так же на научных семинарах в лаборатории биоинформатики ФГУП ГосНИИГенетика, Москва, Россия и в Bioinformatics Department of Boston University, Boston, Massachusetts, USA.

По материалам диссертации опубликовано 8 печатных работ, из них 5 - в реферируемых журналах.

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

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

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

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

Глав» III посвящена сравнению программного обеспечения SeSiMCMC с другими, аналогичными программными инструментами Описан протокол тестирования и приведены ею результаты.

Глава IV посвящена идентификации дивергентных, а поэтому трудных для вычислительной идентификации, сайтов связывания регуляторов АгсА-Р и NarP, включённых в регуляцию дыхания Escherichia coli Описана процедура идентификации сайтов. Предложено описание соответствующих регулонов в геномах четырёх гамма-протеобактерий- Escherichia coli, Yersinia pestis, Pasteurela multocida и Vibrio vulnificus с помощью методов сравнительной геномики.

Список литературы, приведённый в конце диссертации, включает 126 наименований. Работа содержит семь рисунков и четыре таблицы.

Содержание работы

ГЛАВА 1. Биологические задачи: методологические различия физического и вычислительного модельных подходов

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

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

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

Строя модель интересующего нас предмета, мы можем ждать или не ждать от неё соответствия имени моделируемого предмета Это, казалось бы, малосущественное, различие в подходах (в конце концов, от модели ждут адекватности поставленной задаче, а не семантической идеальности) существенным образом определяет парадигму моделирования. Мы будем говорить о более или менее идеальных моделях, имея в виду степень соответствия модели имени моделируемого объекта.

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

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

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

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

Существующие модели ДНК-белкового связывания различаются представлением сайта связывания, и способом его поиска в выборке последовательностей. Модель, используемая семейством алгоритмов «Gibbs Sampler», близка к идеальной в аспекте "стохастического

узнавания". Белок-регулятор, в соответствие с моделью Берга и фон Хиппеля, находится в динамическом равновесии трёх состояний: свободного, неспецифично связанного с нитью ДНК и специфично связанного с нитью ДНК Переход из первого состояния происходит из-за того, что молекула белка в процессе трёхмерной диффузии встречает нить ДНК. Из второго белок отрывается от нити в свободное состояние или находит в процессе одномерной диффузии вдоль нити сайт связывания и переходит в третье. Из третьего (специфически связного) молекула может оторваться или сместится по нити, переходя соответственно в первое или второе состояния. Используемый в ЗеЭ^МСМС при поиске мотива поочерёдный стохастический пересмотр присутствия и позиций сайта в каждой рассматриваемой последовательности по смыслу во многом сходен с описанной моделью трёх состояний. Сам механизм узнавания белком участка ДНК, естественно, моделируется по возможности адекватно, что подтверждается тем, чю хотя бы некоторые результаты работы алгоритма биологически осмысленны, но неидеально, и результат применения модели требует верификации.

ГЛАВА 2. Алгоритм поиска и определения длины и структуры консервативных участков ДНК, программная реализация

Чтобы разработать специализированный инструмент для нахождения слабых мотивов с промежутками неизвестной длины, использующий имеющиеся предположения о струк1уре мотива, мы предложили вероятностную модель и процедуру оптимизации, развивающие классический алгоритм «Gibbs Sampler» Такой специализированный инструмент может более адекватно, чем универсальный алгоритм, решать эту конкретную задачу Были сформулированы две вероятностные модели: фона и сигнала (мотива). Мотив представлялся позиционно-вероятностной матрицей. Фон моделировался независимой последовательноегью символов с фиксированными вероятностями появления нуклеотидов Оптимальной разметкой считалась наиболее вероятная в байесовском смысле разметка, при условии данных последовательностей ДНК.

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

Вероятности q(i,r) появления нуклеотида г в позиции мотива /', i = l..s, где i - это

длина сайта, и фоновые вероятности нуклеотидов /(г), оцениваются, исходя из внутримотивных и внемотивных (фоновых) счетчиков, обозначаемых с(/,г) и g(r),

9(l>)=£M±Hd

чк ' м + в

(2.1)

и

(2.2)

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

В = ^Ь(г)~4м, (2.3)

г

где N - это число входных последовательное гей

Для мотивов, которые предполагаются (нестрого) симметричными, априорное предпочтение определённой симметрии выражается в формуле q(i,r). Для прямых повторов она представлена как

c(i,r) + c{i + int f + 2 b(r)

=-*-, г -, (2.4)

чк ' 2 (М + В) У '

а для палиндромов (обратных повторов) — как:

ah А- с0'г) + Ф + х-{>г) + Чг) + Ь(г)

ЧК ' ' 2 (М + В) ' К ' '

где s - длина мотива иг — это нуклеотид, комплементарный г.

Основная процедура поиска набора сходных сайтов следующая. Работа алгоритма начинается со случайно расположенных сайтов определенной длины, по одному на последовательность. Затем организуется цикл поочередных уточнений позиций сайтов. На каждом шаге выбирается одна (текущая) последовательность. Для однообразия мы рассматриваем отсутствие сайта последовательности как особую позицию сайта (нулевую). На каждом щаге мы подсчитываем нуклеотиды во всех позициях внутри сайта и дня фона по всем последовательностям, кроме текущей. Мы оцениваем позиционные вероятности нуклеотидов внутри мотава по формулам (2.1), (2.3), (2.4) и фоновые вероятности по формуле (2.2). Для каждой выбранной последовательности Rвероятность (правдоподобие) получить текущую последовательность бернуллиевским процессом в предположении, что сайт расположен в позиции к вычисляется по формуле:

(2.6)

Г(* 1[о])=П/(1)= 1-1

где г, — это /-ый нуклеотид в последовательности Я, а [£], к = \..(Ь-,$ +1) обозначают событие: «сайт начинается с позиции к », [0] соответствует случаю отсутствия сайта (нулевая позиция). Априорная вероятность /*([0]) определяется пользователем и обозначает

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

Усреднённая по моделям вероятность самой последовательности (evidence).

/-.1+1

P(RW,/)= £ />(Rl[fc],/)■/>([*]). (2.8)

к-О

Апостериорная вероятность того, что сайт начинается в позиции к :

U Л >4'JJ P(R|it/)

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

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

№

(2.10)

Теперь счетчики с (г, г) и параметры модели д(',г) и /(г) оцениваются по всем последовательностям. Формула (2.10) оьчичается от стандартной кульбаковской энтропии тем, что мы используем с (г, г) как множитель, а <](1,г) — как аргумент логарифма. Расстояния между оцененным распределением вероятностей символов в выравнивании ?(/,>•) (которые содержат псевдокаунты) и фоновым распределением f (г) рассчитывается исходя из наблюдаемых данных с(},г). В стандартной же кульбаковской энтропийной мере присутствуют два распределения и нет наблюдаемых данных. В этой ситуации ч(1,г) участвовал бы в формуле и как множитель и как аргумент логарифма Заметим, что константа М в знаменателе уравнения (2.12), приведенного ниже, дает правильную нормализацию величины энтропийного расстояния.

Пространственный компонент - это расстояние между распределением апостериорных вероятностей позиций сайтов в последовательности (включая нулевую позицию) при известной вероятности модели сайта и априорным распределением вероятностей позиций сайтов:

Ис{кфюк«} к-0 ^ ги*Л/ )

= 2 + , (2.11) Ис{к<111епс«) "(,К7 О

где [&]„ означает событие, что сайт наблюдается в позиции к последовательности Я, ¿л — это длина последовательности, а обозначения и / такие же, как в уравнении (2.6).

Таким образом, значение ИСП равно:

^ 5-М )

где обозначения л- и М такие же, как в уравнениях (2.1)-(2.5).

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

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

Такая процедура уточнения аналогична приведенной Лоуренсом (Lawrence, Altschul et al. 1993), но отличается от нее следующим образом Вычисление информационною содержания по уравнению (2.12) содержит уточненную формулу для пространственного компонента Каждый этап уточнения используется также для оценки оптимальной длины мотива и длины промежутка, если разрешены разделенные мотивы Для каждой длины мотива длина промежутка принимается как минимальное значение, для которого достигается локальный максимум ИСП. Поскольку длина промежутка может оказаться нулевой, эта же процедура определяет, разделен мотив или нет.

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

Рисунок 1. Блок - схема работы алгоритма 8е81МСМС

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

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

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

Программное обеспечение SeSiMCMC написано на языке С++ (gcc 3.x). Исполняемые файлы для FreeBSD и консоли Win32 доступны на сайте проекта http://bioinform genetica ru/SeSiMCMC На этой же странице находится форма веб-интерфейса к этому программному обеспечению Все параметры в ней, кроме обязательной для ввода выборки последовательностей ДНК, по умолчанию установлены в "универсально-разумные" значениия.

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

ГЛАВА 3. Сравнение программы 8е81МСМС с аналогичными

Программное обеспечение 8е5)'МСМС сравнивалось с двенадцатью другими программами для предсказания мотивов, также доступными через Интернет. Сравнение производилось на специально подготовленных выборках данных. Сайты связывания ТФ, их позиции и ориентации в последовательностях брались из базы данных П1А№РАС (http://transfac.gbf-braunschweiji.de/TRANSFАСА. Каждый ТФ был основой для одной выборки входных данных Каждая выборка организовывалась из одного из трёх типов фоновых последовательностей, в который сайты из "ША^РАС встраивались в их позиции и в правильной ориентации Эти три типа - реальные промоторы, в которых расположены сайты, случайные промоторы из того же генома, и, наконец, случайные последовательности, порождённые Марковской моделью. Всего было 52 набора данных с сайтами из четырех биологических видов - человека, мыши, мухи и дрожжей. На рисунке 2 приведены результаты

ТР ■ ТМ-РМ ■ РР

сравнения коэффициента корреляции • СС = г , где все

фтр++РР)(ТР+РР)<ты+ёк)

числа правильных предсказаний (ТР), правильных не-предсказаний (ТЫ), неправильных предсказаний (РР) и неправильных не-предсказаний (РЫ) - приведены в позициях (основаниях) последовательностей, для всех 13 программ, участвовавших в тесте.

Рисунок 2. Сравнение коэффициентов корреляции идентифицированных и исходных наборов сайтов для SeSiMCMC и 12 других программ. Fly - сайты мухи; human - человека; mouse - мыши; yeast - дрожжей; all data - общие результаты.

ГЛАВА 4. Применение алгоритма для поиска участков связывания белков -регуляторов дыхания АгсА и NarP на ДНК в бактерии Е. coli и описания соответствующих регулонов

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

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

Система АгсА регулирует экспрессию ряда генов в ответ на изменения аэробных/анаэробных условий окружающей среды. В качестве входных данных был взят набор регуляторных участков генов, для которых из различных источников было показано, что они регулируются системой АгсА. Программа SeSiMCMC запускалась для этой обучающей выборки последовательностей с различными параметрами для поиска: (1) произвольного мотива, (2) мотива с симметричным спейсером посередине, (3) прямого повтора, возможно, с симметричным спейсером и (4) палиндрома (встречного комплементарного повтора), возможно, с симметричным промежутком (спейсером). Сайты искались на обеих нитях ДНК. Длина сайта могла быть между 6 и 22 основаниями.

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

Рисунок 3. Варианты мотива ССТФ ArcA-Р Лого последовательности для ССТФ NarP, полученное из сайтов в последовательностях обучающей выборки, а. найдепных программой SeSiMCMC b.. приведенный по http.Z/arep.med harvard edu/ecoli matrices/dat/arcA.dat. По горизонтальной оси: позиция в консенсусе, по • горизонтальной - информационное содержание этой позиции в наборе сходных участков. Высота буквы в позиции показывает её предпочтительность в этой позиции Лого создано программой WebLogo http://weblogo.berkelev.edu/

Высокая селективность полученного мотива позволила использовать его в исследовании регулона ArcA-Р в геномах четырёх гамма-протеобактерий: Escherichia coli, Yersinia pestis, Pasteurela multocida и Vibrio vulnificus методами сравнительной геномики. На основе всех сайтов, определённых программой как образующих мотив, было построено распознающее правило, которое позволило выявить ряд новых потенциально АгсА-регулируемых генов в гамма-протеобактериях, большинство их которых упоминаются в литературе как значимые для дыхательно-зависимой регуляции.

Проверим гипотезу, что наше правило работает некорректно, а результат был получен случайно. Всего в полном геноме Е coli 4404 генов. Из найденых нами 23 генов, 14 описаны в литературе как регулируемые в зависимости от концентрации кислорода. Используя завышенную оценку числа всех кислородзависимо регулируемых генов Е coli, равную 500, и применяя критерий Фишера к четырёхпольной таблице: «14 9 // 500 3904», получаем

1-

сн

5'

3'

Рисунок 4. Лого последовательности для ССТФ NarP, полученное из набора сходных участков последовательностей обучающей выборки, найденных программой SeSiMCMC. По горизонтальной оси: позиция в консенсусе, по горизонтальной - информационное содержание этой позиции в наборе сходных участков. Высота буквы в позиции показывает её предпочтительность в этой позиции. Лого создано программой WebLogo http://weblogo.berkelev.edu/

достоверность нулевой гипотезы, примерно равную 2x10"7. Уменьшение оценки числа кислородзависимо регулируемых генов приводит к дальнейшему уменьшению достоверности нулевой гипотезы. Девять обнаруженных генов, не найденных в литературе, можно рассматривать как новые потенциальные гены регулона АгсА.

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

Обучающая выборка для поиска ССТФ NarP состояла из 16 областей, лежащих в 5'-яаправпении от тех оперонов в геноме Е coli, для которых регуляция NarP была ранее извесгна. Программа SeSiMCMC запускалась на этой выборке с различными параметрами. Идентификация сайта связывания NarP оказалась более трудной задачей, чем поиск сайта АгсА-Р. Сходный участок в последовательностях нашёлся, только когда длина возможного мотива была ограничена сверху и снизу 10 и 20 основаниями, а стартовая длина задана равной 16 (то есть известной из литературы). Априорная вероятность отсутствия сигнала в последовательности была взята равной 0,5. При этих параметрах, программа нашла в исходных данных мотив с характеристиками предполагаемого консенсуса NarP (см. рис. 4)

Как и для АгсА, полученный набор сайтов был использован для построения распознающего правила с помощью методов сравнительной геномики. Мы верифицировали сигнал и нашли новых потенциальных членов регулона NarP в геномах четырёх бактерий : Escherichia coli, Yersinia pestis, Pasteurela multocida and Vibrio vulnificus. В частности, была предсказана регуляция фактором NarP для пяти оперонов из обучающей выборки, для которых ранее была показана только регуляция NarL. Сайты - кандидаты NarP были также найдены у пяти новых (ранее не включавшихся в регулон NarP ) оперонов, три из которых ранее упоминались в литературе как регулируемые нитрит- или нитрат-зависимо.

Выводы

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

2. Получены формулы для выражения информационного содержания коллекции участков (сайтов) связывания конкретного белка в наборе последовательностей ДНК.

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

4. Создано программное обеспечение SeSiMCMC с интерфейсом командной строки, реализующее алгоритм, описанный в пункте (3) и открытый веб-интерфейс обращения к этому программному обеспечению.

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

6. С помощью программы SeSiMCMC были найдены дивергентные и поэтому трудные для алгоритмического обнаружения мотивы сайтов связывания двух регуляторов дыхания в Escherichia coli, а именно АгсА-Р и NarP На основании этих мотивов было сделано первичное описание соответствующих регулонов.

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

1 Favorov, А. V, М. S. Gelfand, A A Mironov, V J. Makeev (2002). Yet Another Digging For DNA Motifs Gibbs Sampler. Proceedings of BGRS'2002, Novosibisk, 1: 31-33

2 Favorov. A. V , A. V. Gerasimova, V. J. Makeev (2003). Yet Another Digging-For-DNA-Motifs Gibbs Sampler. MCCMB'2003 Proceedings, Moscow. 67-70.

3 Герасимова, А. В, M С Гельфанд, В. Ю. Макеев, А А. Миронов, А. В. Фаворов (2003) "Первичное описание регулона Area в геномах 1амма-протеобактерий на основе вычислительного распознавания участка связывания белка-регулятора." Биофизика 48(Приложение 1): 21-25.

4. Фаворов, А. В. (2004). "Методологические различия физического и вычислительного модельных подходов." Биофизика 49(5): 958-960.

5. Favorov, А. V., М. S. Gelfand, А. V. Gerasimova, A. A. Mironov, V. J. Makeev (2004). Gibbs Sampler for Identification of Symmetrically Structured, Spaced DNA Motifs With Improved Estimation of the Signal Length and Its Validation on the ArcA Binding Sites. Proceedings of BGRS'2004, Novosibisk, 2: 269-272.

6. Tompa, M., N. Li, T. L. Bailey, G. M. Church, B. De Moor, E. Eskin, A. V. Favorov, M. C. Frith, Y. Fu, W. J. Kent, V. J. Makeev, A. A. Mironov, W. S. Noble, G. Pavesi, G. Pesole, M. Regnier, N. Simonis, S. Sinha, G. Thijs, J. van Helden, M. Vandenbogaert, Z. Weng, C. Workman, C. Ye, Z. Zhu (2005). "Assessing computational tools for the discovery of transcription factor binding sites." Nat Biotechnol 23(1): 137-44.

7. Favorov, A. V., M. S. Gelfand, A. V. Gerasimova, D. A. Ravcheev, A. A. Mironov, V. J. Makeev (2005). "A Gibbs sampler for identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length." Bioinformatics 21(10): 2240-2245.

8. Favorov, A. V., Т. V. Andreewski, M. A. Sudomoina, О. O. Favorova, G. Parmigiani, M. F. Ochs (2005). A Markov Chain Monte Carlo Technique for Identification of Combinations of Allelic Variants Underlying Complex Diseases. Genetics Aug 2005, doi: 10.1534/genetics.l05.048090

I'

»

I

»

Отпечатано в типографии ООО «Г'ипрософт» г Москва, Ленинский пр-т, Д.37А Тираж 100 экз.

»19034

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

2006-4 17364

Содержание диссертации, кандидата физико-математических наук, Фаворов, Александр Владимирович

ОГЛАВЛЕНИЕ.

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

Цель и задачи исследования.

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

Публикации.

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

Объем и структура диссертации.

Введение Диссертация по биологии, на тему "Поиск участков специфического связывания белков-регуляторов транскрипции с ДНК методом Монте-Карло Марковскими цепями"

Экспериментальные методы нахождения ССТФ.11

Поиск сайтов связывания транскрипционных факторов хп яШсо.12

Описания мотива и оценки его качества.12

Матрица позиционных весов.13

Различные типы алгоритмов для поиска мотивов.15

Описание нескольких наиболее известных алгоритмов поиска мотивов.18

Заключение Диссертация по теме "Биофизика", Фаворов, Александр Владимирович

выводы

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

2. Получены формулы для выражения информационного содержания коллекции участков (сайтов) связывания конкретного белка в наборе последовательностей ДНК.

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

4. Созданы программное обеспечение SeSiMCMC с интерфейсом командной строки реализующее алгоритм, описанный в пункте (3), и открытый веб-интерфейс обращения к этому программному обеспечению.

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

6. С помощью программы SeSiMCMC были найдены дивергентные и поэтому трудные для алгоритмического обнаружения мотивы сайтов связывания двух регуляторов дыхания в Escherichia coli, а именно АгсА-Р и NarP. На основании этих мотивов было сделано первичное описание соответствующих регулонов.

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

1. Bailey, T. L., C. Elkan (1995). "The value of prior knowledge in discovering motifs with MEME." Proc Int Conf Intell Syst Mol Biol 3: 21-9.

2. Bailey, T. L., C. P. Elkan (1995). "Unsupervised learning of multiple motifs in biopolymers using expectation maximization." Machine Learning J 21: 51-83.

3. Bearson, S. M., J. A. Albrecht, R. P. Gunsalus (2002). "Oxygen and nitrate-dependent regulation of dmsABC operon expression in Escherichia coli: sites for Fnr and NarL protein interactions." BMC Microbiol 2(1): 13.

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

5. Berg, O. G., P. H. von Hippel (1988). "Selection of DNA binding sites by regulatory proteins." Trends Biochem Sci 13(6): 207-11.

6. Bongaerts, J., S. Zoske, U. Weidner, G. Unden (1995). "Transcriptional regulation of the proton translocating NADH dehydrogenase genes (nuoA-N) of Escherichia coli by electron acceptors, electron donors and gene regulators." Mol Microbiol 16(3): 521-34.

7. Brejova, В., С. DiMarco, Т. Vinar, S. Hidalgo, G. Holguin, C. Patten (2000). "Finding Patterns in Biological Sequences." Unpublished project report for CS798G, University of Waterloo.

8. Buhler, J., M. Tompa (2002). "Finding motifs using random projections." J Comput Biol 9(2): 225-42.

9. Bulyk, M. L. (2003). "Computational prediction of transcription-factor binding site locations." Genome Biol 5(1): 201.

10. Bulyk, M. L., E. Gentalen, D. J. Lockhart, G. M. Church (1999). "Quantifying DNA-protein interactions by double-stranded DNA arrays." Nat Biotechnol 17(6): 573-7.

11. Bulyk, M. L., X. Huang, Y. Choo, G. M. Church (2001). "Exploring the DNA-binding specificities of zinc fingers with DNA microarrays." Proc Natl Acad Sci U S A 98(13): 7158-63.

12. Campbell, J. W., R. M. Morgan-Kiss, J. E. Cronan, Jr. (2003). "A new Escherichia coli metabolic competency: growth on fatty acids by a novel anaerobic beta-oxidation pathway." Mol Microbiol 47(3): 793-805.

13. Cardon, L. R., G. D. Stormo (1992). "Expectation maximization algorithm for identifying protein-binding sites with variable lengths from unaligned DNA fragments." J Mol Biol 223(1): 15970.

14. Chao, G., J. Shen, C. P. Tseng, S. J. Park, R. P. Gunsalus (1997). "Aerobic regulation of isocitrate dehydrogenase gene (icd) expression in Escherichia coli by the arcA and fnr gene products." J Bacteriol 179(13): 4299-304.

15. Chen, P., D. I. Andersson, J. R. Roth (1994). "The control region of the pdu/cob regulon in Salmonella typhimurium." J Bacteriol 176(17): 5474-82.

16. Cliften, P. F., L. W. Hillier, L. Fulton, T. Graves, T. Miner, W. R. Gish, R. H. Waterston, M. Johnston (2001). "Surveying Saccharomyces genomes to identify functional elements by comparative DNA sequence analysis." Genome Res 11(7): 1175-86.

17. Collins, F. S., E. D. Green, A. E. Guttmacher, M. S. Guyer (2003). "A vision for the future of genomics research." Nature 422(6934): 835-47.

18. Colloms, S. D., C. Alen, D. J. Sherratt (1998). "The ArcA/ArcB two-component regulatory system of Escherichia coli is essential for Xer site-specific recombination at psi." Mol Microbiol 28(3): 521-30.

19. Compan, I., D. Touati (1994). "Anaerobic activation of arcA transcription in Escherichia coli: roles of Fnr and ArcA." Mol Microbiol 11(5): 955-64.

20. Crooks, G. E., G. Hon, J. M. Chandonia, S. E. Brenner (2004). "WebLogo: a sequence logo generator." Genome Res 14(6): 1188-90.

21. Darwin, A. J., J. Li, V. Stewart (1996). "Analysis of nitrate regulatory protein NarL-binding sites in the fdnG and narG operon control regions of Escherichia coli K-12." Mol Microbiol 20(3): 621-32.

22. Darwin, A. J., V. Stewart (1995). "Expression of the narX, narL, narP, and narQ genes of Escherichia coli K-12: regulation of the regulators." J Bacteriol 177(13): 3865-9.

23. Darwin, A. J., K. L. Tyson, S. J. Busby, V. Stewart (1997). "Differential regulation by the homologous response regulators NarL and NarP of Escherichia coli K-12 depends on DNA binding site arrangement." Mol Microbiol 25(3): 583-95.

24. Darwin, A. J., E. C. Ziegelhoffer, P. J. Kiley, V. Stewart (1998). "Fnr, NarP, and NarL regulation of Escherichia coli K-12 napF (periplasmic nitrate reductase) operon transcription in vitro." J Bacteriol 180(16): 4192-8.

25. Eskin, E., P. A. Pevzner (2002). "Finding composite regulatory patterns in DNA sequences." Bioinformatics 18 Suppl 1: S354-63.

26. Favorov, A. V., T. V. Andreewski, M. A. Sudomoina, O. O. Favorova, G. Parmigiani, M. F. Ochs (2005). "A Markov Chain Monte Carlo Technique for Identification of Combinations of Allelic Variants Underlying Complex Diseases." Genetics.

27. Fraenkel, Y. M., Y. Mandel, D. Friedberg, H. Margalit (1995). "Identification of common motifs in unaligned DNA sequences: application to Escherichia coli Lrp regulon." Comput Appl Biosci 11(4): 379-87.

28. Freeh, K., G. Herrmann, T. Werner (1993). "Computer-assisted prediction, classification, and delimitation of protein binding sites in nucleic acids." Nucleic Acids Res 21(7): 1655-64.

29. Frishman, D., A. Mironov, M. Gelfand (1999). "Starts of bacterial genes: estimating the reliability of computer predictions." Gene 234(2): 257-65.

30. Gelfand, M. (2003). Computational Identification of Regulatory Sites in DNA Sequences. Artificial intelligence and heuristic methods in bioinformatics. P. Frasconi and R. Shamir. Amsterdam; Washington, DC; Tokyo., IOS Press; Ohmsha. 183: 149-172.

31. Gelfand, M. S. (1999). "Recognition of regulatory sites by genomic comparison." Res Microbiol 150(9-10): 755-71.

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

33. Geman, S., D. Geman (1984). "Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images." IEEE Transactions on Pattern Analysis and Machine Intelligence 6: 621-641.

34. Gilks, W. R., S. Richardson, D. J. Spiegelhalter (1996). Markov chain Monte Carlo in practice. London, Chapman & Hall.

35. Golby, P., D. J. Kelly, J. R. Guest, S. C. Andrews (1998). "Transcriptional regulation and organization of the dcuA and dcuB genes, encoding homologous anaerobic C4-dicarboxylate transporters in Escherichia coli." J Bacterid 180(24): 6586-96.

36. Gold, L., D. Brown, Y. He, T. Shtatland, B. S. Singer, Y. Wu (1997). "From oligonucleotide shapes to genomic SELEX: novel biological regulatory loops." Proc Natl Acad Sci U S A 94(1): 5964.

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

38. Hassan, H. M., H. C. Sun (1992). "Regulatory roles of Fnr, Fur, and Arc in expression of manganese-containing superoxide dismutase in Escherichia coli." Proc Natl Acad Sci U S A 89(8): 3217-21.

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

40. Hertz, G. Z., G. D. Stormo (1999). "Identifying DNA and protein patterns with statistically significant alignments of multiple sequences." Bioinformatics 15(7-8): 563-77.

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

42. Hu, Y. J., S. Sandmeyer, C. McLaughlin, D. Kibler (2000). "Combinatorial motif analysis and hypothesis generation on a genomic scale." Bioinformatics 16(3): 222-32.

43. Jensen, L. J., S. Knudsen (2000). "Automatic discovery of regulatory patterns in promoter regions based on whole cell expression data and functional annotation." Bioinformatics 16(4): 326-33.

44. Jonassen, I. (1997). "Efficient discovery of conserved patterns using a pattern graph." Comput Appl Biosci 13(5): 509-22.

45. Kaiser, M., G. Sawers (1997). "Overlapping promoters modulate Fnr- and ArcA-dependent anaerobic transcriptional activation of the focApfl operon in Escherichia coli." Microbiology 143 (Pt 3): 775-83.

46. Kaiman, L. V., R. P. Gunsalus (1990). "Nitrate- and molybdenum-independent signal transduction mutations in narX that alter regulation of anaerobic respiratory genes in Escherichia coli." J Bacteriol 172(12): 7049-56.

47. Kielbasa, S. M., J. O. Korbel, D. Beule, J. Schuchhardt, H. Herzel (2001). "Combining frequency and positional information to predict transcription factor binding sites." Bioinformatics 17(11): 1019-26.

48. Marsaglia, G., A. Zaman (1994). "Some portable very-long-period random number generators." Computers in Physics 8(1): 117.

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

50. McGuire, A. M., P. De Wulf, G. M. Church, E. C. Lin (1999). "A weight matrix for binding recognition by the redox-response regulator ArcA-P of Escherichia coli." Mol Microbiol 32(1): 21921.

51. McGuire, A. M., J. D. Hughes, G. M. Church (2000). "Conservation of DNA regulatory motifs and discovery of new motifs in microbial genomes." Genome Res 10(6): 744-57.

52. Membrillo-Hernández, J., E. C. Lin (1999). "Regulation of expression of the adhE gene, encoding ethanol oxidoreductase in Escherichia coli: transcription from a downstream promoter and regulation by fnr and RpoS." J Bacteriol 181(24): 7571-9.

53. Mironov, A. A., N. P. Vinokurova, M. S. Gel'fand (2000). "Software for analyzing bacterial genomes." Mol Biol (Mosk) 34(2): 253-62.

54. Oliphant, A. R., C. J. Brandl, K. Struhl (1989). "Defining the sequence specificity of DNA-binding proteins by selecting binding sites from random-sequence oligonucleotides: analysis of yeast GCN4 protein." Mol Cell Biol 9(7): 2944-9.

55. Pellicer, M. T., C. Fernandez, J. Badia, J. Aguilar, E. C. Lin, L. Baldom (1999). "Cross-induction of glc and ace operons of Escherichia coli attributable to pathway intersection. Characterization of the glc promoter." J Biol Chem 274(3): 1745-52.

56. Pellicer, M. T., A. S. Lynch, P. De Wulf, D. Boyd, J. Aguilar, E. C. Lin (1999). "A mutational study of the ArcA-P binding sequences in the aldA promoter of Escherichia coli." Mol Gen Genet 261(1): 170-6.

57. Pesole, G., N. Prunella, S. Liuni, M. Attimonelli, C. Saccone (1992). "WORDUP: an efficient algorithm for discovering statistically significant patterns in DNA sequences." Nucleic Acids Res 20(11): 2871-5.

58. Pevzner, P. A., S. H. Sze (2000). "Combinatorial approaches to finding subtle signals in DNA sequences." Proc Int Conf Intell Syst Mol Biol 8:269-78.

59. Quail, M. A., D. J. Haydon, J. R. Guest (1994). "The pdhR-aceEF-lpd operon of Escherichia coli expresses the pyruvate dehydrogenase complex." Mol Microbiol 12(1): 95-104.

60. Quandt, K., K. Frech, H. Karas, E. Wingender, T. Werner (1995). "Matlnd and Matlnspector: new fast and versatile tools for detection of consensus matches in nucleotide sequence data." Nucleic Acids Res 23(23): 4878-84.

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

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

63. Richard, D. J., G. Sawers, F. Sargent, L. McWalter, D. H. Boxer (1999). "Transcriptional regulation in response to oxygen and nitrate of the operons encoding the NiFe. hydrogenases 1 and 2 of Escherichia coli." Microbiology 145 (Pt 10): 2903-12.

64. Rigoutsos, I., A. Floratos (1998). "Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm." Bioinformatics 14(1): 55-67.

65. Ritz, D., H. Patel, B. Doan, M. Zheng, F. Aslund, G. Storz, J. Beckwith (2000). "Thioredoxin 2 is involved in the oxidative stress response in Escherichia coli." J Biol Chem 275(4): 2505-12.

66. Robert, C. P., G. Casella (1999). Monte Carlo statistical methods. New York, Springer.

67. Rocke, E., M. Tompa (1998). An algorithm for finding novel gapped motifs in DNA sequences. Proceedings of the second annual international conference on Computational molecular biology RECOMB '98, New York, New York, United States: 228-233, ACM Press.

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

69. Rouchka, E. C. (1997). A Brief Overview of Gibbs Sampling, Washington University1.stitute for Biomedical Computing1. Statistics Study Group.

70. Shannon, C. E., W. Weaver (1949). The mathematical theory of communication. Urbana, University of Illinois Press.

71. Sivia, D. S. (1996). Data analysis: a Bayesian tutorial. Oxford; New York, Clarendon Press; Oxford University Press.

72. Stormo, G. D. (2000). "DNA binding sites: representation and discovery." Bioinformatics 16(1): 16-23.

73. Stormo, G. D., G. W. Hartzell, 3rd (1989). "Identifying protein-binding sites from unaligned DNA fragments." Proc Natl Acad Sei U S A 86(4): 1183-7.

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

75. Tompa, M. (1999). "An exact method for finding short motifs in sequences, with application to the ribosome binding site problem." Proc Int Conf Intell Syst Mol Biol: 262-71.

76. Tompa, R., C. M. McCallum, J. Delrow, J. G. Henikoff, B. van Steensel, S. Henikoff (2002). "Genome-wide profiling of DNA methylation reveals transposon targets of CHROMOMETHYLASE3." CurrBiol 12(1): 65-8.

77. Wang, H., R. P. Gunsalus (2000). "The nrfA and nirB nitrite reductase operons in Escherichia coli are expressed differently in response to nitrate than to nitrite." J Bacteriol 182(20): 5813-22.

78. Waterman, M. S. (1986). "Multiple sequence alignment by consensus." Nucleic Acids Res 14(22): 9095-102.

79. Weinmann, A. S., P. S. Yan, M. J. Oberley, Т. H. Huang, P. J. Farnham (2002). "Isolating human transcription factor targets by coupling chromatin immunoprecipitation and CpG island microarray analysis." Genes Dev 16(2): 235-44.

80. Wingender, E., P. Dietze, H. Karas, R. Knuppel (1996). "TRANSFAC: a database on transcription factors and their DNA binding sites." Nucleic Acids Res 24(1): 238-41.

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

82. Wolfsberg, T. G., A. E. Gabrielian, M. J. Campbell, R. J. Cho, J. L. Spouge, D. Landsman (1999). "Candidate regulatory sequence elements for cell cycle-dependent transcription in Saccharomyces cerevisiae." Genome Res 9(8): 775-92.

83. Wood, J. M. (1987). "Membrane association of proline dehydrogenase in Escherichia coli is redox dependent." Proc Natl Acad Sci U S A 84(2): 373-7.

84. Wyrick, J. J., R. A. Young (2002). "Deciphering gene expression regulatory networks." Curr Opin Genet Dev 12(2): 130-6.

85. Xu, X., L. Wang, D. Ding (2004). "Learning module networks from genome-wide location and expression data." FEBS Lett 578(3): 297-304.

86. Миронов, А. А., М. С. Гельфанд (1999). "Компьютерный анализ регуляторных сигналов в полных бактериальных геномах. Участки связывания РигЛ." Молекулярная биология 33(1): 127-132.

87. Фаворов, А. В. (2004). "Методологические различия физического и вычислительного модельных подходов." Биофизика 49(5): 958-960.

88. Фаворов, А. В., М. В. Волькенштейн (1991). "Механическая устойчивость цитоскелета и запуск перестроек клетки." Доклады Академии Наук СССР 319(5): 1239-1243.