Abstract. The authors consider the problem of recovering hidden state sequences for mixture distributions with constituents described by the generalization of high-order Markov chains and hidden Markov models. A new algorithm to solve the problem using dynamic programming is proposed, as well as its modifications to eliminate recursion and diminish search. The results are applied to the problem of gene fragment recognition in plants.
Keywords: Markov chain, hidden variables, gene, bioinformatics, nucleotide, exon, intron, likelihood.
Сергиенко Иван Васильевич,
академик НАН Украины, директор Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: aik@public.icyb.kiev.ua.
Гупал Анатолий Михайлович,
чл.-кор. НАН Украины, доктор физ.-мат. наук, профессор, заведующий отделом Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: gupal_anatol@mail.ru.
Островский Алексей Викторович,
кандидат физ.-мат. наук, младший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: ostrovski.alex@gmail.com.