Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
>,jk - вероятность того, что искомый мотив начинается в j позиции в последовательности k, а f (i, ?) - вероятность символа ? в колонке i для каждого символа из алфавита и 1? i ?l. В процессе работы алгоритма происходит переопределение g и f до тех пор, пока f не будет мало изменяться. Это переопределение происходит с использованием байесовских методик.
Алгоритм MEME [55], созданный Бейли и Элканом, применяет стратегию EM для поиска мотивов. В алгоритме MEME используются три новаторские идеи для поиска мотивов. Во-первых, участки начальных последовательностей используются как отправные точки для алгоритма. Это позволяет повысить скорость работы алгоритма и вероятность нахождения глобально оптимального решения. Во-вторых, отменено требование о том, что в каждой последовательности должен встречаться в точности один сайт. В-третьих, за счет особенностей вероятностной модели, появилась возможность одновременно находить в одном наборе данных сразу несколько мотивов.
Метод Gibbs sampling
Gibbs sampling представляет собой довольно широко используемый стохастический аналог метода максимизации ожидания. Этот алгоритм ищет максимальное значение функции от нескольких переменных. Основная идея алгоритма заключается в следующем. На каждом шаге случайным образом выбирается одна переменная, и ее значение меняется при фиксированных значениях других переменных. Если это изменение приводит к возрастанию целевой функции, переменная принимает выбранное значение. Процесс повторяется до тех пор, пока значение функции не перестанет значимо меняться.
Метод Gibbs sampling был разработан Геманом и Геманом [56] для восстановления изображений. Впервые в биоинформатике этот метод был применён для построения множественного выравнивания Лоренсом и др. [57]. Различные модификации этого метода часто применяются для поиска слабых мотивов. Gibbs sampling - это подход, использующий марковские цепи и метод Монте-Карло (MCMC). Для расчета вероятностей на данном шаге марковские цепи используют вероятности, полученные на предыдущем шаге. Суть метода Монте-Карло состоит в том, что выбор следующего шага осуществляется случайно с вероятностью, зависящей от текущего состояния. В самой простой версии метода Gibbs sampling мы ищем лучший консервативный неразрывный мотив длины l в виде PWM. Предполагается, что искомый сайт встречается во всех последовательностях.
Поиск осуществляется в несколько итераций. Сначала случайно выбирается по одному слову длины l из каждой последовательности. Эти слова формируют начальное множество вхождений мотива. Обозначим позицию слова в i-й последовательности через Oi.
Итерационный шаг:
- Берём одну последовательность i. Обычно последовательности выбирают по очереди, хотя возможны и другие варианты, например, случайный выбор. Существенно, что у всех последовательностей шансы быть выбранными равны.
- Строим PWM по выбранным словам из всех последовательностей, кроме i. Берем каждое слово длины l из i-ой последовательности и вычисляем Байесовскую вероятность того, что данное слово могло бы быть порождено PWM, а не фоном.
- Разыграем следующее Oi случайно из всех слов в последовательности i длины l, используя полученное распределение вероятностей.
- Заменяем Oi на Oi.
Итерационный шаг повторяется до тех пор, пока набор слов не станет неизменным.
Дополнения к методу Gibbs sampling
Рот и др. [58] создали на основе метода Gibbs sampling алгоритм поиска мотивов AlignACE (Aligns Nucleic Acid Conserved Elements). Основные отличия от оригинального алгоритма Gibbs sampling состоят в следующем. Во-первых, фоновые частоты нуклеотидов фиксированы и соответствуют частотам в геноме (например, 62% A+T в случае дрожжей). Во-вторых, на каждом шаге алгоритм ищет мотив по двум цепям одновременно, и перекрывающиеся сайты исключены, даже если они находятся на разных цепях. В-третьих, в AlignACE используется метод MAP (maximum a posteriori log-likelihood) для оценки качества полученных в результате мотивов. Это мера того, что мотив встретился в последовательности не случайно. Важной особенностью метода MAP является то, что в нем учитывается не только распределение частот нуклеотидов в рассматриваемых геномах, но и некоторые другие особенности (например, А-богатые участки в ДНК дрожжей). В результате, мотивы, порожденные такими особенностями генома, исключаются из конечных результатов.
Позднее, Хьюгес и др. [59] использовали AlignACE для поиска мотивов в наборе функционально важных генов дрожжей. Вместо MAP для оценки найденных мотивов в данном случае использовался усовершенствованный метод. Учитывались особенности конкретных начальных данных и выделялись те мотивы, которые более вероятно являются реальными сайтами, чем случайными мусорными последовательностями.
Фиджс и др. [60] разработали алгоритм MotifSampler, использующий алгоритм Gibbs sampling со следующими изменениями. Во-первых, наличие только одного сайта в последовательности более не является обязательным. Во-вторых, в алгоритме используются марковские цепи высокого порядка для построения фоновой модели. Алгоритм применяли для поиска регуляторных мотивов в геномах бактерий и некоторых растений.
На основе алгоритма Gibbs sampling, Лью и др. [61] разработали алгоритм BioProspector, обрабатывающий промоторные области перед совместно регулируемыми генами. Основные отличия от оригинального Gibbs sampling состоят в следующем. Во-первых, в нем использ