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

Построение оптимальных моделей ДНК-сайтов связывания факторов транскрипции высших эукариот на основе данных различных экспериментальных методов

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

Автореферат диссертации по теме "Построение оптимальных моделей ДНК-сайтов связывания факторов транскрипции высших эукариот на основе данных различных экспериментальных методов"

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

Кулаковский Иван Владимирович

□□3481500

Построение оптимальных моделей ДНК-сайтов связывания факторов транскрипции высших эукариот на основе данных различных экспериментальных методов

03.00.28 Биоинформатика

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

Москва

— 2009

003481500

Работа выполнена в лаборатории биоинформатики и системной биологии Учреждения Российской академии наук Института молекулярной биологии им. В.А. Энгельгардта РАН

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

д.ф.-м.н., проф. Владимир Гайсвич Туманян

Официальные оппоненты: д.б.н. Мария Георгиевна Самсонова,

Санкт-Петербургский государственный политехнический университет к.ф.-м.п. Андрей Владимирович Алексеевский, Научно-исследовательский институт физико-химической биологии им. А.Н. Белозерского, МГУ им. М.В. Ломоносова

Ведущая организация:

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

Защита состоится 25 ноября 2009 года в 14 часов на заседании Диссертационного совета Д002.077.02 при Учреждении Российской академии наук Институте проблем передачи информации им. A.A. Харкевича РАН по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, 19, стр. 1.

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

Автореферат разослан «лЗ » октября 2009 года.

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

д.б.н., профессор Рожкова Галина Ивановна

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

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

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

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

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

построения оптимальных моделей ССТФ на основе различных типов экспериментальных данных.

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

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

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

Были поставлены следующие задачи:

• Разработать методику построения оптимальной модели ССТФ па базе результатов традиционных (догеномных) экспериментальных методов.

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

• Реализовать алгоритмы, соответствующие разработанным методам, в виде программных инструментов.

• Верифицировать построенные модели с использованием экспериментальных данных для различных транскрипционных факторов.

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

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

Практическое значение

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

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

Материалы исследований по теме диссертации докладывались и обсуждались на международных научных конференциях BGRS (International Conference on Bioinformatics of Genome Regulation and Structure, Новосибирск 2008) и MCCMB (Moscow Conference on Computational Molecular Biology, Москва 2007, 2009); на конференции молодых ученых ИТиС (Информационные технологии и системы, Звенигород 2007, Геленджик 2008); на IV съезде Российского общества биохимиков

и молекулярных биологов (Новосибирск 2008); на симпозиуме Helmholtz Russian-German Workshop on Systems Biology (Москва 2008).

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

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

Диссертационная работа изложена на 100 страницах машинописного текста и включает в себя введение, обзор литературы, четыре главы, содержащие результаты и обсуждение, выводы и список литературы из 168 наименований. Работа содержит 18 рисунков, 3 таблицы и 5 приложений.

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

Введение и обзор литературы

Раздел содержит аналитический обзор современной литературы, посвященный сравнению современных экспериментальных методов локализации ССТФ в последовательностях нуклеиновых кислот, и описание подходов к построению биоинформатических моделей. Кроме того, в разделе излагается мотивировка постановки решаемых в работе задач и описание их значимости. Идея большинства алгоритмов поиска ССТФ основана на предположении, что различные сайты связывания одного и того же белка схожи между собой, т.е. их выравнивания обладают консервативными позициями. Это позволяет свести задачу поиска набора сайтов, узнаваемых одним и тем же транскрипционным фактором, к задаче нахождения множества сходных фрагментов (мотива) в выборке экспериментально полученных последовательностей ДНК, для которых показано связывание с ТФ. Таким образом, последовательности, включающие в себя ССТФ, должны допускать безделеционное множественное локальное выравнивание (БЛВ, Waterman, 1986) с высоким сходством выравненных сегментов ДНК. БЛВ может быть легко преобразована в классическую модель мотива, а именно матрицу позиционных весов (МПВ, Schneider, 1986). Под мотивом мы везде понимаем БЛВ и соответствующую ему МПВ.

Гпава 1. Моделирование ССТФ в виде МПВ

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

1.1 Представление мотива

БЛВ может быть естественным образом представлено в виде матрицы позиционных подсчетов (МПГТ) в которой каждый элемент хкп ]- ]...т представляет собой число встреч нуклеотида а в /-й колонке выравнивания. При классическом подходе предполагается, что элементы МПП — целые числа. Мы допускаем, что БЛВ может содержать нескольких слов (длины т, т-меров) из одной и той же последовательности. Кроме того, предполагается, что выравниваемые последовательности могут вносить разный вклад в итоговый мотив, что формализуется путем присвоения последовательностям весов и;. Пусть последовательность л,-, принадлежащая исходному набору из N последовательностей, имеет вес wi и содержит к, слов из БЛВ. В этом случае вклад каждого слова в МПП будет равен и',/к, (и ха/ могут быть вещественными числами). Таким образом, принятый в работе подход отличается от традиционного, в котором каждому слову, принадлежащему выравниванию, соответствует вклад в некоторые элементы МПП, равный единице.

1.2 Выбор оптимального БЛВ

Для выбора оптимального БЛВ (ОБЛВ) было предложено использовать дискретное информационное содержание (ДИС):

где m - длина выравнивания (мотива), Ij - ДИС одной колонки. Для подсчета lnx! выбрано приближение Стилтьеса (т. е. для вещественных х используется значение гамма-функции). ДИС является аналогом традиционного информационного содержания (Schneider, 1986) для больших выборок и дает более корректную оценку в случае малых выборок (что типично при анализе данных, полученных с помощью SELEX и футпринтинга с ДНКазой I). ОБЛВ соответствует максимальному ДИС для

(1)

заданного набора последовательностей (ДИС отрицательно и имеет потенциальный максимум в нуле, соответствующий 100% консервативным колонкам).

1.3 Построение МПВ

Для построения МПВ по БЛВ используется формула:

Здесь qa соответствует фоновому распределению нуклеотидов (например, средняя встречаемость нуклеотидов в геноме), а - псевдоотсчет (ЫГапоу, 2003). Для каждого т-мера МПВ позволяет вычислить качество этого слова .г, которое можно использовать как характеристику правдоподобия того, что данное слово является

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

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

1.5 Сравнительная оценка предсказательной способности мотивов

С помощью МПВ и критерия качества слова, можно осуществить предсказание ССТФ в исходных экспериментальных данных. Для сравнения эффективности различных мотивов на заданном наборе последовательностей мы использовали модифицированные ROC-кривые (Receiver Operating Characteristic), которые выражают зависимость между чувствительностью (долей истинных предсказаний) и избирательностью (долей ложных предсказаний). Множество истинных

(2)

сайтом связывания > гДе wi"это7"ая буква слова w.

