Viterbi algorithms for Hidden semi-Markov Models with application to DNA Analysis
RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 3, pp. 511-526.

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.

Received:
Accepted:
DOI: 10.1051/ro/2014053
Classification: 68Q25, 68Q15, 60K15, 65K05
Keywords: Viterbi algorithm, Hidden semi-Markov model, hidden Markov model, DNA Analysis
Pertsinidou, Christina-Elisavet 1, 2; Limnios, Nikolaos 1

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.
2 Aristotle University of Thessaloniki, School of Mathematics, 54124 Thessaloniki, Greece.
@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://archive.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://archive.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://archive.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, Volume 49 (2015) no. 3, pp. 511-526. doi : 10.1051/ro/2014053. http://archive.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

J. Bulla, I. Bulla and O. Nenadić, An R package for analyzing hidden semi-Markov models. Comput. Stat. Data Anal. 54 (2010) 611–619. | DOI | MR | Zbl

O. Chryssaphinou, M. Karaliopoulou and N. Limnios, 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).

M. Dong and D. He, Hidden semi-Markov model-based methodology for multi-sensor equipment health diagnosis and prognosis. Eur. J. Oper. Res. 178 (2011) 858–878. | DOI | Zbl

Y. Guédon, 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

L.R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77 (1989) 257–286. | DOI

A. Taghva, 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.

S.Z. Yu, Hidden semi-Markov models. Artif. Intell. 174 (2010) 215–243. | DOI | MR | Zbl

Cited by Sources: