Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
еди всех возможных выходных значений. Наблюдаемое значение в момент времени t обозначим через y(t). Между состояниями определены переходные вероятности. Для СММ 1-го порядка состояние x(t) в момент времени t зависит только от состояния x (t ? 1) в предыдущий момент времени. Это называется свойством Маркова.
Рис. 9. Общая структура СММ
Вероятность увидеть последовательность значений длины L равна
Здесь сумма пробегает по всем возможным последовательностям скрытых узлов . Метод подсчёта значений P(Y) полным перебором - очень трудоёмкий для многих реальных задач, где количество возможных состояний очень велико. Но существуют эвристические алгоритмы, позволяющие решить эту задачу за приемлемое время. К таким алгоритмам относятся Витерби и вперед-назад (forward-backward).
Алгоритм вперед-назад вычисляет P(Y) для конкретной последовательности наблюдаемых значений и восстанавливает последовательность состояний по последовательности наблюдаемых значений (разметка). СММ можно представить в виде многодольного графа, где узлы соответствуют состояниям, а доли графа - позициям в последовательности наблюдаемых значений. Тогда разметка последовательности наблюдаемых значений в терминах СММ есть путь в данном графе. Основная идея алгоритма заключается в следующем. Вероятность того, что путь пройдет через данный узел графа, складывается из всех путей, которые ведут в данную точку из начальной и из конечной. Алгоритм включает в себя две стадии: проход вперед и проход назад. При проходе вперед для каждой точки вычисляется вероятность прийти в эту точку из начальной, а при проходе назад - из конечной. Далее для каждой позиции можно сравнить вероятности всех состояний и выбрать наиболее вероятное.
В данной работе для обучения СММ использовался алгоритм Витерби, который находит наиболее вероятную последовательность состояний (путь ) для конкретной последовательности наблюдаемых значений . Алгоритм рекурсивен, необходимо наличие начального и конечного состояний.
Пусть дана СММ с набором состояний X, эмиссионными вероятностями ei, в состоянии xi и переходными вероятностями ai,j из i-го состояния в j-ое, . Требуется найти наиболее вероятную последовательность состояний
Пусть вероятности наиболее вероятного пути в состояние k с наблюдаемым значением i известны для всех k. Тогда
Полный алгоритм:
Инициализация (i = 0):, для k > 0.
Рекурсия (i = 1тАжL):
Терминация:
Обратный проход (i = LтАж1):
Основная практическая проблема в применении алгоритмов Витерби и вперед-назад заключается в том, что перемножение многих вероятностей дает малые числа, из-за чего могут возникать потери точности. По этой причине чаще всего такие алгоритмы выполняются в логарифмическом пространстве, где произведения вероятностей превращаются в суммы логарифмов вероятностей.
2. Материалы и методы
.1 Базовый алгоритм
.1.1 Общая схема
В качестве базового алгоритма был использован алгоритм поиска непалиндромных мотивов определенной длины, разработанный в лаборатории биоинформатики ФББ. Алгоритм берет на вход последовательности ДНК, в которых необходимо найти мотив (набор сайтов). Поиск мотива осуществляется в два основных этапа:
1.Поиск перепредставленных слов-кандидатов определенной длины в последовательностях
2.Обучение СММ, созданных на основе слов-кандидатов.
.1.2 Поиск слов-кандидатов
В качестве исходных параметров на этом этапе используется длина слова-затравки и количество допустимых замен.
Сначала создается словарь из всех возможных слов заданной длины. Соседями в таком словаре считаются слова, количество замен между которыми (расстояние по Хэммингу) не превышает допустимый уровень. Затем для слов из словаря считается количество вхождений в последовательности с заданным количеством замен. Если в последовательности найдены слова из словаря, то счетчик вхождений увеличивается не только для данного слова, но и для всех его соседей. Эта операция проводится для реальных последовательностей и для случайно сгенерированных последовательностей такой же длины с теми же частотами нуклеотидов. Таким образом, мы получаем реальную и фоновую частоты вхождений для каждого слова из словаря с заданным уровнем замен. Для того чтобы получить достоверные фоновые частоты, производится несколько (около 10) генераций случайных последовательностей.
Далее по полученным данным для реального и фонового распределений вычисляется величина hCount (см. ниже), а затем строится частотная гистограмма для этой величины (рис. 10).
где count - количество вхождений слова, min - минимальное значение гистограммы, step - шаг гистограммы, scale - шкала гистограммы, dictsize - размер начального словаря.
Рис. 10. Гистограмма фонового и реального распределений величины hCount. Здесь n(hCount) - количество слов из словаря с данным значением hCount, foreground - реальное распределение, background - фоновое распределение, foreground (trend) и background (trend) - линии тренда для соответствующих распределений
Нетрудно заметить, что в правой части гистограммы (в области около 60-70) значения n(hCount) реального распределения в какой-то мо?/p>