Алгоритмы, применяемые при работе со скрытыми моделями Маркова

Рассмотрим алгоритмы, применяемые при работе со скрытыми моделями Маркова.

Прямое решение задачи б) потребовало бы произвести перебор всех возможных путей, но графу скрытой модели Маркова, удовлетворяющих исследуемой последовательности состояний, с расчетом вероятности каждого пути по формуле.

и последующим выбором наиболее вероятного пути. Сложность такого решения растет экспоненциально с увеличением длины последовательности состояний и может быть выражена как 0(N^T). Решением проблемы стало использование схем динамического программирования (см. далее).

Алгоритм Витерби.

Очевидно, что решать задачу определения наиболее вероятной последовательности состояний модели для данной последовательности символов прямым способом бессмысленно. Однако тот факт, что система обладает «памятью» лишь на одну позицию назад^[1], что в некотором смысле аналогично «локальности» оценочной функции при выравнивании последовательностей, позволяет нам применить техники динамического программирования для создания более эффективного алгоритма. Этот алгоритм называется алгоритмом Витерби и состоит из следующих шагов (рис. 2.16):

• 1) в начальном состоянии имеем пустой граф состояний для каждой позиции в последовательности и начальную «пустую» вершину г>_нач;
• 2) для каждой вершины i-го столбца вершин на графе, начиная с первого, рассчитываем значение переменной v, а именно вероятность перейти в данную вершину и сгенерировать символ x-_v при этом отталкиваясь от максимального значения вероятности в предыдущем столбце:

Так же как и в случае алгоритмов выравнивания, запоминаем, откуда пришло в данную вершину максимальное значение вероятности;

3) пройдя таким образом все столбцы, отметим наибольшую вероятность в последнем столбце. Из этой вершины, следуя по ранее сделанным отметкам в обратном порядке, мы можем восстановить наиболее вероятный путь по графу нашей модели.

Рис. 2.16. Граф выполнения алгоритма Витерби:

стрелками показаны примеры опроса вершин Из графа алгоритма очевидно, что мы должны обработать Т столбцов по N вершин и для каждой из вершин произвести N вычислений. Таким образом, алгоритм имеет вычислительную сложность 0(Т№).

Еще один аспект реализации этого алгоритма связан с тем, что при произведении вероятностей мы можем получить очень маленькие величины, что часто нежелательно ввиду возможного выхода за пределы машинного представления значения. Решением в данном случае является замена в формуле (2.16) произведения вероятностей на сумму их логарифмов:

Прямой и обратный алгоритмы. Отличие задачи а) от задачи б) состоит в том, что нас интересует не столько сама последовательность состояний, через которую проходит модель, сколько сумма вероятностей тех путей, но модели, которые способны дать, т. е. сгенерировать, с вероятностью, отличной от нуля, некоторую последовательность символов X. Как и в случае с задачей б), имеется прямой путь решения, который заключается в нахождении всех путей, способных сгенерировать последовательность X, и суммировании их вероятностей. Сложность такого алгоритма растет экспоненциально с увеличением длины последовательности 0(Д7), что неприемлемо. Для решения этой задачи эффективным способом известно два алгоритма: прямой (Forward algorithm) и обратный (Backward algorithm). Алгоритмы несколько похожи между собой и, так же как и алгоритм Витерби, являются алгоритмами динамического программирования.

Прямой алгоритм использует граф, аналогичный графу алгоритма Витерби, и такую же схему обхода вершин, однако в данном случае для каждой вершины мы рассчитываем значение переменной /_} (г):

т.е. вероятность для рассматриваемой системы, сгенерировав фрагмент последовательности от х_х до Xj, оказаться в состоянии j. Для того чтобы рассчитать данную вероятность, достаточно формулу (2.16) заменить на.

т.е. на сумму произведения вероятности пути до каждой из вершин (к от О до N) предыдущего (г — 1) столбца на вероятность перехода к данной вершине (a_kj), умноженную на вероятность сгенерировать нужный (х,) символ из данного состояния (ej (х)). Результатом работы алгоритма будет сумма вероятностей в последнем (i = Т) столбце. Вычислительная сложность алгоритма такая же, как и у алгоритма Витерби.

Обратный алгоритм отличается от прямого тем, что осуществляет проход, но последовательности сгенерированных символов в обратную сторону (от конца к началу (рис. 2.17)). Таким образом, на каждом шагу алгоритма мы рассчитываем значение другой переменной b/i):

т.е. вероятность, начав из состояния системы у в момент г, сгенерировать суффикс x_{j + i}, x_{j + 2},…, х_т последовательности ХТ. В этом случае расчет производится по формуле.

Следует отметить, что описанная выше модификация алгоритма Витерби для использования логарифмов вероятностей не может быть применена к прямом}' и обратному алгоритмам, поскольку мы не только перемножаем вероятности, но и суммируем их. Однако если мы воспользуемся функцией экспоненты и формулой:

Расчет параметров для скрытых моделей Маркова. Напомним, что в случае марковских цепей мы рассчитывали параметры а, _; по формуле (2.15), основываясь на наблюдаемых парах событий. В случае скрытых моделей Маркова мы имеем дело с двумя различными случайными процессами и можем произвести расчет параметров о, _; и с_к(х,) по формулам.

то уравнения (9) и (11) можно переписать следующим образом:

Рис. 2.17. Граф выполнения обратного алгоритма:

стрелками показаны примеры опроса вершин где Ej (x) — количество раз, когда, оказавшись в г-м состоянии, система генерировала некоторый символ х; сумма в знаменателе означает суммирование по всему количеству сгенерированных символов для г-го состояния.

Как видно из формул, рассчитать параметры системы мы можем только в том случае, когда нам известны некоторый набор изменений состояния системы и соответствующий им набор сгенерированных символов. В примере модели анализа трансмембранных белков это будет информация о структуре известных трансмембранных белков, а точнее, о том, являются ли соседние остатки трансмембранными или они относятся к фрагментам разных типов, что соответствует количеству пар остатков А_{т ш}, А_ш ео Аес, тм ^и Ацс, ес ^в аминокислотных последовательностях, и информация о типе гидрофобное™ данного остатка с учетом типа фрагмента (Е_тм (Ю> Е_тм (L), Де|с (II) и Еёс (О);

В ряде случаев при недостаточной выборке наблюдаемых изменений состояния системы и (или) генерации символов, чтобы избежать нулевых значений вероятностей, возможно использование скорректированных значений количества наблюдений и Е_к (b):

Наиболее простым случаем такой коррекции можно считать коррекцию Лапласа, при этом r_{/ ;}— = r_k (b) = 1, что интуитивно можно воспринимать как добавление фона равномерного распределения. Если же априори подразумевается другой закон распределения этих параметров, то имеет смысл добавлять «псевдозначения» (pseudo-counts) r_x j и r_k(b), соответствующие этому закону распределения¹.

Настройка параметров скрытых моделей Маркова обучением. Рассчитать параметры модели мы можем только в том случае, если нам известны наборы состояний системы и соответствующие им сгенерированные наборы символов, однако на практике часто встречаются ситуации, когда исследователю доступны только генерируемые символы, а информация о состоянии системы, из которой эти символы были сгенерированы, недоступна. Введем обозначение Х^¹), Х (^[2][3] …, Х<") — п наборов ранее сгенерированных символов с длинами L (^[3] соответственно. В результате задача обучения системы на основе набора символов Х^¹), Х (^[3] …, Х<'^?), обычно такой набор называют тренировочным (training set), формулируется как задача нахождения таких параметров системы е_к(Ь)), чтобы для всех последовательностей тренировочного набора вероятность быть сгенерированными становилась максимальной:

На самом деле проблема нахождения глобально-оптимальных значений параметра 0 является ХР-полной^[3], поэтому обычно обучение производят алгоритмом Баума — Велша (Baum — Welch), который осуществляет поиск локального оптимального решения. Рассмотрим этот алгоритм:

1) назначаем случайные значения для параметра 0;

2) рассчитываем ожидаемое число переходов системы из состояния k в состояние / для тренировочного набора.

3) рассчитываем ожидаемое число генераций символа b из состояния k:

• 4) на основании рассчитанных значений А_м и E_k(b) получаем новый набор параметров 0;
• 5) повторяем пункты 2—4, пока изменение оценочной функции оптимальности параметров Score (Х^ X С).X (*) | (c)) не станет меньше некоторого заранее заданного параметра в:

Ввиду того что описанный выше алгоритм производит поиск локального максимума оценочной функции, то рекомендуется производить определение оптимальных параметров несколько раз, используя различные начальные наборы значений 0 (пункт 1 алгоритма). Если результаты нескольких тренировок будут давать близкие значения параметров, то можно предполагать, что найден глобальный максимум оценочной функции.

Скрытые модели Маркова широко применяются для моделирования практически любых проблем биоинформатики. Такой популярности способствовала, с одной стороны, простота концепции наряду с возможностью автоматической настройки параметров, а с другой — тот факт, что сами модели ориентированы на генерацию последовательностей символов со скрытыми закономерностями распределения, что отвечает способу представления биологических полимеров, принятому в молекулярной биологии и биоинформатике.

• [1] Под памятью в данном случае понимается все то, что будет влиять на вероятностивыбора в текущей позиции.
• [2] Так, для количества встречаемости аминокислот удобнее всего будет использовать"псевдозначения", пропорциональные частотам встречаемости аминокислот в реальныхбелках.
• [3] То есть не существует алгоритма, способного найти глобальное решение за полиномиальное время.
• [4] То есть не существует алгоритма, способного найти глобальное решение за полиномиальное время.
• [5] То есть не существует алгоритма, способного найти глобальное решение за полиномиальное время.
• [6] То есть не существует алгоритма, способного найти глобальное решение за полиномиальное время.