Аннотация. Рассмотрена задача восстановления последовательности скрытых состояний для смесей распределений, описываемых обобщениями цепей Маркова произвольного порядка и скрытых марковских моделей. Предложен алгоритм динамического программирования для решения этой задачи, а также его модификации, направленные на устранение рекурсии и сокращение перебора. Полученные результаты применены к задаче распознавания фрагментов генов в геномах растений.
Ключевые слова: цепь Маркова, скрытые переменные, ген, биоинформатика, нуклеотид, экзон, интрон, правдоподобие.
Сергиенко Иван Васильевич,
академик НАН Украины, директор Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: aik@public.icyb.kiev.ua.
Гупал Анатолий Михайлович,
чл.-кор. НАН Украины, доктор физ.-мат. наук, профессор, заведующий отделом Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: gupal_anatol@mail.ru.
Островский Алексей Викторович,
кандидат физ.-мат. наук, младший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: ostrovski.alex@gmail.com.