Geodesic
Viterbi algorithms for Hidden semi-Markov Models with application to DNA Analysis
Pertsinidou, Christina-Elisavet1, 2  ; Limnios, Nikolaos1 
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.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 511-526

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :