Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ент начинают превышать соответствующие значения фонового. В этой области находятся часто встречающиеся слова (то есть слова с большой величиной count и, соответственно, hCount), которых в реальных последовательностях больше, чем в сгенерированных, то есть эти слова перепредставлены. Пики гистограммы в области глобального максимума соответствуют словам с самопересекающейся структурой (например, ATGCGATG)
Далее строится отношение гистограмм реального и фонового распределений (рис. 11). Пороговое значение (xCount) для отбора перепредставленных слов-кандидатов выставляется в наименьшей точке, где отношение реального распределения к фоновому превышает 1.
В данном подходе при построении фонового распределения учитываются только частоты нуклеотидов в исходных данных, но не другие особенности, которые должны моделироваться СММ более высокого порядка. Предположим, существует слово, вероятность встретить которое в сгенерированных данных очень мала. В результате, для того, чтобы это слово оказалось перепредставленным, ему и его соседям достаточно встретиться в исходных данных всего несколько раз. Такие редко встречающиеся слова (то есть слова с маленькой величиной count и, соответственно, hCount) выделяются в левой части реального распределения (область около 45-50), где отношение распределений также превышает 1. Но они не являются искомыми мотивами. Поэтому было введено условие, что пороговое значение xCount должно всегда быть правее максимума фонового распределения.
Рис. 11. Гистограмма отношения реального распределения частот вхождений слов к фоновому. Пороговое значение выбрано равным 61
Далее составляется список реальных слов-кандидатов (т.е. участков начальных последовательностей), соответствующих словам из словаря, величина count которых больше порогового значения xCount. Если два перепредставленных слова перекрываются на реальной последовательности, то в список слов-кандидатов добавляется и их объединение (большей длины). Эта операция позволяет строить словарь из коротких слов (например, 8 нуклеотидов), что существенно экономит память и ускоряет работу алгоритма, а затем объединять их до нужной длины. Кроме того, такой подход в какой-то мере позволяет решить проблему поиска мотива неизвестной длины.
Каждое слово-кандидат используется для определения эмиссионных и переходных вероятностей СММ.
2.1.3 Структура СММ
Структура СММ базового алгоритма содержит следующие состояния:
Begin - молчащее (т.е. не имеющее эмиссионных вероятностей) состояние, определяющее начало работы.
Background (bckg) - состояние фона. Начальные эмиссионные вероятности для всех нуклеотидов равны 0.25.
Site - молчащее состояние, определяющее начало сайта на последовательности.
Pos 1, pos 2 тАж pos n - состояния, определяющие позиции сайта.
End - молчащее состояние, определяющее конец работы.
Рис. 12. Схема СММ базового алгоритма
На рисунке 12 изображена схема СММ для базового алгоритма, стрелками показаны возможные переходы между состояниями СММ. Переходные вероятности между состояниями pos 1, pos 2тАжpos n (позиции в сайте) равны 1 и не меняются в процессе обучения. Начальные эмиссионные вероятности состояний pos 1 тАж pos n задаются в соответствии с буквой в последовательности слова-кандидата и размываются псевдокаунтами. Такая СММ позволяет найти в последовательности произвольное число сайтов.
.1.4 Обучение СММ и применение для поиска сайтов
Обучение СММ производится с помощью алгоритма Витерби. В результате работы данного алгоритма мы получаем наиболее вероятную разметку последовательности на состояния site и background. Общая схема процесса обучения такова: каждая последовательность размечается алгоритмом Витерби, в соответствии с новым набором полученных сайтов изменяются эмиссионные вероятности состояний сайта. Проводится несколько итераций обучения. В результате, для каждого слова-кандидата мы получаем список возможных сайтов в последовательностях и обученную PWM. По ней для каждого кандидата рассчитывается его информационное содержание, а для каждого сайта - его вес.
.2 Модификации алгоритма
Базовый алгоритм был модифицирован так, чтобы можно было искать мотивы со сложной структурой, такой как палиндром, прямой повтор и инвертированный повтор.
.2.1 Начальная обработка последовательностей
Известно, что в последовательностях ДНК существуют так называемые области низкой сложности [94] - чаще всего это высоко периодичные AT-богатые участки. Наличие таких участков в начальных последовательностях приводит к появлению множества бессмысленных перепредставленных слов-кандидатов и завышению порогового значения. В нашей программе мы применили процедуру маскировки областей низкой сложности до начала основной работы алгоритма. После составления словаря и получения слов-кандидатов обучение СММ проводится на полных исходных последовательностях.
.2.2 Модификация процедуры поиска слов-кандидатов
Для того, чтобы сократить время работы алгоритма, процедура поиска слов-кандидатов была модифицирована. Модификация процедуры поиска слов-кандидатов описана на примере сайта со структурой типа прямой повтор.
В начале работы в исходных последовательностях ищутся все существующие повторы с плечом заданной длины и заданным количеством допустимых замен между плечами.
Для построени?/p>