предсказаний (true positive) составляет набор лучших вхождений мотива в последовательности тестового набора, имеющие вхождения с оценкой МПВ выше заданного порогового значения. Множество ложных предсказаний (false positive) составляют все слова с оценкой МПВ выше того же порога, которые могут присутствовать в случайной последовательности. Таким образом, ROC-кривая будет представлена графиком, на котором значения по оси Y соответствуют доле экспериментально определенных последовательностей, имеющих лучшее вхождение выше порога; по оси X - P-value (вероятность встретить слово с оценкой МПВ выше порога в случайной последовательности). Под случайной последовательностью мы понимаем последовательность независимых случайных испытаний над ДНК-алфавитом с фоновыми вероятностями нуклеотидов, оцененными из полного генома. При сравнении мотивов длиной меньше или равной от, длина случайной последовательности выбирается как Зот-2. Это позволяет учесть возможные эффекты самопериодичности мотива. Для подсчета точных значений P-value использован алгоритм AhoPro (Boeva, 2007).

Для суммарной оценки качества ,мотива подсчитывали число точек ROC кривых (каждая точка соответствует одной последовательности в наборе), в которых чувствительность конкретного мотива оказывалась выше всех остальных, участвовавших в сравнении (т. е. ROC-кривая этого мотива проходит слева от остальных, см. рисунок 2). Фактически, в этом случае мы оцениваем, как часто мотив показывает лучшую чувствительность при фиксированной доле ложных предсказаний. Зная, что в наборе могут содержаться ошибочные последовательности, не содержащие реальных ССТФ и, следовательно, вхождений мотива, из рассмотрения разумно исключать ряд точек в правой области ROC-кривой (например, ограничиваясь фиксированным процентом рассматриваемых последовательностей, либо минимально допустимыми порогами для мотивов, либо ограничивая диапазон значимых P-value). При анализе малых выборок в главе 2 мы используем диапазон 10-90% последовательностей. В главе 3 для больших выборок

мы ограничиваемся диапазоном (0, 0.1) для P-value и нижней границей па пороги каждого мотива заданной как t3.

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

Исследование ССТФ получило существенное развитие с появлением новых высокопроизводительных экспериментальных методов анализа на базе иммунопреципитации хроматина (СЫР) с последующей гибридизацией выделенной ДНК на микрочипах (Horak and Snyder, 2002), либо непосредственным секвенированием (Mardis, 2007). Эти методы дают возможность определения ССТФ в масштабах полного генома. Недостатком метода ChIP оказалась сравнительно большая длина выделяемых фрагментов ДНК, что во многих случаях затрудняет однозначное определение ССТФ. Однако, привлечение дополнительных данных, полученных традиционными методами футпринтинга (Galas and Schmitz, 1978) и SELEX (systematic evolution of ligands by exponential enrichment, Tuerk and Gold, 1990), часто дает возможность корректной интерпретации и верификации данных ChIP. В частности, на основе ССТФ-содержащих искусственных олигонуклеотидов, получаемых с использованием SELEX-подобных методов, можно непосредственно строить ОБЛВ. Для ряда высших эукариот накоплен большой экспериментальный материал, систематизированный в базах данных (Kolchanov, 2002; Sandelin, 2004). Нами был разработан набор инструментов для работы с коммерчески доступной базой данных TRANSFAC (Matys, 2003), осуществляющий картирование на геном выбранного организма данных для заданного ТФ, извлечение сегментов ДНК с соответствующими фланкирующими областями и корректное построение ОБЛВ с помощью опубликованного ранее алгоритма SeSiMCMC (Favorov, 2005). Эта методика была успешно применена для определения мотива связывания белка Spl у Homo sapiens.

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

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

Для выработки универсальной методики получения ОБЛВ на базе результатов футпринтинга нами был разработан новый алгоритм Bigfoot. Были использованы данные футпринтов для различных ТФ D. melanogaster, картированные на геном и систематизированные в курированной БД Drosophila DNasc I Footprint Database (Bergman, 2005).

2.1 Алгоритм Bigfoot

Алгоритм выполняет поиск оптимального мотива путем построения ОБЛВ в заданном диапазоне длин (перебираемом в направлении от наименьшей к наибольшей) на базе футпринтов, взятых с соответствующими фланкирующими областями. Bigfoot предполагает, что каждая последовательность содержит одно значимое вхождение мотива. Проблема отсечения фрагментов, являющихся ошибками эксперимента, решается для уже построенного ОБЛВ, как описано в разделе 2.2. Для исследуемого ТФ длина фланков выбирается как разность длин самого короткого футпринта и стартовой длины мотива (если мотив длиннее, чем самый короткий футпринт). Длина фланков увеличивается при переходе от длины т

к т+1. Построив ОБЛВ с максимальным ДИС, алгоритм определяет оптимальную длину мотива. Эта процедура основана на оценке значимости колонок путем применении критерия к колонкам выравнивания и идентификации наиболее стабильного ядра (наиболее консервативной части) мотива для разных длин ОБЛВ. Помимо определения оптимальной длины мотива эта процедура решает проблему переобученное™ модели, которая часто возникает на малых выборках (что типично для классических экспериментальных методов исследования ССТФ).

Для поиска ОБЛВ заданной длины Bigfoot использует модификацию классического подхода максимизации правдоподобия (Bailey and Elkan, 1994). МП-процедура для заданной стартовой МПВ заключается в выборке слов с максимальными оценками из каждой последовательности и итеративной перестройке МПВ на базе каждого нового набора слов. В случае наличия в последовательности нескольких слов с одинаковой наилучшей для данной последовательности оценкой, используются все слова, причем им присваиваются веса в соответствии с методикой, описанной ранее. В качестве стартовых МПВ Bigfoot использует МПВ построенные из всех возможных пар слов, содержащихся в последовательностях, используемых для построения ОБЛВ.

2.2 Коллекция DMMPMM

