Применение скрытых моделей Маркова для идентификации последовательностей

Особым случаем использования скрытых моделей Маркова в биоинформатике является применение их в качестве технологии выравнивания исследуемой последовательности и профиля. На рис. 3.12 представлены архитектуры некоторых моделей.

Рис. 3.12. Примеры структур различных НММ:

стрелки обозначают переходы между различными состояниями (распределения символов, генерируемые состояниями, не показаны); ромбики — состояния «вставки»; пронумерованные квадраты — состояния «совпадений»; кружки — специальные негенерирующие символы состояния «удаления», а также начальные и конечные состояния [9].

Так, в данной области сложились некоторые стандартные способы представления состояний модели. В виде квадрата обозначают состояние, способное генерировать символы аминокислот с определенными частотами. Поскольку через это состояние система может пройти один раз, то оно соответствует выравниванию (совпадению) позиции профиля, описываемого данным состоянием модели и исследуемой последовательности, что в рамках модели соответствует сгенерированной последовательности символов. Состояния, обозначаемые ромбами, соответствуют вставке символов в исследуемую последовательность относительно профиля, поскольку позволяют осуществлять переход к самому себе (стрелка в виде петли), каждый раз генерируя следующий символ последовательности. Окружностями обозначают специальные негенерирующие символы состояния, используемые для реализации пропусков в последовательности относительно профиля. Также окружностями обозначают начальное и конечное состояния.

Рис. 3.13. Пример скрытой модели Маркова для выравнивания последовательности с профилем

Из литературы известно несколько типичных реализаций моделей Маркова для задачи выравнивания профиля и последовательности, рассмотрим некоторые из них. Наиболее простой является модель BLOCKS (см. рис. 3.13). Из рисунка очевидно, что модель подразумевает выравнивание с профилем без пропусков и состоит только из состояний «совпадения» (match states). Профилем Prof длинной L будем называть набор вероятностей е,(й), где для каждой позиции профиля 1 < i < L и для всех символов b е О — efjb) определяет вероятность наблюдать символ b в позиции i. В этом случае вероятность генерации строки символов X = (x_ltx_t,…, x_L) при заданном профиле Prof будет равна.

также мы можем произвести оценку правдоподобия выравнивания без пропусков между последовательностью X и профилем Prof:

где p (b) — вероятность встречи символа b в последовательностях. Поскольку значения оценки правдоподобия для случайных последовательностей следуют распределению экстремальных значений, известному нам по распределениям значений оценочной функции при выравнивании последовательностей, к ним применимы основные наблюдения из подпараграфа 3.1.3^[1].

Несколько более сложный вариант модели, реализованный в методе МЕТА-МЕМЕ, использует дополнительный тип состояний, обеспечивающий возможность вставок в последовательности относительно профиля и которые обычно изображаются в виде ромбиков (рис. 3.14). Эти специальные состояния, называемые состоянием вставки (insertion states), обычно имеют вероятности генерации, равные фоновым частотам распределения символов^[2]: /Ь е О е^(Ь) = р (Ь). Реализация вставок различной длины обеспечивается циклическим переходом из вставочного состояния к самому себе. Если обозначать состояния вставки буквой /, а обычные состояния совпадения — буквой М, то реализацию аффинных пропусков можно обеспечить заданием вероятностей переходов a_Mj у, ау у и a_{Vj M}j₊

Рис. 3.14. Схема состояний скрытой модели Маркова, позволяющей вставки в последовательность относительно профиля

Наконец, реализация пропусков в последовательности относительно профиля требует введения еще одного типа состояний — специальных негенерирующих состояний (silent states), обозначаемых символом D (рис. 3.15). Эти состояния позволяют «обходить» состояния совмещения и вставки.

Рис. 3.15. Схема состояний скрытой модели Маркова, позволяющей вставки и делеции в последовательности относительно профиля

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

• 1) существенно меньшая связность узлов, в отличие от общей модели, в которой подразумевалось, что каждый узел связан со всеми другими. В случае профильных НММ каждый из узлов имеет до трех входящих связей и трех исходящих;
• 2) топология связей подразумевает «направленный» проход узлов;
• 3) совершенно четко можно выделить три типа узлов с различным типом поведения. При этом, с учетом распределения связей, узлы можно разделить на группы, в которых за одно прохождение модели будет посещен только один из узлов группы.

Эти отличия позволяют произвести модификации в алгоритмах Витерби, прямом и обратном алгоритмах, а также в алгоритме Баума — Велша, повышающие их эффективность. Основным изменением в алгоритмах является рассмотрение не всех возможных предыдущих состояний для каждого текущего состояния, а только тех, из которых к данному состоянию ведет ребро графа. Так, для профиля, состоящего из Т колонок, где каждое генерирующее состояние оперирует М типами символов, вычислительная сложность алгоритмов оценивается как 0(Т • М).

• [1] За исключением выравнивания специфичных алгоритмов и подходов, например таких, как «метод островков».
• [2] Одним из преимуществ применения скрытых моделей Маркова для выравниваний типапоследовательность — профиль состоит в возможности задавать для состояний «вставки"при необходимости специальные распределения частот генерации символов, что позволяетпрофилю описывать петли с необычным распределением различных остатков.