Biological Sequence Analysis
Computational Biology, also called Bioinformatics, is a rapidly growing, interdisciplinary field posed to be of immense importance in the first decades of the 21-st century where megabytes of raw biological data (e.g., of genome sequences, protein conformations, etc.) can only be analyzed and interpreted using computer programs. Though bioinformatics applications concern molecular biology (and in the future certainly other fields, such as neurobiology), the methods used issue from statistics, computer science, and mathematics. For this reason, different texts treat different aspects of computational biology. For instance, the books of \textit{M. Waterman} [Introduction to computational biology: Maps, sequences and genomes. (1995; Zbl 0831.92011)], \textit{P. Baldi} and \textit{S. Brunak} [Bioinformatics - The machine learning approach. (1998)], \textit{J. Setubal} and \textit{J. Meidanis} [Introduction to computational molecular biology. (1997)] all have a different area of focus, where for instance Baldi and Brunak emphasize machine learning algorithms such as hidden Markov models, neural nets, and hybrid models. The current text under review is a welcome addition to existing books, and, as its title indicates, focuses mainly on probabilistic methods including Markov models, hidden Markov models, parsiminony and maximum likelihood phylogeny construction algorithms, stochastic context-free grammars, profiles, etc. The main application areas concern sequence alignment (pairwise and multiple), genomic motif recognition, phylogeny, and RNA secondary structure. The text is clearly aimed not only at an audience of statisticians, computer scientists and mathematicians, but also at practicing biologists interested in computational biology. To that end, though entirely rigorous, the book does an admirable job of suppressing certain mathematical details, which might otherwise be distracting to biologists; for instance, details about probability distributions (such as Dirichlet distributions), entropy, and the EM algorithm (Expectation-Maximization) are relegated to the last chapter. By these means, the book gains in general readability. Broadly speaking, the book is Bayesian in outlook -- given a certain prior probability distribution (such as compositional frequencies of amino acids), one computes a new posterior distribution using Bayesian learning (e.g. a stochastic model for a class of proteins, when given a training set of members of the class to be learned). There are 11 chapters in the book. Chapter 1 is an introduction to probability models, maximum likelihood and maximum a posteriori estimation. Simple examples concerning dice illustrate concepts such as the multinomial distribution for a wide audience. Chapter 2 concerns pairwise sequence alignment using dynamic programming methods (Needleman - Wunsch, Smith - Waterman, etc.). Chapter 3 concerns Markov chains and hidden Markov models (HMMs). In a hidden Markov model, one cannot observe the state of the model, but only an output symbol, where the output distribution depends on the state. Thus a stochastic model can be constructed for a protein family (say G-coupled receptor proteins), where with a certain probability, a particular amino acid symbol will be output at the \(i\)-th position of the chain. Chapter 4 explains how to perform pairwise sequence alignments using HMM's. Since pairwise sequence alignment is not typically computed using HMM's, this chapter is largely pedagogic and provides the reader with better intuition for later applications of HMM's in multiple sequence alignments. Chapters 5 and 6 concern the construction of profiles for database searches and survey some methods for multiple sequence alignments, known to be an \(NP\)-complete problem. For instance, given a training set of globin proteins, using HMMs one can construct a stochastic model of a globin, yielding a profile, used then to search for hits in a database. Chapters 7 and 8 present algorithms for phylogeny construction (clustering methods, maximum likelihood, parsimony, etc.). Chapter 9 concerns formal grammars -- transformational, regular, context-free, stochastic context-free, as these can be viewed as generalizations of HMMs. Chapter 10 covers RNA secondary structure prediction using dynamic programming and stochastic context-free grammars. The idea of applying grammars to describe RNA secondary structure goes back to Searls. The gist of the idea can be seen, in considering a hairpin loop \texttt{ACGUXXXXXACGU}, where base pairing is of the form \texttt{((((.....))))}. In this fashion, secondary structure is essentially a balanced parenthesis expression, hence generated by a context-free grammar of the form \(S \rightarrow (S)S | \mathtt{.} | \epsilon\). Placing probabilities on the grammar's production rules yields a stochastic context-free grammar, and the CYK or Early parser, along with the forward-backward method of HMMs, yields an efficient algorithm to learn the probabilities of rule applications given a training set. Finally, Chapter 11, as earlier mentioned, is essentially an appendix for the most important concepts from probability theory and statistics used for the algorithms of this text. Molecular biology, like quantum physics in the early part of the 20-th century, is now at the exciting stage where important contributions are comming from mathematics and the related fields of statistics and computer science. Any scientifically educated reader with an interest in understanding the algorithmic techniques of computational molecular biology -- used, for instance, after DNA amplification, to determine that Neanderthal was not a direct ancestor of H. sapiens in the work of Svante Pääbo -- should read this well-written and enjoyable classic.
- The adjusted Viterbi training for hidden Markov models
- Protein secondary structure prediction using three neural networks and a segmental semi-Markov model
- A grammatical approach to RNA-RNA interaction prediction
- A hidden Markov model applied to the protein 3D structure analysis
- Polarity formation by a higher order interaction Markov-like chain
- A segmental semi Markov model for protein secondary structure prediction
- Maximum likelihood analysis of algorithms and data structures
- Parsimonious hidden Markov models for matrix-variate longitudinal data
- Exact MLE and asymptotic properties for nonparametric semi-Markov models
- Inverting random functions
- Orphan gene finding -- an exon assembly approach.
- Exact distribution for the local score of a Markov chain
- An optimization approach to multiple sequence alignment
- On the state of the art in machine learning: A personal review
- Fast estimation of posterior probabilities in change-point analysis through a constrained hidden Markov model
- Witnessing the quasiperiodic-ordering transition of one-dimensional \(k\)-component Fibonacci sequences
- 2-adic clustering of the PAM matrix
- Selecting effective siRNA target sequences by using Bayes' theorem
- Computation of mutual information from hidden Markov models
- Lower bounds on the generalized central moments of the optimal alignments score of random sequences
- A statistical method for analysing cospeciation in tritrophic ecology using electrical circuit theory
- Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
- Latent tree models for hierarchical topic detection
- HMM with emission process resulting from a special combination of independent Markovian emissions
- Accelerating Viterbi algorithm on graphics processing units
- Generalization bounds for learning weighted automata
- Hardness of RNA folding problem with four symbols
- Large-scale frequent stem pattern mining in RNA families
- A novel statistical measure for sequence comparison on the basis of \(k\)-word counts
- Information-theoretic uncertainty of SCFG-modeled folding space of the non-coding RNA
- Applying length-dependent stochastic context-free grammars to RNA secondary structure prediction
- Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
- Integrating Pareto optimization into dynamic programming
- siEDM: an efficient string index and search algorithm for edit distance with moves
- Lower bounds for moments of global scores of pairwise Markov chains
- Inference in population genetics using forward and backward, discrete and continuous time processes
- Reconstructing trees from subtree weights.
- Averaging fuzzy biopolymers
- Characterization of protein primary sequences based on partial ordering
- Using Bayesian multinomial classifier to predict whether a given protein sequence is intrinsically disordered
- A fast algorithm for all-pairs Hamming distances
- Approximate p-values for local sequence alignments.
- Identification of genetic networks by strategic gene disruptions and gene overexpressions under a Boolean model.
- Trees and ultrametric spaces: A categorical equivalence
- Predicting partial customer churn using Markov for discrimination for modeling first purchase sequences
- Efficient identification of transcription factor binding sites with a graph theoretic approach
- Strong law of large numbers for hidden Markov chains indexed by Cayley trees
- Automatic identification of audio recordings based on statistical modeling
- gBoost: a mathematical programming approach to graph classification and regression
- Inference attacks on genomic privacy with an improved HMM and an RCNN model for unrelated individuals
- Strong law of large numbers for hidden Markov chains indexed by an infinite tree with uniformly bounded degrees
- Hidden Markov model with Markovian emission
- Improved DNA-versus-protein homology search for protein fossils
- A comprehensive survey and analysis of generative models in machine learning
- Hidden Markov models with binary dependence
- Compositional properties of alignments
- Information geometry approach to parameter estimation in hidden Markov model
- Order selection for regression-based hidden Markov model
- An impossibility result for phylogeny reconstruction from \(k\)-mer counts
- Estimation of steady-state quantities of an HMM with some rarely generated emissions
- A coarse-grained Markov chain is a hidden Markov model
- Statistical physics and representations in real and artificial neural networks
- Duality between the local score of one sequence and constrained hidden Markov model
- The Modular Subset-Sum Problem and the size of deletion correcting codes
- An ambiguity hierarchy of weighted context-free grammars
- Structured hierarchical models for probabilistic inference from perturbation screening data
- Comparison methods for branching and axillary flowering sequences
- Improving RNA secondary structure prediction via state inference with deep recurrent neural networks
- A causal discovery algorithm based on the prior selection of leaf nodes
- Implementation of a Markov model for phylogenetic trees
- Chernoff information between Gaussian trees
- Hidden Markov models for multivariate functional data
- Bayesian protein structure alignment
- Spectral graph features for the classification of graphs and graph sequences
- Greedy learning of latent tree models for multidimensional clustering
- Phylogenetic analysis of DNA sequences based on the generalized pseudo-amino acid composition
- Sequence comparison via polar coordinates representation and curve tree
- Analyzing ambiguity of context-free grammars
- Component-based discriminative classification for hidden Markov models
- On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
- POMDPs under probabilistic semantics
- Sequence annotation with HMMs: new problems and their complexity
- A disambiguation algorithm for weighted automata
- A survey of temporal data mining
- A time warping approach to multiple sequence alignment
- Extraction of high quality \(k\)-words for alignment-free sequence comparison
- Recursive stochastic games with positive rewards
- Penalized estimation in high-dimensional hidden Markov models with state-specific graphical models
- A note on probabilistic models over strings: the linear algebra approach
- A Markovian approach for the prediction of mouse isochores
- Case-factor diagrams for structured probabilistic modeling
- A fuzzy model of predicting RNA secondary structure
- Distributions associated with general runs and patterns in hidden Markov models
- Exact distribution of the local score for Markovian sequences
- Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms
- Estimation of a matrix of intensities for model of Markov process
- A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
- On some stochastic models for replication of character strings
- Identification of related gene/protein names based on an HMM of name variations
- A C\(++\) computational environment for biomolecular sequence management
This page was built for publication: Biological Sequence Analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4223050)