В результате работы был создан автоматизированный программный конвейер DMMPMM (Drosophila Melanogaster Major Position Matrix Motifs, htlp://line.imb.ac.ru/DMMPMMA для построения коллекции основных мотивов ССТФ D. melanogaster, заданных в форме МПВ. Данные БД футпршггов были загружены в

С

База данных ДНКазных футпринтов D.melanogaster

а- I В1Н HD

О

В1Н

БД small-BiSMark j

добавление |

фланкирующих поел едо ва те л ь н осте й

D

.................I ^ , ,, ,, ,г

Bigfoot fBigfoot) CSeSiMCMC) (Down) (Pollard; (Beipman)(Papatsenko:

сравнение, верификация и оценка качества мотивов

Рисунок 1. Схема построения коллекции DMMPMM.

специализированную БД (см. Главу 4). Для построения мотивов использовали опубликованный ранее алгоритм SeSiMCMC и новый алгоритм Bigfoot.

В качестве данных использовались результаты ДНК футпринтига для 41 ТФ, т.е. для всех факторов D, melanogaster; для которых доступны футпринты числом более восьми. Для сравнительного анализа были использованы существующие коллекции мотивов (Papatsenko, 2007; Pollard 2006; Down, 2007), частично основанные на БД футпринтов, а также коллекция мотивов (Bergman, 2005), построенная на базе SELEX. Кроме того, были использованы данные бактериальной одногибридной системы (В1Н, Noyes, 2008). В этом случае для определения мотивов ТФ (за исключением независимой коллекции мотивов гомеодомениых (HD) белков) использовали алгоритм Bigfoot. Для построения МПВ по ОБЛВ псевдоотсчет был принят равным 1; в рамках МП-процедуры Bigfoot использовал псевдоотсчеты, равные числу последовательностей в ОБЛВ.

Для оценки количества футпринтов, не содержащих ССТФ, мы выбрали пороговые значения на качество лучшего слова в последовательности (см. Главу 1): лучше, чем t} (мотив присутствует); хуже, чем г, (мотив отсутствует). Дополнительно для подсчета числа случаев, когда рассмотрение фланкирующих областей дало возможность восстановить вхождения мотивов, мы ввели порог í2: успешно восстановленным сайтом считали ситуацию, когда добавление фланков к последовательности, в которой изначально максимальное качество МПВ не превышало t¡, позволяло найти сайт лучше t2.

В результате удалось установить, что только для 25% ТФ все доступные футпринты для всех коллекций мотивов содержали хорошее вхождение МПВ. Для других 25% все коллекции мотивов детектировали наличие футпринтов, не содержащих сайта. В оставшихся 50% случаев «ошибочные» футпринты детектировались мотивами только из некоторых коллекций. Добавление фланкирующих последовательностей длиной 2 п.н. позволяло восстановить более 50% утерянных сайтов; добавление фланков длины равной длине мотива доводило это число до 80%.

[а]

РЮС-кривые МПВ ТФ Вюо!с1 на базе 48 футпринтов, средняя длина последовательности 28 п.н., длина фланков 7 п.н.

мотив длины 6 мотив длины 8 мотив длины 10 мотив длины 12

1ЧОС-кривые МПВ ТФ Вюо1"с1 на базе 48 футпринтов; данные БЕЦЕХ в качестве тестового набора

мотив длины 6 —в— мотив длины В —в—

мотив длины 10 -А—

мотив длины 12 —

СЭГ"'"

^ Лай — ) т

Рисупок 2. Проверка переобученное™ мотивов па базе двух источников данных, (а) КОС-кривые для мотивов разных длин, построенных Б|^Гоо1 на наборе футпринтов для фактора В1с01с1. Качество мотива растет с ростом длины (соотв. увеличению числа свободных параметров), что демонстрирует переобучепность МПВ. (б) ИОС-кривые с использованием данных вЕЬЕХ в качестве тестового набора. Оптимальная длина мотива здесь составляет 8 п.н.

Кроме того, рассмотрение фланкирующих областей позволило построить более точные МПВ. Даже с учетом жесткой процедуры определения длины, мотивы, построенные с помощью Bigfoot, в 10% случаев оказались лучшими среди всех коллекций. В случае отключенной процедуры определения длины В1§Гоо1 показал лучшую чувствительность в 60% случаев. Кроме того, удалось установить, что курированные коллекции мотивов и мотивы, созданные на основе данных БЕЬЕХ и ВШ-системы, обладают плохой предсказательной способностью на наборах футпринтов. Важным результатом также является демонстрация существенной переобученное™ моделей (рисунок 2), построенных всего на одном экспериментальном источнике данных, что дает дополнительный стимул к интеграции различных источников.

Глава 3. Интеграция данных, полученных различными экспериментальными методами для определения мотивов ССТФ в последовательностях ДНК

Одной из важных проблем в определении ССТФ является идентификация длины участка ДНК, несущего сигнал специфического связывания с регуляторным белком. Практика показывает, что эта проблема не может быть однозначно решена при использовании данных СЫР, 8ЕЬЕХ или футпринтига, рассмотренных по отдельности. Интеграция данных, полученных различными экспериментальными методами, позволяет не только эффективно решить эту проблему, но и получить в общем случае мотивы, обладающие лучшей предсказательной способностью.

Первый подход, который мы применили при исследовании ТФ Бр1 человека, заключался в том, чтобы совместно использовать неточные данные СЫР-сЫр и БЕЬЕХ для построения совместной модели мотива. В этом случае данные БЕЬЕХ использовались для расстановки якорей внутри последовательностей, полученных СЫР-сЫр. Под якорями мы понимаем слова, отличающиеся от найденных с помощью БЕЬЕХ не более чем иа фиксированное число замен. Затем, с помощью 8е81МСМС мы строили «заякоренное» БЛВ, т. е. такое, в котором каждое слово выравнивания пересекалось с якорным словом не менее чем в одной позиции. Совместное использование СЫР-сЫр и ЗЕЬЕХ в этом случае позволило выявить

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

Для D. melanogaster мы разработали более гибкий подход, позволивший интегрировать все доступные на сегодня источники данных, сравнение которых проводилось в главе 2. Дополнительно мы использовали данные ChlP-chip (MacArthur, 2009). Были выбраны сегменты длиной 500 п.н., несущие сигнал ChlP-chip с интенсивностью, входившей в сотню лучших значений по геному (в тех случаях, когда были доступны данные нескольких независимых экспериментов, соответствующие геномные сегменты составляли единую выборку). С учетом этих данных был создан набор из 39 ТФ, для которых были доступны последовательности из двух и более экспериментальных источников, использованных для коллекции DMMPMM. Принималось предположение, что каждая последовательность содержит единственное вхождение мотива неизвестной длины.

3.1 Алгоритм Chipmunk

Алгоритм Chipmunk разработан для определения мотива из данных ChlP с возможностью использования данных, полученных традиционными методами, как дополнительных источников информации. В качестве входных данных Chipmunk использует п независимых наборов последовательностей; различные наборы соответствуют различным источникам данных. Последовательностям присваиваются веса, равные в пределах одного набора. Пусть N - полное число последовательностей во всех и наборах, 1к - число последовательностей в к-м наборе; тогда вес каждой последовательности в fc-м наборе принимается

N

равным j . ОБЛВ строится на объединенном наборе взвешенных

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

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

Для поиска ОБЛВ заданной длины Chipmunk использует модификацию алгоритма максимизации ожидания с бутстраппингом. Основой алгоритма является процедура двухэтапной оптимизации (ДО) МПВ. На первом этапе предварительной оптимизации выбирается случайное подмножество последовательностей (возможно с дубликатами) общим весом порядка . Выполняется фиксированное число итераций МП-оптимизации на выбранном подмножестве последовательностей. Полученная в результате матрица подвергается МП-оптимизации до сходимости на полном наборе последовательностей. МП позволяет существенно (до 50% в зависимости от набора последовательностей и МПВ) уменьшить число итераций по сравнению с прямой оптимизацией МПВ на полном наборе последовательностей.

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

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

