Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? и реального, и фонового распределений словарь составляется только из слов, действительно существующих в последовательностях (реальных или сгенерированных соответственно). Соседи также выбираются только из списка существующих слов. В данном подходе частота встречаемости рассматривается как случайная величина, поэтому возможно оценить ее распределение по неполному множеству слов. Такая процедура сильно сокращает время работы алгоритма и экономит используемую память, особенно в случае небольших выборок начальных данных. В случае больших выборок, время работы модифицированного и базового алгоритмов сопоставимы.
В процессе тестирования было замечено, что для маленьких выборок начальных данных (около 5 последовательностей длины 200), пороговое значение иногда выбирается неверно по случайным причинам из-за недостаточного количества информации. Для решения этой проблемы пороговое значение уменьшается на величину , где N - количество последовательностей в начальной выборке, - коэффициент поправки, вычисленный экспериментально - методом Монте-Карло с 10000 итераций. В случае больших выборок сдвиг на такую величину не оказывает большого влияния на результат, но помогает восполнить недостаток информации в случае маленьких выборок (рис. 13).
Рис. 13. Гистограммы реального (foreground) и фонового (background) распределений со сдвинутым пороговым значением (xCount) для выборки из 25 последовательностей длины 200 нуклеотидов
В последовательностях ДНК практически не встречаются сайты связывания транскрипционных факторов и другие регуляторные элементы, состоящие только из аденинов и тиминов, так как подобные участки часто встречаются в последовательностях и не являются функциональными. В связи с этим, слова-кандидаты выбираются таким образом, чтобы в них обязательно присутствовал хотя бы один цитозин или гуанин. В противном случае при обучении СММ эти слова могут получить серьезное преимущество из-за присутствия в последовательностях областей низкой сложности.
В результате слово-кандидат выбирается по следующим критериям:
1.В исходных последовательностях присутствует повтор, соответствующий данному слову
.Слово перепредставлено в исходных последовательностях (частота вхождений соответствующего ему слова из словаря выше порогового значения)
.В составе слова должна быть хотя бы одна буква С или G.
Перекрывающиеся слова-кандидаты не рассматриваются.
.2.3 Кластеризация слов-кандидатов
Так как слова-кандидаты - это реальные участки начальных последовательностей, среди них встречаются идентичные или очень похожие. Чтобы не создавать несколько одинаковых СММ, слова-кандидаты кластеризуются с помощью алгоритма, использующего бинарное дерево. В одном кластере могут находиться слова-кандидаты, отличающиеся в одной или двух конкретных позициях. Кластеры представлены в виде PWM, составленной по входящим в него последовательностям. Рассматриваются только кластеры, содержащие более двух слов.
.2.4 Модификация СММ
Помимо уже известных состояний, модифицированная СММ содержит также состояния:
Spacer - молчащее состояние, определяющее начало промежутка между плечами структуры
Spacer 1, spacer 2 тАж spacer n - состояния, определяющие позиции спейсера
Pos 1, pos 2 тАж pos n - состояния, определяющие позиции второго плеча мотива
Рис. 14. Схема модифицированной СММ
На рисунке 14 показаны возможные переходы между состояниями модифицированной СММ. Такая схема СММ подходит для любой структуры мотива. Переходные вероятности между состояниями site, pos 1 тАж pos n и pos 1 тАж pos n равны 1 и не меняются в процессе обучения. Эмиссионные вероятности состояний pos 1 тАж pos n задаются в соответствии с PWM, составленной по кластеру слов-кандидатов. В случае повторов эмиссионные вероятности состояний pos 1 тАж pos n равны вероятностям состояний pos 1 тАж pos n соответственно, в случае палиндромов и инвертированных повторов - вероятностям симметричных (комплементарных) состояний (pos n тАж pos 1). Из молчащего состояния spacer возможен переход сразу в следующее плечо сайта, что позволяет найти мотивы без спейсера. Из конечного состояния второго плеча сайта возможен обратный переход в спейсер, что позволяет найти мотив, состоящий больше, чем из 2-х плеч. Такое иногда встречается в случае повторов.
2.2.5 Модификация процесса обучения
В процессе обучения СММ, эмиссионные вероятности в состояниях pos 1 тАж pos n и pos 1 тАж pos n обучаются одновременно: после каждой итерации обучения эмиссии соответствующих позиций двух плеч усредняются.
.2.6 Уточнение мотива
Результатом работы алгоритма являются список найденных сайтов и построенная по ним PWM. Как правило, найденный мотив содержит некоторую долю ложно предсказанных сайтов. Для уточнения мотива был введен порог - минимальный вес сайта. Все сайты с весом ниже порога удаляются из мотива, после чего PWM перестраивается.
.3 Веб-ресурс
Для обеспечения открытого доступа к алгоритму был разработан веб-интерфейс
Страница формы (рис. 15) содержит следующие поля: файл с начальными данными, структура искомого сайта (прямой повтор, инвертированный повтор или палиндром), минимальная и мак