Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ать только для поиска довольно коротких консервативных мотивов. Позднее, ван Хельден и др. усовершенствовали свой алгоритм, добавив в него возможность искать мотивы, состоящие из двух частей, разделенных спейсером [41]. Так как спейсер может быть различным для одного мотива, длину промежутка можно варьировать от 0 до 16. Частота такого двойного мотива может быть вычислена как сумма частот двух плеч или же как общая частота двойного мотива. Основным недостатком алгоритма ван Хельдена является то, что в нем ищутся точные вхождения слов, то есть не учитывается вариабельность сайтов.
Томпа [42] обратил внимание на эту проблему, и представил свой алгоритм, использующий словарную технику, для поиска коротких мотивов в последовательностях ДНК. В процессе его работы для каждого отрезка s длины k рассчитывается значение Ns - количество вхождений слова s в исходные последовательности с допустимым количеством замен. Также рассчитывается значение Ns, вычисленное для случайно сгенерированной последовательности той же длины. Мерой того, является ли s мотивом, считается разность Ns - Ns.
В дальнейших работах этот подход был усовершенствован. Пусть Х - отдельная случайная последовательность длины L. Фоновая частота каждого нуклеотида полагается равной 0.25, или же вычисляться по начальному набору данных. Предположим, что ps - это вероятность того, что Х содержит хотя бы одно слово s длины k или же любого его соседа (то есть слово, отличающееся в нескольких позициях). Если предположить, что в наборе из N случайных последовательностей длины L последовательности независимы, предполагаемое количество встреч слова s и его соседей в этом наборе есть , стандартное отклонение равно .
Тогда
,
где - z-score или отклонение в стандартных единицах. Величина имеет стандартное нормальное распределение и позволяет сравнивать различные мотивы. Томпа предложил эффективный алгоритм оценки , использующий марковские модели.
Используя подобный подход, Синха и Томпа [43, 44] разработали алгоритм YMF (Yeast Motif Finder), в котором для расчета фонового распределения частот последовательности генерируются с помощью марковской модели. Для определения параметров модели используются все существующие последовательности ДНК дрожжей. Алгоритм возвращает мотивы с наибольшей величиной z-score. Авторы протестировали свой алгоритм на выборках из геномов дрожжей и показали его высокую эффективность.
Ванет и др. использовали суффиксные деревья для представления набора последовательностей при создании алгоритма для поиска единичных мотивов в полных геномах бактерий [45]. Марсан и Сагот [46] добавили в этот алгоритм поиск комбинаций мотивов. Представление набора последовательностей в виде суффиксного дерева давало огромное количество возможных решений, но, несмотря на это, методика оказалась эффективной.
Существуют и другие алгоритмы, использующие суффиксные деревья и их вариации, такие как Weeder и MITRA (Mismatch Tree Algorithm), созданные Павеси и др. [47] и Эскиным и Певзнером [48] соответственно, а также алгоритмы, использующие словарные техники совместно с графовыми методиками, такие как WINNOWER [49] и cWINNOWER [50].
Вероятностные алгоритмы
Одним из первых вероятностных методов поиска сайтов связывания транскрипционных факторов стал вероятностный алгоритм Хертца и др. [51]. Он является жадным и ищет мотив, представленный в виде PWM, с наибольшим информационным содержанием. Предполагается, что каждая исходная последовательность содержит ровно один сайт. Позднее этот алгоритм был усовершенствован. В его последней версии (Consensus), разработанной Хертцем и Стормо [52], используется следующий метод. Строится PWM по одному случайному слову длины l. Далее по очереди из каждой последовательности выбирается слово, имеющее максимальный вес по PWM и добавляется к исходному слову. После каждого добавления выбирается набор слов с наибольшим информационным содержанием. По полученным словам PWM перестраивается.
Большинство вероятностных алгоритмов поиска мотивов используют эвристические методы, такие как метод максимизации ожидания и Gibbs sampling, а также дополнения к ним.
Метод максимизации ожидания
Одним из широко известных методов оценки параметров вероятностных моделей, позволяющих эффективно работать с большими объемами данных, является EM-алгоритм. Его название происходит от слов expectation-maximization, что переводится как ожидание-максимизация. Это связано с тем, что каждая итерация содержит два шага: вычисление математических ожиданий (expectation) и максимизацию (maximisation). Алгоритм основан на методике итеративного вычисления оценок максимального правдоподобия, предложенной в 1977 г. [68].
EM-алгоритм впервые был применен для поиска мотивов Лоренцем и Рейлли [54]. Их алгоритм - это дополнение к жадному алгоритму Хертца и др. [51]. Первоначально этот алгоритм был разработан для поиска белковых мотивов, но он также может использоваться и для поиска в последовательностях ДНК. Метод не требует никакого выравнивания сайтов в последовательностях, но изначально предполагает, что каждая из них включает только один сайт. Набор сайтов находится методом, описанным выше (см. обзор литературы, вероятностные модели). Неточность в расположении сайтов устраняется с помощью метода максимизации ожидания, работающего следующим образом. Пусть g