В большинстве реализацией МП-алгоритмов рассматривается большое число

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

Для выбора оптимальной длины ОБЛВ в заданном диапазоне длин алгоритм перебирает их, начиная с наибольшей, и останавливается тогда, когда находит так называемый сильный мотив. Выберем два пороговых значения на ДИС: Т и /. Т соответствует ДИС колонки, в которой представлены только 3 нуклеотида из возможных 4х; t соответствует колонке, в которой два из четырех нуклеотидов представлены в два раза более часто, чем два оставшихся. Будем считать, что мотив состоит из нескольких доменов в том случае, если одна или несколько внутренних колонок выравнивания имеют ДИС хуже t. Сильным называется мотив, для которого в целом и для каждого входящего в него домена выполняется следующее условие: крайние колонки имеют ДИС не хуже t, присутствует не менее одной колонки с ДИС лучше Т. Использование такого критерия возможно благодаря сравнительно большим выборкам, получающимся при объединении различных экспериментальных источников.

3.2 Коллекция iDMMPMM

Созданная коллекция iDMMPMM (impoved Drosophila Melanogaster Major Position Matrix Motifs, коллекция улучшенных основных МПВ мотивов D. melanogaster, http://line.imb.ac.ru/iDMMPMM) содержит 39 интегрированных мотивов, построенных с помощью Chipmunk как ОБЛВ объединенной взвешенной выборки.

Для ROC-анализа мы создали независимые наборы последовательностей. Для этого выбрали 300 сегментов длиной 500 п.н., соответствующих лучшим сигналам

ChlP-chip для каждого фактора и исключили из этой выборки лучшие 100, использованные при построении мотивов (при наличии независимых экспериментов выборки последовательностей объединялись). От 50 до 90% точек ROC-кривых интегрированных мотивов соответствуют наилучшей чувствительности для 90% факторов (пример для фактора Knirps приведен на рисунке 3).

Анализ мотивов из различных независимых источников позволяет утверждать, что в более чем 80% случаев интеграция данных позволила построить мотив с лучшими показателями чувствительности и избирательности в широком диапазоне порогов МПВ. Случаи, когда интеграция источников приводила к ухудшению мотива, соответствуют либо недостаточному объему данных, либо реальному существованию различных функциональных мотивов для одного ТФ.

Гпава 4. Программная реализация

В качестве эффективного стандартного формата передачи данных в рамках работы был разработан язык разметки smaII-BiSMark(small Biological Sequence Markup Language) на основе XML и набор инструментов для поддержки базы данных (работающей под управлением MySQL 5), адаптированной для импорта и экспорта наборов сегментов ДНК и моделей ССТФ на их основе. Кроме того, разработана многофункциональная библиотека для решения различных вычислительных задач, интегрирующая новые алгоритмы Bigfoot и Chipmunk, а также существующие инструменты AhoPro и SeSiMCMC.

Программные конвейеры для сборки коллекций мотивов, автоматизированной верификации и сравнения реализованы на базе Ruby 1.8. Вычислительно-нагруженные этапы алгоритма Bigfoot и алгоритм Chipmunk реализованы на базе Java 1.6. Созданный набор программных средств базируется исключительно на свободном программном обеспечении, является кросс-платформенным и был успешно протестирован на платформах Windows (ХР32/64) и Linux (Ubuntu 8.04).

ROC-кривые МПВ на основе данных В1Н-системы для фактора Knirps длина случайной последовательности 40 п.о.

Мотив на основе футпринтов —£}-Мотив на основе ChlP-chip данных — Интегрированный мотив — Мотив на основе футпринтов и ChlP-chip данных —А-

о «

О ф

* §

0) л

о "

0 2

1 О Л со

s |

1е-006

1е-005

0.0001

0.01

(Down, 2007) (Papatsenko, 2007) ChlP-chip футпринтинг В1Н-система интегрированный мотив

Рисунок 3. ROC-кривые, полученные на базе результатов BlH-еиетсмы в качестве тестового набора последовательностей. Мотивы построены с помощью алгоритма Chipmunk.

При визуализации ДИС используется для масштабирования колонок выравнивания. Мотивы, представленные в коллекциях (Down) и (Papatsenko), соответствуют неверным сигналам.

Выводы

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

2. Разработан метод построения оптимальной модели ССТФ путем интеграции данных различных экспериментальных методов, включая современные высокопроизводительные техники на базе иммунопреципитации хроматина. Метод реализован в виде вычислительного алгоритма Chipmunk.

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

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

5. Разработанные программные средства и построенные коллекции уточненных мотивов доступны в сети Интернет по адресам: http://line.imb.ac.ru/DMMPMM, http://line.imb.ac.ru/iDMMPMM, http://line.imb.ac.ru/Chipmunk.

Список принятых сокращений

БЛВ безделеционное локальное выравнивание

ДИС дискретное информационное содержание

ДО двухэтапная оптимизация

МП максимизация правдоподобия

МПВ матрица позиционных весов

МПП матрица позиционных подсчетов

ОБЛВ оптимальное безделеционное локальное выравнивание

ССТФ сайты связывания транскрипционных факторов

ТФ транскрипционный фактор

ChIP chromatin immunoprecipitation

SELEX systematic evolution of ligands by exponential enrichment

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

Статьи в реферируемых журналах

1. I.V. Kulakovskiy, A.V. Favorov, VJ. Makeev (2009) Motif discovery and motif finding from genome-mapped DIM Ase footprint data. Bioinformatics, 25(18), 2318-2325

2. И.В. Кулаковский, В.Ю. Макеев (2009) Интеграция данных, полученных различными экспериментальными методами, для определения мотивов в последовательностях ДНК, распознаваемых факторами, регулирующими транскрипцию. Биофизика, 54(6), 965

Тезисы конференций

1. I.V. Kulakovskiy, V.J. Makeev (2007) Constructing PWM from unaligned TFBS footprints. Proceedings of the 3-rd Moscow Conference on Computational Molecular Biology; 167-168, Moscow

2. A.B. Фаворов, M.C. Гельфаид, А. Герасимова, Д.А. Равчеев, И. Кулаковский, А. Миронов, В. Макеев (2007) Алгоритм SeSiMCMC для поиска участков специфического связывания белков-регуляторов транскрипции. Сборник трудов конференции «Информационные технологии и системы» ИТиС'07, 334-337, Звенигород

3. 1. V. Kulakovskiy (2008) Integrated tool for analysis of DNA-protein binding data. Helmholtz Russian-German Workshop on Systems Biology, 45, Moscow

