Анотація. Розглянуто задачу відновлення послідовності прихованих станів для сумішей розподілів, що описуються узагальненнями ланцюгів Маркова довільного порядку і прихованих марковських моделей. Запропоновано алгоритм динамічного програмування для розв’язання цієї задачі, а також його модифікації, що направлені на усунення рекурсії та скорочення перебору. Отримані результати застосовано до задачі розпізнавання фрагментів генів у геномах рослин.

Ключові слова: ланцюг Маркова, приховані змінні, ген, біоінформатика, нуклеотид, екзон, інтрон, правдоподібність.