Algorithmic Issues in Hidden Markov Models
David Fernández-Baca (1)
e-mails: fernande@cs.iastate.edu
(1) Department of Computer Science, Iowa State University, Ames, Iowa 50011 Estados Unidos
A hidden Markov model (HMM) is a stochastic system that can, at
any given time, be in one of a finite number of states, each of
which emits a symbol with a certain probability. Furthermore,
transitions between states occur according to certain
probabilities. An observer of a HMM can see the sequence it emits,
but not the sequence of states that produced the symbols. A
basic problem in HMMs is to infer the most likely sequence of
states that resulted in a given observed sequence. HMMs are used
in applications ranging from speech recognition to gene
identification. For example, in speech recognition the observed
symbols are a series of phonemes and the problem is to infer the
sequence of words that produced it. In this tutorial, we give an
overview of HMMs and discuss some of their applications, with
special emphasis on their use in bioinformatics. We then discuss
some of the algorithmic issues that arise in conjunction with
HMMs. In particular, we consider methods for studying the
sensitivity of HMMs to the choice of transition probabilities and
for estimating the best parameters for a model. We illustrate
these approaches through an application in computational biology:
estimating the evolutionary distance between two DNA sequences.
Keywords:Hidden Markov models, Statistical models, Bioinformatics, Computational biology, Algorithms, Evolutionary trees, Sensitivity analysis, Optimization
David Fernández-Baca is a Professor of Computer Science at Iowa
State University, where he has been a faculty member since 1986.
He obtained the undergraduate degree in Computer Engineering
(Ingeniería en Computación) in 1980 from the Universidad Nacional
Autónoma de México, the MS in Computer Engineering and the PhD in
Computer Science from the University of California, Davis in 1983
and 1986, respectively. His research interests are in
computational biology (primarily in evolutionary tree
construction) and combinatorial optimization (primarily in
sensitivity analysis of optimization problems).
BibTex
@INPROCEEDINGS{fernandez-baca04:1008,
AUTHOR = {David Fernández-Baca},
TITLE = {Algorithmic Issues in Hidden Markov Models},
BOOKTITLE = {30ma Conferencia Latinoamericana de Informática (CLEI2004)},
YEAR = {2004},
editor = {Mauricio Solar and David Fernández-Baca and Ernesto Cuadros-Vargas},
pages = {12--12},
address = {},
month = Sep,
organization = {Sociedad Peruana de Computación},
note = {ISBN 9972-9876-2-0},
}
PDF de CLEI2004 (incluye todos los artículos)
Página principal CLEI 2004
Generado por Sociedad Peruana de Computación