4. И.В. Кулаковский, A.A. Белостоцкий, A.B. Фаворов, B.A. Боева, Д.Б. Малько, В.Ю. Макеев (2008) Интеграция различных типов экспериментальных данных для анализа последовательностей регуляторных районов эукариот. Сборник материалов IVсъезда Российского общества биохимиков и молекулярных биологов, 278, Новосибирск

5. A. Heinzel, I.V. Kulakovskiy, V.J. Makeev (2008) Comparison of ChlP-chip Spl binding location data for human chromosome 21, 22 with PWM hits. The Sixth International Conference on Bioinformatics of Genome Regulation and Structure, 97, Novosibirsk

6. I.V. Kulakovskiy, A.V. Favorov, V.J. Makeev (2008) Incorporating different types of experimental data on DNA-protein binding into the single in silico model. The Sixth International Conference on Bioinformatics of Genome Regulation and Structure, 129, Novosibirsk

7. Y.A. Medvedeva, M.V. Fridman, N.J. Oparina, D.B. Malko, E.O. Ermakova, I.V. Kulakovskiy, V.J. Makeev (2008) Non-5' CpG islands in the human genome: probable involvement in transcription regulation. Сборник трудов конференции «Информационные технологии и системы» ИТиС'08, 298-299, Геленджик

8. I.V. Kulakovskiy, V.A. Boeva, A.V. Favorov, V.J. Makeev (2009) Chipmunk: a fast DNA motif finder for ChIP data and its application to data integration from different experimental sources. Proceedings of the 4-th Moscow Conference on Computational Molecular Biology, 194, Москва

Подписано в печать 23.10.2009 г. Печать лазерная цифровая Тираж 100 экз.

Типография Aegis-Print 115230, Москва, Варшавское шоссе, д. 42 Тел.: 543-50-32 www.autoref.ae-print.ru

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

Введение.

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

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

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

Практическое значение.

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

Заключение Диссертация по теме "Биоинформатика", Кулаковский, Иван Владимирович

Выводы

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

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

3. Создан набор программных средств, реализующих предложенные алгоритмы. Созданные программы позволяют на базе различных вычислительных платформ анализировать данные, полученные с использованием широкого спектра экспериментальных методик. Создан единый вычислительный конвейер, интегрирующий новые алгоритмы и существующие программные инструменты АЬоРго и 8е81МСМС.

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

5. Разработанные программные средства и построенные коллекции уточненных мотивов доступны в сети Интернет по адресам: http://line.imb .ac.ru/DMMPMM, http://line.imb. ac.ru/iDMMPMM, http://line.imb.ac.ru/Chipmunk.

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

1. Abramowitz, M. and Stegun, I.A. (1972) Handbook of Mathematical Functions, Dover Publications, New York

2. Angarica, V.E., Perez, A.G., Vasconcelos, A.T. et al. (2008) Prediction of TF target sites based on atomistic models of protein-DNA complexes. BMC Bioinformatics, 9, 436

3. Ao, W., Gaudet, J., Kent, W.J. et al. (2004) Environmentally induced foregut remodeling by PHA-4/FoxA and D AF-12/NHR. Science, 305, 1743-1746

4. Badis, G., Berger, M.F., Philippakis, A.A. et al. (2009) Diversity and complexity in DNA recognition by transcription factors. Science, 324(5935), 1720-1723

5. Bailey, T.L., Boden, M., Buske, F. A. et al. (2009) MEME SUITE: tools for motif discovery and searching. Nucleic Acids Res, 37, W202-W208

6. Barski, A., Cuddapah, S., Cui, K. et al. (2007) High-resolution profiling of histone methylations in the human genome. Cell, 129, 823-837

7. Beckstette, M., Homann, R., Giegerich, R. et al. (2006) Fast index based algorithms and software for matching position specific scoring matrices. BMC Bioinformatics, 1, 389

8. Ben-Gal, I., Shani, A., Gohr, A. et al. (2005) Identification of transcription factor binding sites with variable-order Bayesian networks. Bioinformatics, 21, 2657-2666

9. Ben-Tabou de-Leon, S. and Davidson, E.H. (2007) Gene regulation: gene control network in development. An пи Rev Biophys Biomol Struct, 36, 191

10. Benizri, E., Ginouves, A. and Berra, E. (2008) The magic of the hypoxia-signaling cascade. Cell Mol Life Sei, 65, 1133-1149

11. Benos, P.V., Bulyk, M.L. and Stormo, G.D. (2002) Additivity in protein-DNAinteractions: how good an approximation is it?. Nucleic Acids Res, 30, 4442-4451

12. Berg, O.G. and von Hippel, P.H. (1987) Selection of DNA binding sites by regulatory proteins. Statistical-mechanical theory and application to operators and promoters. JMolBiol, 193, 723-750

13. Berger, M.F., Philippakis, A.A., Qureshi, A.M. et al. (2006) Compact, universal DNA microarrays to comprehensively determine transcription-factor binding site specificities. Nat Biotechnol, 24, 1429-1435

14. Bergman, C.M., Carlson, J.W. and Celniker, S.E. (2005) Drosophila DNase I footprint database: a systematic genome annotation of transcription factor binding sites in the fruitfly, Drosophila melanogaster. Bioinformatics, 21, 1747-1749

15. Berman, H.M., Olson, W.K., Beveridge, D.L. et al. (1992) The nucleic acid database. A comprehensive relational database of three-dimensional structures of nucleic acids. BiophysJ, 63, 751-759

16. Blackwell, T.K. and Weintraub, H. (1990) Differences and similarities in DNA-binding preferences of MyoD and E2A protein complexes revealed by binding site selection. Science, 250, 1104-1110

17. Blanchette, M., Schwikowski, B. and Tompa, M. (2002) Algorithms for phylogenetic footprinting. J Comput Biol, 9, 211-223

18. Boeva, V., Clement, J., Regnier, M. et al. (2007) Exact P-value calculation for heterotypic clusters of regulatory motifs and its application in computational annotation of cis-regulatory modules. Algorithms Mol Biol, 2, 13

19. Boeva, V., Regnier, M., Papatsenko, D. et al. (2006) Short fuzzy tandem repeats in genomic sequences, identification, and possible role in regulation of gene expression. Bioinformatics, 22, 676-684

20. Boffelli, D., McAuliffe, J., Ovcharenko, D. et al. (2003) Phylogenetic shadowing of primate sequences to find functional regions of the human genome. Science, 299, 1391-1394

21. Brazma, A., Jonassen, I., Vilo, J. et al. (1998) Predicting gene regulatoryelements in silico on a genomic scale. Genome Res, 8, 1202-1215

22. Brivanlou, A.H. and Darnell, J E, Jr (2002) Signal transduction and the control of gene expression. Science, 295, 813-818

23. Biyne, J.C., Valen, E., Tang, M.H. et al. (2008) JASPAR, the open access database of transcription factor-binding profiles: new content and tools in the 2008 update. Nucleic Acids Res, 36, D102-6

24. Buck, M.J. and Lieb, J.D. (2004) ChlP-chip: considerations for the design, analysis, and application of genome-wide chromatin immunoprecipitation experiments. Genomics, 83, 349-360

25. Bulyk, M.L. (2006) DNA microarray technologies for measuring protein-DNA interactions. Curr Opin Biotechnol, 17, 422-430

26. Bulyk, M.L., Johnson, P.L. and Church, G.M. (2002) Nucleotides of transcription factor binding sites exert interdependent effects on the binding affinities of transcription factors. Nucleic Acids Res, 30, 1255-1261

27. Butler, J.E. and Kadonaga, J.T. (2002) The RNA polymerase II core promoter: a key component in the regulation of gene expression. Genes Dev, 16, 2583-2592

28. Cawley, S., Bekiranov, S., Ng, H.H. et al. (2004) Unbiased mapping of transcription factor binding sites along human chromosomes 21 and 22 points to widespread regulation of noncoding RNAs. Cell, 116(4), 499-509

29. Chen, X., Guo, L., Fan, Z. et al. (2008) W-AlignACE: an improved Gibbs sampling algorithm based on more accurate position weight matrices learned from sequence and gene expression/ChlP-chip data. Bioinformatics, 24, 1121-1128

30. Chen, Z., Lewis, K.A., Shultzaberger, R.K. et al. (2007) Discovery of Fur binding site clusters in Escherichia coli by information theory models. Nucleic Acids Res, 35, 6762-6777

31. Cliften, P.F., Hillier, L.W., Fulton, L. et al. (2001) Surveying Saccharomyces genomes to identify functional elements by comparative DNA sequence analysis. Genome Res, 11, 1175-1186

32. Contreras-Moreira, B., Branger, P.A. and Collado-Vides, J. (2007) TFmodeller: comparative modelling of protein-DNA complexes. Bioinformatics, 23, 1694-1696

33. Dai, S.M., Chen, H.H., Chang, C. et al. (2000) Ligation-mediated PCR for quantitative in vivo footprinting. Nat Biotechnol, 18, 1108-1111

34. Das, D., Banerjee, N. and Zhang, M.Q. (2004) Interacting models of cooperative gene regulation. Proc Natl Acad Sci USA, 101, 16234-16239

35. Das, M.K. and Dai, H.K. (2007) A survey of DNA motif finding algorithms. BMC Bioinformatics, 8 Suppl 7, S21

36. Day, W.H. and McMorris, F.R. (1992) Critical comparison of consensus methods for molecular sequences. Nucleic Acids Res, 20, 1093-1099

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

38. Ettwiller, L., Paten, B., Ramialison, M. et al. (2007) Trawler: de novo regulatory motif discovery pipeline for chromatin immunoprecipitation. Nat Methods, 4, 563565

39. Euskirchen, G.M., Rozowsky, J.S., Wei, C.L. et al. (2007) Mapping of transcription factor binding regions in mammalian cells by ChIP: comparison of array- and sequencing-based technologies. Genome Res, 17, 898-909

40. Evan, G., Harrington, E., Fanidi, A. et al. (1994) Integrated control of cell proliferation and cell death by the c-myc oncogene. Philos Trans R Soc Lond B Biol Sci, 345, 269-275

41. Favorov, A.V., Gelfand, M.S., Gerasimova, A.V. et al. (2005) A Gibbs sampler for identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length. Bioinformatics, 21, 2240-2245

42. Fields, D.S., He, Y., Al-Uzri, A.Y. et al. (1997) Quantitative specificity of the Mnt repressor. JMol Biol, 271, 178-194

43. Fratkin, E., Naughton, B.T., Brutlag, D.L. et al. (2006) MotifCut: regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22, el50-7

44. Frith, M.C., Saunders, N.F., Kobe, B. et al. (2008) Discovering sequence motifs with arbitrary insertions and deletions. PLoS Comput Biol, 4, el000071

45. Fujioka, M., Miskiewicz, P., Raj, L. et al. (1996) Drosophila Paired regulates late even-skipped expression through a composite binding site for the paired domain and the homeodomain. Development, 122(9), 2697-2707

46. Gershenzon, N.I., Stormo, G.D. and Ioshikhes, I.P. (2005) Computational technique for improvement of the position-weight matrices for the DNA/protein binding sites. Nucleic Acids Res, 33, 2290-2301

47. Goodman, S.D., Velten, N.J., Gao, Q. et al. (1999) In vitro selection of integration host factor binding sites. JBacteriol, 181, 3246-3255

48. Guille, M.J. and Kneale, G.G. (1997) Methods for the analysis of DNA-protein interactions. Mol Biotech, 8, 35-52

49. Gupta, S., Stamatoyannopoulos, J.A., Bailey, T.L. et al. (2007) Quantifying similarity between motifs. Genome Biol, 8, R24

50. Hampshire, A.J., Rusling, D.A., Broughton-Head, V.J. et al. (2007) Footprinting: a method for determining the sequence selectivity, affinity and kinetics of DNA-binding ligands. Methods, 42, 128-140

51. Hannenhalli, S. (2008) Eukaryotic transcription factor binding sites-modeling and integrative search methods. Bioinformatics, 24, 1325-1331

52. Hannenhalli, S. and Wang, L.S. (2005) Enhanced position weight matrices usingmixture models. Bioinformatics, 21 Suppl 1, i204-12

53. Harr, R., Haggstrom, M. and Gustafsson, R (1983) Search algorithm for pattern match analysis of nucleic acid sequences. Nucleic Acids Res, 11, 2943-2957

54. Heinemeyer, T., Wingender, E., Reuter, I. et al. (1998) Databases on transcriptional regulation: TRANSFAC, TRRD and COMPEL. Nucleic Acids Res, 26, 362-367

55. Hertz, G.Z. and Stormo, G.D. (1999) Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics, 15, 563-577

56. Hertz, G.Z., Hartzell, G W, 3rd and Stormo, G.D. (1990) Identification of consensus patterns in unaligned DNA sequences known to be functionally related. ComputAppl Biosci, 6, 81-92

57. Hochheimer, A. and Tjian, R. (2003) Diversified transcription initiation complexes expand promoter selectivity and tissue-specific gene expression. Genes Dev, 17,1309-1320

58. Ji, H., Vokes, S.A. and Wong, W.H. (2006) A comparative analysis of genome-wide chromatin immunoprecipitation data for mammalian transcription factors. Nucleic Acids Res, 34, el46

59. Karin, M. (1990) Too many transcription factors: positive and negative interactions. New Biol, 2, 126-131

60. Keilwagen, J., Baumbach, J., Kohl, T. A. et al. (2009) MotifAdjuster: a tool for computational reassessment of transcription factor binding site annotations. Genome Biol, 10(5), R46

61. Kel-Margoulis, O.V., Kel, A.E., Reuter, I. et al. (2002) TRANSCompel: a database on composite regulatory elements in eukaryotic genes. Nucleic Acids Res, 30, 332-334

