Основы биоинформатики - Огурцов А.Н. 2013
Методы биоинформационного анализа
Множественное выравнивание последовательностей
Скрытые марковские модели
Скрытая марковская модель (Hidden Markov model, НММ) - это статистическая модель, имитирующая работу процесса, похожего на марковский процесс с неизвестными параметрами, в которой задачей ставится разгадывание (восстановление) неизвестных параметров на основе наблюдаемых. Полученные параметры могут быть использованы в дальнейшем анализе, например, для распознавания образов. Первые заметки о скрытых марковских моделях опубликовал Баум в 1960-х, и уже в 70-х их впервые применили при распознавании речи. С середины 1980-х НММ применяются при анализе биологических последовательностей, в частности, ДНК.
Марковский процесс - это случайный процесс, эволюция которого после любого заданного значения временного параметра t не зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот момент фиксировано ("будущее" процесса не зависит от "прошлого" при известном "настоящем"; или, иначе: "будущее" процесса зависит от "прошлого" лишь через "настоящее").
Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано Андреем Андреевичем Марковым (1856-1922) - выдающимся русским математиком, внёсшим большой вклад в теорию вероятностей, математический анализ и теорию чисел. В работах 1907 г. А.А. Марков положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова (Markov chain). Кроме биоинформатики скрытые марковские модели применяются в криптоанализе и машинном переводе.
В биоинформатике скрытые марковские модели служат для описания тонких различий, существующих между семействами гомологичных последовательностей. Метод скрытых марковских моделей (Hidden Markov model, НММ) эффективен и при сравнении дальних родственников, и при предсказании путей сворачивания белков. Только этот метод, полностью базирующийся на анализе последовательностей (то есть не использующий структурную информацию), может соперничать с программой PSI-BLAST при идентификации дальних гомологов.
Хотя метод скрытых марковских моделей работает с множественными выравниваниями последовательностей, но этот метод также часто используется и для генерации последовательностей.
Обычная таблица множественного выравнивания последовательностей, вообще говоря, также может использоваться для генерации этих последовательностей путём выборки аминокислот в последовательных позициях. Каждая аминокислота выбирается из вероятностного позиционно-специфического распределения, полученного из профиля.
Модели НММ являются более общими методами, чем профили, поскольку включают вероятность возникновения делеций или вставок в генерируемой последовательности с позиционно-зависимыми штрафами для них.
Если применение профилей требует предварительного построения множественного выравнивания последовательностей и при таком подходе статистика запросов определяется после построения выравнивания, то НММ одновременно выполняет и выравнивание, и оценку вероятностей.
Рисунок 62 схематично иллюстрирует механизм генерации последовательностей. На рисунке показаны три позиции и набор состояний (m), (i), (d).
Рисунок 62 - Структура скрытой марковской модели
Начиная со "Старт" НММ перемещается по стрелкам до "Стоп". Каждая стрелка приводит к определённому состоянию (state) системы. В каждом из этих состояний предпринимается (1) определённое действие (например, задаётся аминокислота) и затем (2) выбирается стрелка, которая переводит в следующее состояние системы. Действие и выбор следующего состояния управляются определёнными наборами вероятностей.
На каждой позиции, на которой вводится аминокислотный остаток, один набор вероятностей задан для процесса выбора одной из 20 стандартных аминокислот, а второй набор вероятностей — для процесса выбора пути перехода к следующей стадии процесса. Оба этих набора вероятностей подбираются так, чтобы задать адекватное описание определённого семейства последовательностей. Используя такой подход, и варьируя только позиционно-специфические таблицы вероятностей, одинаковый алгоритм может быть использован для различных семейств последовательностей. На рисунке 62 каждой из трёх позиций во множественном выравнивании НММ соответствуют сопоставление (m) (mach) и делеция (d). Вставки (i) могут быть как между позициями остатков, так и в начале, и в конце выравнивания.
Если данная позиция соответствует сопоставлению (m), то в выравнивание вставляется соответствующий аминокислотный остаток.
В данном случае слово "сопоставление" означает только то, что некоторые аминокислоты есть и в НММ-последовательности, и в итоговой последовательности, а не то, что это должны быть обязательно одинаковые аминокислоты.
Вероятность выбора одной из 20 аминокислот в данной позиции сопоставления определяется параметрами используемой модели, то есть позиционно-специфичными вероятностями вставки аминокислот в данной позиции.
В случае делеции (d) данная колонка множественного выравнивания пропускается. Введение первой делеции означает открытие интервала делеции (gap-open), а вероятность такого введения определяет величину штрафа за введение делеции, которая также является позиционноспецифичной. Введение второй делеции сразу вслед за первой означает продолжение делеции (gap-extension), за что также может назначаться штраф (см. п. 7.2).
Вставки (і) помещают между двумя последовательными позициями в выравнивании. Если программа вводит вставку, то в генерируемую последовательность вставляется остаток, не совпадающий (в данной позиции) с остатками в последовательностях, по отношению к которым производится множественное выравнивание. За первой вставкой может следовать вторая и т. д., образуя вставку размером больше, чем один остаток.
Последовательность остатков, полученных сопоставлений и вставок, и представляет собой искомую (генерируемую) последовательность.
После выполнения соответствующего действия (т, d или і), переход в следующий узел графа определяется уже новым набором вероятностей.
В каждой возможной последовательности положений каждая колонка построенного выравнивания должна быть либо сопоставлением, либо делецией - не существует способа пересечь граф без прохода или через (m)-узел, или через (d)-узел, и так для каждой позиции в последовательности.
Динамика описанной системы такова, что только текущая позиция определяет какая из возможных стрелок будет выбрана для следующего перехода, иначе говоря, система не "помнит" своей истории. А это как раз и характерно для марковских процессов.
Отметим, что следует отличать последовательность позиций (или этапов) в работе программы от последовательности аминокислот, которая генерируется в результате работы алгоритма.
Может оказаться, что разные пути через систему могут порождать одинаковые последовательности.
В итоге мы получаем результат работы алгоритма, а все "подробности" прохождения графа внутри системы и выбора конкретного "маршрута" между "Старт" и "Стоп" остаются скрытыми (hidden). Отсюда и название - скрытая марковская модель (Hidden Markov Model).
Специфичность работы алгоритма для данного набора последовательностей задаётся как раз теми наборами вероятностей (выбора остатка и выбора перехода), которые задаются для каждой позиции индивидуально.
Программы, в которых реализованы НММ для анализа биологических последовательностей, могут делать следующее.
1. Обучение. Имея набор не выровненных гомологичных последовательностей, можно (1) выровнять их и (2) подобрать такие вероятности переходов и выбора остатков, чтобы определить НММ, описывающую заданный набор последовательностей.
2. Поиск дальних гомологов. Имея НММ и исследуемую последовательность, можно рассчитать вероятность того, что НММ могла бы сгенерировать эту последовательность. Если НММ, разработанная для известного семейства последовательностей, может это сделать с достаточно большой вероятностью, то это свидетельствует в пользу того, что исследуемая последовательность также принадлежит к этому семейству.
3. Выравнивание дополнительных последовательностей. Вероятность прохождения любого маршрута в данной НММ, то есть вероятность получения именно данного набора состояний, может быть рассчитана из индивидуальных вероятностей переходов "состояние-за-состоянием" (state-by-state). Нахождение наиболее вероятной последовательности состояний, которые использовала бы НММ для создания одной или нескольких тестовых последовательностей, демонстрирует их оптимальное выравнивание с данным семейством последовательностей.
Контрольные вопросы и задания
1. Что называется множественным выравниванием?
2. Какой вид аннотации множественного выравнивания использует программа ClustalW?
3. Что такое профиль выравнивания?
4. В чём преимущество программы PSI-BLAST по сравнению с профилями выравниваний?
5. Какой процесс называют Марковским?
6. В чём преимущество метода скрытых марковских моделей?
7. Какие два выбора с использованием позиционно-специфических таблиц вероятностей делаются в каждом состоянии системы в рамках скрытой марковской модели?
8. Какие три типа задач могут решать программы, в которых реализованы скрытые марковские модели?