A Constraint Model for Constrained Hidden Markov Models: a First Biological Application

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

A Constraint Model for Constrained Hidden Markov Models: a First Biological Application

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

Programming, Logic and Intelligent Systems

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics
Number of pages	26
Publication date	2009
Pages	19
Publication status	Published - 2009
Event	Workshop on Constraint Based Methods for Bioinformatics - Lisboa, Portugal Duration: 20 Sept 2009 → 20 Sept 2009

Conference

Conference	Workshop on Constraint Based Methods for Bioinformatics
Country/Territory	Portugal
City	Lisboa
Period	20/09/2009 → 20/09/2009

Keywords

Hidden Markov Model
Constraint Programming
Constrained Hidden Markov Model

Link to document

WCB09 CRFinal published version, 134 KB

http://www.bioinf.uni-freiburg.de/Events/WCB09/proceedings.pdf

Logic-statistic modelling and analysis of biological sequence data
Christiansen, H., Gallagher, J. P., Skovgaard, O., Pedersen, M. B., Garrigues, C., Jaeger, M., Forsberg, R., Steffensen, P. J., Knudsen, T., Knudsen, B., Krogh, A. & Sato, T.
Det strategiske forskningsråd; NABIIT, Programkomitéen for nanovidenskab og teknologi, bioteknologi og IT
01/05/2007 → 31/12/2012
Project: Research

Cite this

@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",

note = "null ; Conference date: 20-09-2009 Through 20-09-2009",

}

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, Workshop on Constraint Based Methods for Bioinformatics, Lisboa, Portugal, 20/09/2009. <http://www.bioinf.uni-freiburg.de/Events/WCB09/proceedings.pdf>

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

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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - A Constraint Model for Constrained Hidden Markov Models

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

Y2 - 20 September 2009 through 20 September 2009

ER -

A Constraint Model for Constrained Hidden Markov Models: a First Biological Application

Abstract

Conference

Keywords

Link to document

Projects

Logic-statistic modelling and analysis of biological sequence data

Cite this