62. Khouiy, G. and Gruss, P. (1983) Enhancer elements. Cell, 33, 313-314 ICing, O.D. and Roth, F.P. (2003) A non-parametric model for transcription factor binding sites. Nucleic Acids Res, 31, el 16

63. Kolchanov, N.A., Ignatieva, E.V., Ananko, E.A. et al. (2002) Transcription Regulatory Regions Database (TRRD): its status in 2002. Nucleic Acids Res, 30, 312-317

64. Man, T.K. and Stormo, G.D. (2001) Non-independence of Mnt repressor-operator interaction determined by a new quantitative multiple fluorescence relative affinity (QuMFRA) assay. Nucleic Acids Res, 29, 2471-2478

65. Maniatis, T., Ptashne, M., Backman, K. et al. (1975) Recognition sequences of repressor and polymerase in the operators of bacteriophage lambda. Cell, 5, 109-113

66. Mardis, E.R. (2007) ChlP-seq: welcome to the new frontier. Nat Methods, 4, 613-614

67. Matys, V., Fricke, E., Geffers, R. et al. (2003) TRANSFAC: transcriptionalregulation, from patterns to profiles. Nucleic Acids Res, 31, 374-378

68. Matys, V., Kel-Margoulis, O.V., Fricke, E. et al. (2006) TRANSFAC and its module TRANSCompel: transcriptional gene regulation in eukaryotes. Nucleic Acids Res, 34, D108-10

69. McGinnis, S. and Madden, T.L. (2004) BLAST: at the core of a powerful and diverse set of sequence analysis tools. Nucleic Acids Res, 32, W20-5

70. Meng, X., Brodsky, M.H. and Wolfe, S.A. (2005) A bacterial one-hybrid system for determining the DNA-binding specificity of transcription factors. Nat Biotechnol, 23(8), 988-994

71. Mitchell, P.J. and Tjian, R. (1989) Transcriptional regulation in mammalian cells by sequence-specific DNA binding proteins. Science, 245, 371-378

72. Moens, C.B. and Selleri, L. (2006) Hox cofactors in vertebrate development. Dev Biol, 291, 193-206

73. Morozov, A.V. and Siggia, E.D. (2007) Connecting protein structure with predictions of regulatory sites. P roc Natl Acad Sei USA, 104, 7068-7073

74. Moses, A.M., Chiang, D.Y., Kellis, M. et al. (2003) Position specific variation in the rate of evolution in transcription factor binding sites. BMC Evol Biol, 3,19

75. Mueller, P.R. and Wold, B. (1989) In vivo footprinting of a muscle specific enhancer by ligation mediated PCR. Science, 246, 780-786

76. Mukherjee, S., Berger, M.F., Jona, G. et al. (2004) Rapid analysis of the DNA-binding specificities of transcription factors with DNA microarrays. Nat Genet, 36, 1331-1339

77. Mulligan, M.E., Hawley, D.K., Entriken, R. et al. (1984) Escherichia coli promoter sequences predict in vitro RNA polymerase selectivity. Nucleic Acids Res, 12, 789-800

78. Myers, E.W. and Miller, W. (1989) Approximate matching of regular expressions. Bull Math Biol, 51, 5-37

79. Newberg, L.A., Thompson, W.A., Conlan, S. et al. (2007) A phylogenetic Gibbssampler that yields centroid solutions for cis-regulatoiy site prediction. Bioinformatics, 23, 1718-1727

80. Newburger, D.E. and Bulyk, M.L. (2009) UniPROBE: an online database of protein binding microarray data on protein-DNA interactions. Nucleic Acids Res, 37, D77-82

81. Ng, P., Tan, J. J., Ooi, H.S. et al. (2006) Multiplex sequencing of paired-end ditags (MS-PET): a strategy for the ultra-high-throughput analysis of transcriptomes and genomes. Nucleic Acids Res, 34, e84

82. Noyes, M.B., Christensen, R.G., Wakabayashi, A. et al. (2008a) Analysis of homeodomain specificities allows the family-wide prediction of preferred recognition sites. Cell, 133, 1277-1289

83. Noyes, M.B., Meng, X., Wakabayashi, A. et al. (2008b) A systematic characterization of factors that regulate Drosophila segmentation via a bacterial one-hybrid system. Nucleic Acids Res, 36, 2547-2560

