M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.003.0006
- Subject:
- Mathematics, Probability / Statistics
This chapter considers the basic properties of hidden Markov processes (HMPs) or hidden Markov models (HMMs), a special type of stochastic process. It begins with a discussion of three distinct types ...
More
This chapter considers the basic properties of hidden Markov processes (HMPs) or hidden Markov models (HMMs), a special type of stochastic process. It begins with a discussion of three distinct types of HMMs and shows that they are all equivalent from the standpoint of their expressive power or modeling ability: Type 1 hidden Markov model, or a HMM of the deterministic function of a Markov chain type; hidden Markov model of Type 2, or a HMM of the random function of a Markov chain type; and hidden Markov model of Type 3, or a HMM of the joint Markov process type. The chapter also examines various issues related to the computation of likelihoods in a HMM before concluding with an overview of the Viterbi algorithm and the Baum–Welch algorithm.Less
This chapter considers the basic properties of hidden Markov processes (HMPs) or hidden Markov models (HMMs), a special type of stochastic process. It begins with a discussion of three distinct types of HMMs and shows that they are all equivalent from the standpoint of their expressive power or modeling ability: Type 1 hidden Markov model, or a HMM of the deterministic function of a Markov chain type; hidden Markov model of Type 2, or a HMM of the random function of a Markov chain type; and hidden Markov model of Type 3, or a HMM of the joint Markov process type. The chapter also examines various issues related to the computation of likelihoods in a HMM before concluding with an overview of the Viterbi algorithm and the Baum–Welch algorithm.
M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.003.0007
- Subject:
- Mathematics, Probability / Statistics
This chapter considers hidden Markov processes (HMPs), focusing on the so-called complete realization problem. It is quite easy to prove a universal necessary condition for the given process to have ...
More
This chapter considers hidden Markov processes (HMPs), focusing on the so-called complete realization problem. It is quite easy to prove a universal necessary condition for the given process to have a hidden Markov model (HMM). However, this condition is not sufficient in general. In principle, one can derive a “necessary and sufficient condition,” but the “necessary and sufficient condition” is virtually a restatement of the problem to be solved and does not shed any insight into the solution. The chapter first introduces a very useful matrix known as the “Hankel” matrix before discussing the nonsufficiency of the finite Hankel rank condition, an abstract necessary and sufficient condition, and the existence of regular quasi-realizations. It also describes the spectral properties of alpha-mixing processes and goes on to analyze ultra-mixing processes and a sufficient condition for the existence of HMMs.Less
This chapter considers hidden Markov processes (HMPs), focusing on the so-called complete realization problem. It is quite easy to prove a universal necessary condition for the given process to have a hidden Markov model (HMM). However, this condition is not sufficient in general. In principle, one can derive a “necessary and sufficient condition,” but the “necessary and sufficient condition” is virtually a restatement of the problem to be solved and does not shed any insight into the solution. The chapter first introduces a very useful matrix known as the “Hankel” matrix before discussing the nonsufficiency of the finite Hankel rank condition, an abstract necessary and sufficient condition, and the existence of regular quasi-realizations. It also describes the spectral properties of alpha-mixing processes and goes on to analyze ultra-mixing processes and a sufficient condition for the existence of HMMs.
M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.001.0001
- Subject:
- Mathematics, Probability / Statistics
This book explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. It starts from first principles, so that ...
More
This book explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. It starts from first principles, so that no previous knowledge of probability is necessary. However, the work is rigorous and mathematical, making it useful to engineers and mathematicians, even those not interested in biological applications. A range of exercises is provided, including drills to familiarize the reader with concepts and more advanced problems that require deep thinking about the theory. Biological applications are taken from post-genomic biology, especially genomics and proteomics. The topics examined include standard material such as the Perron–Frobenius theorem, transient and recurrent states, hitting probabilities and hitting times, maximum likelihood estimation, the Viterbi algorithm, and the Baum–Welch algorithm. The book contains discussions of extremely useful topics not usually seen at the basic level, such as ergodicity of Markov processes, Markov Chain Monte Carlo (MCMC), information theory, and large deviation theory for both i.i.d and Markov processes. It also presents state-of-the-art realization theory for hidden Markov models. Among biological applications, it offers an in-depth look at the BLAST (Basic Local Alignment Search Technique) algorithm, including a comprehensive explanation of the underlying theory. Other applications such as profile hidden Markov models are also explored.Less
This book explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. It starts from first principles, so that no previous knowledge of probability is necessary. However, the work is rigorous and mathematical, making it useful to engineers and mathematicians, even those not interested in biological applications. A range of exercises is provided, including drills to familiarize the reader with concepts and more advanced problems that require deep thinking about the theory. Biological applications are taken from post-genomic biology, especially genomics and proteomics. The topics examined include standard material such as the Perron–Frobenius theorem, transient and recurrent states, hitting probabilities and hitting times, maximum likelihood estimation, the Viterbi algorithm, and the Baum–Welch algorithm. The book contains discussions of extremely useful topics not usually seen at the basic level, such as ergodicity of Markov processes, Markov Chain Monte Carlo (MCMC), information theory, and large deviation theory for both i.i.d and Markov processes. It also presents state-of-the-art realization theory for hidden Markov models. Among biological applications, it offers an in-depth look at the BLAST (Basic Local Alignment Search Technique) algorithm, including a comprehensive explanation of the underlying theory. Other applications such as profile hidden Markov models are also explored.
M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.003.0008
- Subject:
- Mathematics, Probability / Statistics
This chapter considers some applications of Markov processes and hidden Markov processes to computational biology. It introduces three important problems, namely: sequence alignment, the gene-finding ...
More
This chapter considers some applications of Markov processes and hidden Markov processes to computational biology. It introduces three important problems, namely: sequence alignment, the gene-finding problem, and protein classification. After providing an overview of some relevant aspects of biology, the chapter examines the problem of optimal gapped alignment between two sequences. This is a way to detect similarity between two sequences over a common alphabet, such as the four-symbol alphabet of nucleotides, or the 20-symbol alphabet of amino acids. The chapter proceeds by discussing some widely used algorithms for finding genes from DNA sequences (genomes), including the GLIMMER algorithm and the GENSCAN algorithm. Finally, it describes a special type of hidden Markov model termed profile hidden Markov model, which is commonly used to classify proteins into a small number of groups.Less
This chapter considers some applications of Markov processes and hidden Markov processes to computational biology. It introduces three important problems, namely: sequence alignment, the gene-finding problem, and protein classification. After providing an overview of some relevant aspects of biology, the chapter examines the problem of optimal gapped alignment between two sequences. This is a way to detect similarity between two sequences over a common alphabet, such as the four-symbol alphabet of nucleotides, or the 20-symbol alphabet of amino acids. The chapter proceeds by discussing some widely used algorithms for finding genes from DNA sequences (genomes), including the GLIMMER algorithm and the GENSCAN algorithm. Finally, it describes a special type of hidden Markov model termed profile hidden Markov model, which is commonly used to classify proteins into a small number of groups.
