Inference with constrained hidden Markov models in PRISM

Henning Christiansen, Christian Theil Have, Ole Torp Lassen, Matthieu Petit

Research output: Contribution to journalJournal articleResearchpeer-review


A Hidden Markov Model (HMM) is a common statistical model which is widely used for analysis of biological sequence data and other sequential phenomena. In the present paper we show how HMMs can be extended with side-constraints and present constraint solving techniques for efficient inference. Defining HMMs with side-constraints in Constraint Logic Programming has advantages in terms of more compact expression and pruning opportunities during inference. We present a PRISM-based framework for extending HMMs with side-constraints and show how well-known constraints such as cardinality and all_different are integrated. We experimentally validate our approach on the biologically motivated problem of global pairwise alignment.
Original languageEnglish
JournalTheory and Practice of Logic Programming
Issue number4-6
Pages (from-to)449-464
Number of pages15
Publication statusPublished - 2010


  • Hidden Markov Model with side-constraints
  • inference
  • Programming in statistical modeling

Cite this