An introduction to hidden Markov models for biological sequences
New comprehensive biochemistryPublished 1 January 1998
Anders Krogh
Citations172
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This chapter discusses the hidden Markov models (HMM) for biological sequences, a statistical model which is very well suited for many tasks in molecular biology, although they have been mostly developed for speech recognition.
Abstract
This chapter discusses the hidden Markov models (HMM) for biological sequences. A hidden Markov model (HMM) is a statistical model, which is very well suited for many tasks in molecular biology, although they have been mostly developed for speech recognition. The most popular use of the HMM in molecular biology is as a probabilistic profile of a protein family, which is called a profile HMM. From a family of proteins (or DNA), a profile HMM can be made for searching a database for other members of the family. These profile HMMs resemble the profile and weight matrix methods, and the main contribution is that the profile HMM treats gaps in a systematic way. The HMM is particularly well suited for problems with a simple grammatical structure, such as gene finding. In gene finding several signals must be recognized and combined into a prediction of exons and introns and the prediction must conform to various rules to make it a reasonable gene prediction. An HMM can combine recognition of the signals and it can be made such that the predictions always follow the rules of a gene.
Keywords
Biochemistry, Genetics and Molecular Biology
Proceedings of the IEEEA tutorial on hidden Markov models and selected applications in speech recognition
22,785 Citations1989L. R. Rabiner
Journal of Molecular BiologyPrediction of complete gene structures in human genomic DNA
4,264 Citations1997Chris Burge, Samuel Karlin
A general probabilistic model of the gene structure of human genomic sequences which incorporates descriptions of the basic transcriptional, translational and splicing signals, as well as length distributions and compositional features of exons, introns and intergenic regions is introduced.
Cambridge University Press eBooksBiological Sequence Analysis
3,283 Citations1998Richard Durbin, Sean R. Eddy +2 more
This book gives a unified, up-to-date and self-contained account, with a Bayesian slant, of such methods, and more generally to probabilistic methods of sequence analysis.
Journal of Molecular BiologyHidden Markov Models in Computational Biology
1,961 Citations1994Anders Krogh, Michael Brown +3 more
The results suggest the presence of an EF-hand calcium binding motif in a highly conserved and evolutionary preserved putative intracellular region of 155 residues in the alpha-1 subunit of L-type calcium channels which play an important role in excitation-contraction coupling.
Nucleic Acids ResearchThe PROSITE database, its status in 1997
1,768 Citations1997Amos Bairoch, Philip Bucher +1 more
Journal of Computational BiologyImproved Splice Site Detection in Genie
1,581 Citations1997Martin G. Reese, Frank H. Eeckman +2 more
Improved splice site detection in Genie
1,462 Citations1997Martin G. Reese, Frank H. Eeckman +2 more
An improved splice site predictor for the genefinding program Genie is presented and it is shown that Genie shows significant improvements in the sensitivity and specificity of gene structure identification.
Current Opinion in Structural BiologyHidden Markov models
1,400 Citations1996Sean R. Eddy
'Profiles' of protein structures and sequence alignments can detect subtle homologies and are beginning to appear in the fields of protein-structure prediction and large-scale genome-sequence analysis.
Proceedings of the National Academy of SciencesProfile analysis: detection of distantly related proteins.
1,339 Citations1987Michael Gribskov, A. McLachlan +1 more
Tests with globin and immunoglobulin sequences show that profile analysis can distinguish all members of these families from all other sequences in a database containing 3800 protein sequences.
BioinformaticsBiological sequence analysis
1,251 Citations2021Samvedna Shukla, Bhawana Mishra +2 more
The basics of sequence alignment, algorithms, and tools available for biological sequence alignment are discussed, which has important application in disease diagnosis, biomaterial engineering, genetic engineering, and drug discovery.
Proteins Structure Function and BioinformaticsPfam: A comprehensive database of protein domain families based on seed alignments
1,236 Citations1997Erik L. L. Sonnhammer, Sean R. Eddy +1 more
A database based on hidden Markov model profiles (HMMs), which combines high quality and completeness, and a large number of previously unannotated proteins from the Caenorhabditis elegans genome project were classified.
Bioinformatics the machine learning approach
929 Citations1998Pierre Baldi, Søren Brunak
Molecular Biology and EvolutionA Hidden Markov Model approach to variation among sites in rate of evolution
862 Citations1996Joe Felsenstein, Gary A. Churchill
The method of Hidden Markov Models is used to allow for unequal and unknown evolutionary rates at different sites in molecular sequences and it is shown how to use the Newton-Raphson method to estimate branch lengths of a phylogeny and to infer from a phylogenies what assignment of rates to sites has the largest posterior probability.
Computers & ChemistryGENMARK: Parallel gene recognition for both DNA strands
742 Citations1993Mark Borodovsky, James D. McIninch
The initial idea of the method combines the specific Markov models of coding and non-coding region together with Bayes' decision making function and allows easy generalization for employing of higher order Markov chain models.
Nucleic Acids ResearchComputer methods to locate signals in nucleic acid sequences
665 Citations1984Rodger Staden
The methods are of use both to those trying to interpret the function of newly determined sequences and to those studying the molecular mechanisms involved in the recognition of these special signal sequences.
Proceedings of the National Academy of SciencesHidden Markov models of biological primary sequence information.
458 Citations1994Pierre Baldi, Yves Chauvin +2 more
A smooth and convergent algorithm is introduced to iteratively adapt the transition and emission parameters of the models from the examples in a given family, yielding an effective multiple-alignment algorithm which requires O(KN2) operations, linear in the number of sequences.
PubMedA generalized hidden Markov model for the recognition of human genes in DNA.
392 Citations1996David Kulp, David Haussler +2 more
A Generalized Hidden Markov Model (GHMM) provides the framework for describing the grammar of a legal parse of a DNA sequence and provides simple solutions for integrating cardinality constraints, reading frame constraints, "indels", and homology searching.
Bulletin of Mathematical BiologyStochastic models for heterogeneous DNA sequences
365 Citations1989Gary A. Churchill
The DNA sequence is viewed as a stochastic process with local compositional properties determined by the states of a hidden Markov chain, a discrete-state, discreteoutcome version of a general model for non-stationary time series proposed by Kitagawa (1987).
Computers & ChemistryA flexible motif search technique based on generalized profiles
313 Citations1996Philipp Bucher, Kevin Karplus +2 more
A flexible motif search technique is presented which has a generalized profile syntax serving as a motif definition language and a motif search method specifically adapted to the problem of finding multiple instances of a motif in the same sequence.
Nucleic Acids ResearchA hidden Markov model that finds genes in<i><i>E.coli</i></i>DNA
312 Citations1994Anders Krogh, I. Saira Mian +1 more
The hidden Markov model finds the exact locations of about 80% of the known E. coli genes, and approximate locations for about 10%, and finds several potentially new genes and locates several places were insertion or deletion errors/and or frameshifts may be present in the contigs.
PubMedTwo methods for improving performance of an HMM and their application for gene finding.
294 Citations1997Anders Krogh
A new (approximative) algorithm is described, which finds the most probable prediction summed over all paths yielding the same prediction, and it is shown that these methods contribute significantly to the high performance of HMMgene.
Proceedings of the National Academy of SciencesDetection of conserved segments in proteins: iterative scanning of sequence databases with alignment blocks.
287 Citations1994Roman L. Tatusov, Stephen F. Altschul +1 more
An approach to analyzing protein sequence databases that, starting from a single uncharacterized sequence or group of related sequences, generates blocks of conserved segments that are used to detect novel conserved motifs of potential biological importance is described.
Journal of Computational BiologyMaximum Discrimination Hidden Markov Models of Sequence Consensus
246 Citations1995Sean R. Eddy, Graeme Mitchison +1 more
The maximum discrimination method for building hidden Markov models (HMMs) of protein or nucleic acid primary sequence consensus compensates for biased representation in sequence data sets, superseding the need for sequence weighting methods.
Journal of Computational BiologyFinding Genes in DNA with a Hidden Markov Model
227 Citations1997John Henderson, Steven L. Salzberg +1 more
A new Hidden Markov Model (HMM) system for segmenting uncharacterized genomic DNA sequences into exons, introns, and intergenic regions, called VEIL (Viterbi Exon-Intron Locator), obtains an overall accuracy on test data of 92% of total bases correctly labelled.
Protein ScienceStructural analysis based on state‐space modeling
190 Citations1993Collin M. Stultz, James V. White +1 more
The method has two important advantages: the probability of each residue being in each of the modeled secondary structural elements is computed using the totality of the amino acid sequence, and these probabilities are consistent with prior knowledge of realizable domain folds as encoded in each model.
PubMedUsing Dirichlet mixture priors to derive hidden Markov models for protein families.
170 Citations1993Michael Brown, Richard Hughey +4 more
A Bayesian method for estimating the amino acid distributions in the states of a hidden Markov model (HMM) for a protein family or the columns of a multiple alignment of that family is introduced, which can improve the quality of HMMs produced from small training sets.
GenomicsGene Structure Prediction by Linguistic Methods
168 Citations1994Shan Dong, David B. Searls
A grammar and parser for eukaryotic protein-encoding genes is described, which by some measures is as effective as current connectionist and combinatorial algorithms in predicting gene structures for sequence database entries.
Mathematical BiosciencesProtein classification by stochastic modeling and optimal filtering of amino-acid sequences
150 Citations1994James V. White, Collin M. Stultz +1 more
This work solves the problem of determining, from a set of candidates, which model is the most probable generator of a protein's entire amino-acid sequence, and employs a nonlinear, optimal filtering algorithm, which is suited for implementation on parallel computer architectures.
Trends in GeneticsFinding genes by computer: the state of the art
146 Citations1996James W. Fickett
The main kinds of tools; their working principles, strengths and limitations; and how combined evidence from multiple tools can aid in optimum gene identification are described.
Computers & ChemistryHidden Markov chains and the analysis of genome structure
135 Citations1992Gary A. Churchill
Analysis of the structure of some small complete genomes and a human genome segment using a hidden Markov chain model finds a variety of discrete compositional domains and their correlations with genome function are explored.
Journal of Molecular BiologyUsing Evolutionary Trees in Protein Secondary Structure Prediction and Other Comparative Sequence Analyses
124 Citations1996Nick Goldman, Jeffrey L. Thorne +1 more
A hidden Markov model approach to secondary structure prediction is presented that more fully uses the evolutionary information contained in protein sequence alignments to improve inferences.
Protein modeling using hidden Markov models: analysis of globins
92 Citations2002David Haussler, Anders Krogh +2 more
A variant of the expectation maximization algorithm known as the Viterbi algorithm is used to obtain the statistical model from the unaligned sequences, and a multiple alignment of the 400 sequences and 225 other globin sequences was obtained that agrees almost perfectly with a structural alignment by D Bashford et al. (1987).
Journal of Molecular BiologyNaturally Occurring Nucleosome Positioning Signals in Human Exons and Introns
80 Citations1996Pierre Baldi, Søren Brunak +2 more
The structural implications of a periodic pattern found in human exons and introns by hidden Markov models are described and the relation between the bending potential of coding and non-coding regions and its impact on the translational positioning of nucleosomes and the recognition of genes by the transcriptional machinery is discussed.
Journal of Computational BiologyStatistical Modeling, Phylogenetic Analysis and Structure Prediction of a Protein Splicing Domain Common to Inteins and Hedgehog Proteins
75 Citations1997Jacob Z. Dalgaard, Michael J. Moser +2 more
A specific and sensitive hidden Markov model of protein splicing domain shared by inteins and the hedgehog proteins has been trained and employed for further analysis and secondary and tertiary structure predictions suggest that the domain has a structure similar to a beta-sandwich.
Nucleic Acids ResearchA branch point consensus from Arabidopsis found by non-circular analysis allows for better prediction of acceptor sites
69 Citations1997Niels Tolstrup
Despite the fact that branch point consensus sequences in plants are weak, it is shown that a prediction scheme incorporating them leads to a substantial improvement in the recognition of true acceptor sites; the false positive rate is reduced by a factor of 2.5, an indication that the consensus found here is the genuine one and that the branch point does play a role in the proper recognition of the acceptor site in plants.
PubMedCharacterization of prokaryotic and eukaryotic promoters using hidden Markov models.
61 Citations1996Anders Gorm Pedersen, Pierre Baldi +2 more
It is found that HMMs trained on such subclasses of Escherichia coli promoters (specifically, the so-called sigma 70 and sigma 54 classes) give an excellent classification of unknown promoters with respect to sigma-class.
Journal of Molecular BiologyProtein topology recognition from secondary structure sequences: application of the hidden markov models to the alpha class proteins
47 Citations1997Valentina Di Francesco, J. Garnier +1 more
The study indicates that the HMMs are useful for protein topology recognition even when no detectable primary amino acid sequence similarity is present, and will become increasingly useful as the accuracy of secondary prediction algorithms is improved.
PubMedIntegrating database homology in a probabilistic gene structure model.
44 Citations1997David Kulp, David Haussler +2 more
An improved stochastic model of genes in DNA is presented, a method for integrating database homology into the probabilistic framework is described, and a generalized hidden Markov model (GHMM) describes the grammar of a legal parse of a DNA sequence.
Current BiologyFibronectin type III domains in yeast detected by a hidden Markov model
30 Citations1996Alex Bateman, Cyrus Chothia
Large-scale proteincharacterization projects will definethe effect of factors and the utility of sequence tags forprotein identification and the accuracy of sequence data that can be obtained from proteins purified from two-dimensional gels, and theuracy of prediction of protein openreading frames in genome/proteomedatabases.
PubMedEvaluating regularizers for estimating distributions of amino acids.
23 Citations1995Kevin Karplus
One of the substitution matrix variants, which added pseudocounts and scaled counts, does almost as well as the best known Dirichlet mixtures, but with a lower computation cost.
DNA ResearchDetection of Short Protein Coding Regions within the Cyanobacterium Genome: Application of the Hidden Markov Model
22 Citations1996Tetsushi Yada
GeneHacker, a gene-finding program based on the hidden Markov model, was clearly superior to GeneMark in detecting very short CDSs corresponding to genes in a 1.0 mega contiguous sequence of cyanobacterium Synechocystis sp.
DNA ResearchAnalysis of Sequence Patterns Surrounding the Translation Initiation Sites on Cyanobacterium Genome Using the Hidden Markov Model
11 Citations1997Tetsushi Yada
This work extracted sequence patterns surrounding translation initiation sites of Cyanobacterium using the computer program YEBIS and found that the second amino acid could be classified into two types, one of which had C as their second codon while another of which has a nucleotide distribution relatively similar to the distribution among amino acids in the 72 proteins.