Ускоренный поиск с использованием профильных скрытых марковских моделей

Профильные скрытые марковские модели (профильные HMM) и методы вероятностного вывода внесли существенный вклад в теорию поиска гомологий в базах последовательностей. Однако широкому практическому применению профильных HMM мешали высокие вычислительные затраты существующих программных реализаций. Здесь описана эвристика ускорения работы профильных HMM — алгоритм Витерби для нескольких сегментов (MSV). С помощью векторно-параллельных вычислений с разбиением на полосы, ранее применённых для быстрого выравнивания Смита—Уотермана, алгоритм MSV вычисляет оптимальную сумму нескольких локальных сегментов выравнивания без гэпов. Оценки MSV подчиняются тому же статистическому распределению, что и оценки оптимального локального выравнивания с гэпами. Благодаря этому статистическую значимость оценки MSV можно быстро определить, что позволяет использовать её в качестве фильтра-эвристики. Также описан метод «разреженного масштабирования», ускоряющий стандартные алгоритмы прямого и обратного прохода профильных HMM в 20 раз. Эти методы объединены в конвейер: совпадения с высокими оценками MSV передаются на повторный анализ с помощью полных алгоритмов прямого и обратного прохода HMM. Ускоренный конвейер реализован в свободно распространяемом программном пакете HMMER3. Сравнительные испытания показали, что применение эвристического фильтра MSV практически не снижает чувствительность по сравнению с поиском по профильным HMM без ускорения. HMMER3 значительно чувствительнее HMMER2 и работает в 100–1000 раз быстрее. При поиске белковых последовательностей HMMER3 по скорости примерно сопоставим с BLAST.