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

Programmering, logik og intelligente systemer

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

5062 Downloads (Pure)

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.

Originalsprog	Engelsk
Titel	Proceedings of WCB09: Workshop on Constraint Based Methods for Bioinformatics
Antal sider	26
Publikationsdato	2009
Sider	19
Status	Udgivet - 2009
Begivenhed	Workshop on Constraint Based Methods for Bioinformatics - Lisboa, Portugal Varighed: 20 sep. 2009 → 20 sep. 2009

Konference

Konference	Workshop on Constraint Based Methods for Bioinformatics
Land/Område	Portugal
By	Lisboa
Periode	20/09/2009 → 20/09/2009

Link til dokument

WCB09 CRForlagets udgivne version, 134 KB

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

Logisk-statistisk modellering og analyse af biologiske sekvensdata
Christiansen, H. (Projektdeltager), Gallagher, J. P. (Projektdeltager), Skovgaard, O. (Projektdeltager), Pedersen, M. B. (Projektdeltager), Garrigues, C. (Projektdeltager), Jaeger, M. (Projektdeltager), Forsberg, R. (Projektdeltager), Steffensen, P. J. (Projektdeltager), Knudsen, T. (Projektdeltager), Knudsen, B. (Projektdeltager), Krogh, A. (Projektdeltager) & Sato, T. (Projektdeltager)
Det strategiske forskningsråd; NABIIT, Programkomitéen for nanovidenskab og teknologi, bioteknologi og IT
01/05/2007 → 31/12/2012
Projekter: Projekt › Forskning

Citer dette

@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 = "Workshop on Constraint Based Methods for Bioinformatics ; 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. 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. <http://www.bioinf.uni-freiburg.de/Events/WCB09/proceedings.pdf>

TY - GEN

T1 - A Constraint Model for Constrained Hidden Markov Models

T2 - Workshop on Constraint Based Methods for Bioinformatics

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

Konference

Link til dokument

Projekter

Logisk-statistisk modellering og analyse af biologiske sekvensdata

Citer dette