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.
Accepté le :
DOI : 10.1051/ro/2014053
Mots clés : Viterbi algorithm, Hidden semi-Markov model, hidden Markov model, DNA Analysis
@article{RO_2015__49_3_511_0,
author = {Pertsinidou, Christina-Elisavet and Limnios, Nikolaos},
title = {Viterbi algorithms for {Hidden} {semi-Markov} {Models} with application to {DNA} {Analysis}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {511--526},
publisher = {EDP-Sciences},
volume = {49},
number = {3},
year = {2015},
doi = {10.1051/ro/2014053},
mrnumber = {3349132},
zbl = {1336.68301},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2014053/}
}
TY - JOUR AU - Pertsinidou, Christina-Elisavet AU - Limnios, Nikolaos TI - Viterbi algorithms for Hidden semi-Markov Models with application to DNA Analysis JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 511 EP - 526 VL - 49 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2014053/ DO - 10.1051/ro/2014053 LA - en ID - RO_2015__49_3_511_0 ER -
%0 Journal Article %A Pertsinidou, Christina-Elisavet %A Limnios, Nikolaos %T Viterbi algorithms for Hidden semi-Markov Models with application to DNA Analysis %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 511-526 %V 49 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2014053/ %R 10.1051/ro/2014053 %G en %F RO_2015__49_3_511_0
Pertsinidou, Christina-Elisavet; Limnios, Nikolaos. Viterbi algorithms for Hidden semi-Markov Models with application to DNA Analysis. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 511-526. doi : 10.1051/ro/2014053. http://www.numdam.org/articles/10.1051/ro/2014053/
V.S. Barbu and N. Limnios, Semi-Markov chains and hidden semi-Markov models toward applications. Springer, New York (2008). | MR | Zbl
, and , An R package for analyzing hidden semi-Markov models. Comput. Stat. Data Anal. 54 (2010) 611–619. | DOI | MR | Zbl
, and , On discrete time semi-Markov chains and applications in words occurrences. Commun. Stat. Theory Methods 37 (2008) 1306–1322. | DOI | MR | Zbl
N.A. Dasu, Implementation of hidden semi-Markov models. Th.D. Thesis, University of Nevada, Las Vegas (2011).
and , Hidden semi-Markov model-based methodology for multi-sensor equipment health diagnosis and prognosis. Eur. J. Oper. Res. 178 (2011) 858–878. | DOI | Zbl
, Estimating hidden semi-Markov chains from discrete sequences. J. Comput. Graph. Stat. 12 (2003) 604–639. | DOI | MR
T. Koski, Hidden Markov models for bioinformatics. Kluwer, Dordrecht (2001). | MR | Zbl
, A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77 (1989) 257–286. | DOI
, Hidden semi-Markov models in the computerized decoding of microelectrode recording data for deep brain stimulator placement. World Neurosurg. 75 (2011) 758–763. | DOI
M. Tang and P. Di Cristo, Backward Viterbi beam search for utilizing dynamic task complexity information, in Proc. Conference International Speech Communication Association (2008) 2090–2093.
, Hidden semi-Markov models. Artif. Intell. 174 (2010) 215–243. | DOI | MR | Zbl
Cité par Sources :
