A Constraint Model for Constrained Hidden Markov Models

a First Biological Application

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

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TitelProceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics
Antal sider26
Publikationsdato2009
Sider19
StatusUdgivet - 2009
BegivenhedWorkshop on Constraint Based Methods for Bioinformatics - Lisboa, Portugal
Varighed: 20 sep. 200920 sep. 2009

Konference

KonferenceWorkshop on Constraint Based Methods for Bioinformatics
LandPortugal
ByLisboa
Periode20/09/200920/09/2009

Citer dette

Christiansen, H., Have, C. T., Lassen, O. T., & Petit, M. (2009). A Constraint Model for Constrained Hidden Markov Models: a First Biological Application. I Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics (s. 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. s. 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. i Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics. s. 19, Workshop on Constraint Based Methods for Bioinformatics, 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. s. 19.

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer 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. I Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics. 2009. s. 19