84. Oliphant, A.R., Brandl, C.J. and Struhl, K. (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, 2944-2949

85. Osada, R., Zaslavsky, E. and Singh, M. (2004) Comparative analysis of methods for representing and searching for transcription factor binding sites. Bioinformatics, 20,3516-3525

86. Ottolenghi, C., Uda, M., Crisponi, L. et al. (2007) Determination and stability of sex. Bioessays, 29, 15-25

87. Papatsenko, D. (2007) ClusterDraw web server: a tool to identify and visualize clusters of binding motifs for transcription factors. Bioinformatics, 23, 1032-1034

88. Papatsenko, D. and Levine, M. (2007) A rationale for the enhanceosome and other evolutionarily constrained enhancers. Curr Biology, 17, R955-7

89. Papatsenko, D.A., Makeev, V.J., Lifanov, A.P. et al. (2002) Extraction of functional binding sites from unique regulatory regions: the Drosophila early developmental enhancers. Genome Res, 12,470-481

90. Pavesi, G., Mereghetti, P., Mauri, G. et al. (2004) Weeder Web: discovery of transcription factor binding sites in a set of sequences from co-regulated genes. Nucleic Acids Res, 32, W199-203

91. Pawson, T. (1993) Signal transduction-^ conserved pathway from the membrane to the nucleus. Dev Genet, 14, 333-338

92. Philippakis, A.A., Qureshi, A.M., Berger, M.F. et al. (2008) Design of compact, universal DNA microarrays for protein binding microarray experiments. J Comput Biol, 15, 655-665

93. Pollard, D.A., Moses, A.M., Iyer, V.N. et al. (2006) Detecting the limits of regulatory element conservation and divergence estimation using pairwise and multiple alignments. BMC Bioinformatics, 7, 376

94. Ponomarenko, J.V., Orlova, G.V., Frolov, A.S. et al. (2002) SELEXJDB: a database on in vitro selected oligomers adapted for recognizing natural sites and for analyzing both SNPs and site-directed mutagenesis data. Nucleic Acids /^,,30(1), 195-199

95. Pribnow, D. (1975) Nucleotide sequence of an RN A polymerase binding site at an early T7 promoter. Proc Natl Acad Sci USA, 72, 784-788

96. Ptashne, M. and Gann, A. (1997) Transcriptional activation by recruitment. Nature, 386, 569-577

97. Pudimat, R., Schukat-Talamazzmi, E.G. and Backofen, R. (2005) A multiple-feature framework for modelling and predicting transcription factor binding sites. Bioinformatics, 21, 3082-3088

98. Reese, J.C. (2003) Basal transcription factors. Curr Opin Genet Dev, 13, 114118

99. Roeder, R.G. (1996) Nuclear RNA polymerases: role of general initiation factors and cofactors in eukaryotic transcription. Methods Enzymol, 273, 165-171

100. Roulet, E., Busso, S., Camargo, A.A. et al. (2002) High-throughput SELEX • SAGE method for quantitative modeling of transcription-factor binding sites. Nat Biotechnol, 20, 831-835

101. Rozanov, U.A. (1995) Probability Theory, Random Processes, and Mathematical Statistics. Kluwer Academic Publishers, Dordrecht (Netherlands)/Boston (MA)

102. Saffer, J.D., Jackson, S.P. and Annarella, M.B. (1991) Developmental expression of Spl in the mouse. Mol Cell Biol, 11, 2189-2199

103. Sandelin, A. and Wasserman, W. W. (2004) Constrained binding site diversity within families of transcription factors enhances pattern discovery bioinfonhatics. J Mol Biol, 338, 207-215

104. Sandve, G.K., Abul, O., Walseng, V. et al. (2007) Improved benchmarks for computational motif discovery. BMC Bioinformatics, 8, 193

105. Schneider, T.D., Stormo, G.D., Gold, L. et al. (1986) Information content of binding sites on nucleotide sequences. J Mol Biol, 188, 415-431

106. Shamovsky, I. and Nudler, E. (2008) New insights into the mechanism of heat shock response activation. Cell Mol Life Sci, 65, 855-861

107. Sharon, E., Lubliner, S. and Segal, E. (2008) A feature-based approach to modeling protein-DNA interactions. PLoS Comput Biol, 4, el000154

108. Singh, S.P. and Mishra, B.N. (2008) Prediction of MHC binding peptide using Gibbs motif sampler, weight matrix and artificial neural network. Bioinformation, 3,150.155

109. Sinha, S. and Torapa, M. (2003) YMF: A program for discovery of novel transcription factor binding sites by statistical overrepresentation. Nucleic Acids Res, 31, 3586-3588

110. Sinha, S., Blanchette, M. and Tompa, M. (2004) PhyME: a probabilistic algorithm for finding motifs in sets of orthologous sequences. BMC Bioinformatics, 5, 170

111. Stavrovskaia, E.D., Makeev, V. and Mironov, A.A. (2006) ClusterTree-RS: the binary tree algorithm for identification of co-regulated genes by clustering regulatory signals. Mol Biol (Mosk), 40, 524-532

112. Stormo, G.D. (1990) Consensus patterns in DNA. Methods Enzymol, 183, 211221

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

114. Stormo, G.D., Schneider, T.D. and Gold, L. (1986) Quantitative analysis of the relationship between nucleotide sequence and functional activity. Nucleic Acids Res, 14, 6661-6679

115. Stormo, G.D., Schneider, T.D., Gold, L. et al. (1982) algorithm to distinguish translational initiation sites in E. coli. Nucleic Acids Res, 10, 2997-3011

116. Thiesen, H.J. and Bach, C. (1990) Target Detection Assay (TDA): a versatile procedure to determine DNA binding sites as demonstrated on SP1 protein. Nucleic Acids Res, 18(11), 3203-3209

117. Thompson, J.D., Gibson, T.J. and Higgins, D.G. (2002) Multiple sequence alignment using ClustalW and ClustalX. Curr Protoc Bioinformatics, Chapter 2, Unit 2 3

118. Thompson, W., Conlan, S., McCue, L.A. et al. (2007) Using the Gibbs Motif Sampler for phylogenetic footprinting. Methods Mol Biol, 395, 403-424

119. Thompson, W., Rouchka, E.C. and Lawrence, C.E. (2003) Gibbs Recursive

120. Sampler: finding transcription factor binding sites. Nucleic Acids Res, 31, 3580-3585

121. Tornaletti, S. and Pfeifer, G.P. (1995) UV light as a footprinting agent: modulation of UV-induced DNA damage by transcription factors bound at the promoters of three human genes. J Mol Biol, 249, 714-728

122. Treisman, R., Marais, R.' and Wynne, J. (1992) Spatial flexibility in ternary complexes between SRF and its accessory proteins. EMBOJ, 11, 4631-4640

123. Tuerk, C. and Gold, L. (1990) Systematic evolution of ligands by exponential enrichment: RNA ligands to bacteriophage T4 DNA polymerase. Science, 249, 505510

124. Vanet, A., Marsan, L., Labigne, A. et al. (2000) Inferring regulatory elements from a whole genome. An analysis of Helicobacter pylori sigma(80) family of promoter signals. J Mol Biol, 297, 335-353

125. Velculescu, V.E., Zhang, L., Vogelstein, B. et al. (1995) Serial analysis of gene expression. Science, 270, 484-487

126. Venter, J.C., Adams, M.D., Myers, E.W. et al. (2001) The sequence of the human genome. Science, 291, 1304-1351

127. Warren, C.L., Kratochvil, N.C.S., Hauschild, K.E. et al. (2006) Defining the sequence-recognition profile of DNA-binding molecules. Proc Natl Acad Sci U SA, 103(4), 867-872

128. Wasserman, W.W. and Sandelin, A. (2004) Applied bioinformatics for the identification of regulatory elements. Nat Rev Genet, 5, 276-287

129. Waterman, M.S. (1986) Multiple sequence alignment by consensus. Nucleic Acids Res, 14, 9095-9102

130. Wei, C.L., Wu, Q., Vega, V.B. et al. (2006) A global map of p53 transcription-factor binding sites in the human genome. Cell, 124, 207-219

131. Werner, M.H. and Burley, S.K. (1997) Architectural transcription factors: proteins that remodel DNA. Cell, 88, 733-736

132. Wheeler, D.A., Srinivasan, M., Egholm, M. et al. (2008) The complete genome of an individual by massively parallel DNA sequencing. Nature, 452, 872-876

133. Xing, E.P., Wu, W., Jordan, M.I. et al. (2003) LOGOS: a modular Bayesian model for de novo motif detection. Proc IEEE Comput Soc Bioinform Conf, 2, 266276

134. Yudkovsky, N,, Ranish, J. A. and Hahn, S. (2000) A transcription reinitiation intermediate that is stabilized by activator. Nature, 408(6809), 225-229

135. Zhang, M.Q. and Marr, T.G. (1993) A weight array method for splicing signal analysis. ComputAppl Biosci, 9,499-509

136. Zhang, Y., Shin, H., Song, J.S. et al. (2008) Identifying positioned nucleosomes with epigenetic marks in human from ChlP-Seq. BMC Genomics, 9, 537

137. Zhao, X., Huang, H. and Speed, T.P. (2005) Finding short DNA motifs using permuted Markov models. J Comput Biol, 12, 894-906