A Constraint Model for Constrained Hidden Markov Models

a First Biological Application

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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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 extend HMMs with constraints and show how the familiar Viterbi algorithm can be generalized, based on constraint solving methods. HMMs with constraints have advantages over traditional ones in terms of more compact expressions as well as opportunities for pruning during Viterbi computations. We exemplify this by an enhancement of a simple prokaryote gene finder given by an HMM.
Original languageEnglish
Title of host publicationProceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics
Number of pages26
Publication date2009
Pages19
Publication statusPublished - 2009
EventWorkshop on Constraint Based Methods for Bioinformatics - Lisboa, Portugal
Duration: 20 Sep 200920 Sep 2009

Conference

ConferenceWorkshop on Constraint Based Methods for Bioinformatics
CountryPortugal
CityLisboa
Period20/09/200920/09/2009

Keywords

  • Hidden Markov Model
  • Constraint Programming
  • Constrained Hidden Markov Model

Cite this

Christiansen, H., Have, C. T., Lassen, O. T., & Petit, M. (2009). A Constraint Model for Constrained Hidden Markov Models: a First Biological Application. In Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics (pp. 19)
Christiansen, Henning ; Have, Christian Theil ; Lassen, Ole Torp ; Petit, Matthieu. / A Constraint Model for Constrained Hidden Markov Models : a First Biological Application. Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics. 2009. pp. 19
@inproceedings{12564d808d6611debe3e000ea68e967b,
title = "A Constraint Model for Constrained Hidden Markov Models: a First Biological Application",
abstract = "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 extend HMMs with constraints and show how the familiar Viterbi algorithm can be generalized, based on constraint solving methods. HMMs with constraints have advantages over traditional ones in terms of more compact expressions as well as opportunities for pruning during Viterbi computations. We exemplify this by an enhancement of a simple prokaryote gene finder given by an HMM.",
keywords = "Hidden Markov Model, Constraint Programming, Constrained Hidden Markov Model",
author = "Henning Christiansen and Have, {Christian Theil} and Lassen, {Ole Torp} and Matthieu Petit",
year = "2009",
language = "English",
pages = "19",
booktitle = "Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics",

}

Christiansen, H, Have, CT, Lassen, OT & Petit, M 2009, A Constraint Model for Constrained Hidden Markov Models: a First Biological Application. in Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics. pp. 19, Lisboa, Portugal, 20/09/2009.

A Constraint Model for Constrained Hidden Markov Models : a First Biological Application. / Christiansen, Henning; Have, Christian Theil; Lassen, Ole Torp; Petit, Matthieu.

Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics. 2009. p. 19.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - A Constraint Model for Constrained Hidden Markov Models

T2 - a First Biological Application

AU - Christiansen, Henning

AU - Have, Christian Theil

AU - Lassen, Ole Torp

AU - Petit, Matthieu

PY - 2009

Y1 - 2009

N2 - 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 extend HMMs with constraints and show how the familiar Viterbi algorithm can be generalized, based on constraint solving methods. HMMs with constraints have advantages over traditional ones in terms of more compact expressions as well as opportunities for pruning during Viterbi computations. We exemplify this by an enhancement of a simple prokaryote gene finder given by an HMM.

AB - 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 extend HMMs with constraints and show how the familiar Viterbi algorithm can be generalized, based on constraint solving methods. HMMs with constraints have advantages over traditional ones in terms of more compact expressions as well as opportunities for pruning during Viterbi computations. We exemplify this by an enhancement of a simple prokaryote gene finder given by an HMM.

KW - Hidden Markov Model

KW - Constraint Programming

KW - Constrained Hidden Markov Model

M3 - Article in proceedings

SP - 19

BT - Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics

ER -

Christiansen H, Have CT, Lassen OT, Petit M. A Constraint Model for Constrained Hidden Markov Models: a First Biological Application. In Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics. 2009. p. 19