Hidden Markov processes : theory and applications to biology / M. Vidyasagar.

Includes bibliographical references and index.

1. Introduction to probability and random variables : Introduction to random variables ; Motivation ; Definition of a random variable and probability ; Function of a random variable, expected value ; Total variation distance ; Multiple random variables ; Joint and marginal distributions ; Independence and conditional distributions ; Bayes' rule ; MAP and maximum likelihood estimates ; Random variables assuming infinitely many values ; Some preliminaries ; Markov and Chebycheff inequalities ; Hoeffding's inequality ; Monte Carlo simulation ; Introduction to Cramer's theorem --
2. Introduction information theory : Convex and concave functions ; Entropy ; Definition of entropy ; Properties of the entropy function ; Conditional entropy ; Uniqueness of the entropy function ; Relative entropy and the Kullback-Leibler divergence --
3. Nonnegative matrices : Canonical form for nonnegative matrices ; Basic version of the canonical form ; Irreducible matrices ; Final version of canonical form ; Irreducibility, aperiodicity, and primitivity ; Canonical form for periodic irreducible matrices ; Perron-Frobenius theory ; Perron-Frobenius theorem for primitive matrices ; Perron-Frobenius theorem for irreducible matrices.
4. Markov processes : Basic definitions ; The Markov property and the state transition matrix ; Estimating the state transition matrix ; Dynamics of stationary Markov chains ; Recurrent and transient states; Hitting probabilities and mean hitting times ; Ergodicity of Markov chains --
5. Introduction to large deviation theory : Problem formulation ; large deviation property for I.I.D. samples: Sanov's theorem ; Large deviation property for Markov chains ; Stationary distributions ; Entropy and relative entropy rates ; The rate function for Doubleton frequencies ; The rate function for Singleton frequencies --
6. Hidden Markov processes: basic properties : Equivalence of various hidden Markov models ; Three different-looking models ; Equivalence between the three models ; Computation of likelihoods ; Computation of likelihoods of output sequences ; The Viterbi algorithm ; The Baum-Welch algorithm --
7. Hidden Markov processes: the complete realization problem : Finite Hankel rank: a universal necessary condition ; Nonsufficiency of the finite Hankel rank condition ; An abstract necessary and sufficient condition ; Existence of regular quasi-realizations ; Spectral properties of alpha-mixing processes ; Ultra-mixing processes ; A sufficient condition for the existence of HMMs. 8. Some applications to computational biology : Some basic biology ; The genome ; The genetic code ; Optimal gapped sequence alignment ; Problem formulation ; Solution via dynamic programming ; Gene finding ; Genes and the gene-finding problem ; The GLIMMER family of algorithms ; The GENSCAN algorithm ; Protein classification ; Proteins and the protein classification problem ; Protein classification using profile hidden Markov models --
9. BLAST theory : BLAST theory: statements of main results ; Problem formulations ; THe moment generating function ; Statement of main results ; Application of main results ; BLAST theory: proofs of main results --
Bibliography --
Index.

Explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. This book provides a range of exercises, including drills to familiarize the reader with concepts and more advanced problems that require deep thinking about the theory.