| Issue |
RAIRO-Oper. Res.
Volume 49, Number 3, July-September 2015
|
|
|---|---|---|
| Page(s) | 511 - 526 | |
| DOI | https://doi.org/10.1051/ro/2014053 | |
| Published online | 06 February 2015 | |
Viterbi algorithms for Hidden semi-Markov Models with application to DNA Analysis
1 Université de Technologie de Compiègne, Laboratoire de Mathématiques Appliquées, Centre de Recherches de Royallieu, CS 60319, 60203 Compiègne Cedex, France.
p.eli.christina@gmail.com
2 Aristotle University of Thessaloniki, School of Mathematics, 54124 Thessaloniki, Greece.
Received: 3 March 2013
Accepted: 8 October 2014
In this paper we present a new Viterbi algorithm for Hidden semi-Markov models and also a second algorithm which is a generalization of the first. These algorithms can be used to decode an unobserved hidden semi-Markov process and it is the first time that the complexity is achieved to be the same as in the Viterbi for Hidden Markov models, i.e. a linear function of the number of observations and quadratic function of the number of hidden states. An example in DNA Analysis is also given.
Mathematics Subject Classification: 68Q25 / 68Q15 / 60K15 / 65K05
Key words: Viterbi algorithm / Hidden semi-Markov model / hidden Markov model / DNA Analysis
© EDP Sciences, ROADEF, SMAI, 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.