Methods for Computational Gene Prediction - Softcover

Majoros, William H.

Softcover

ISBN 10: 0521706947 ISBN 13: 9780521706940

Publisher: Cambridge University Press, 2007

Synopsis

Inferring the precise locations and splicing patterns of genes in DNA is a difficult but important task, with broad applications to biomedicine. The mathematical and statistical techniques that have been applied to this problem are surveyed and organized into a logical framework based on the theory of parsing. Both established approaches and methods at the forefront of current research are discussed. Numerous case studies of existing software systems are provided, in addition to detailed examples that work through the actual implementation of effective gene-predictors using hidden Markov models and other machine-learning techniques. Background material on probability theory, discrete mathematics, computer science, and molecular biology is provided, making the book accessible to students and researchers from across the life and computational sciences. This book is ideal for use in a first course in bioinformatics at graduate or advanced undergraduate level, and for anyone wanting to keep pace with this rapidly-advancing field.

About this title

Book Description

This advanced text describes in detail the algorithms and models used to identify genes in genomic DNA sequences. It provides the underlying theory of both established techniques and also methods at the forefront of current research and is ideal for use in a first course in bioinformatics or computational biology.

From the Author

This book is still by far the most comprehensive and accessible text on the subject, including extensive coverage of comparative gene finding, implementation details and pitfalls, technical primers for non-computational readers, several hundred student exercises, and a full chapter devoted to a "toy gene finder" that the reader can implement in a few hundred lines of code.  The online supplement contains additional chapters devoted to the most recent developments in gene finding, including Conditional Random Fields, as well as data and software for use in practical exercises and projects.
Contents 

Preface 1. Introduction 1.1 The Central Dogma of Molecular Biology 1.2 Evolution 1.3 Genome Sequencing and Assembly 1.4 Genomic Annotation 1.5 The Problem of Computational Gene Prediction Exercises 2. Mathematical Preliminaries 2.1 Numbers and Functions 2.2 Logic and Boolean Algebra 2.3 Sets 2.4 Algorithms and Pseudocode 2.5 Optimization 2.6 Probability 2.7 Some Important Distributions 2.8 Parameter Estimation 2.9 Statistical Hypothesis Testing 2.10 Information 2.11 Computational Complexity 2.12 Dynamic Programming 2.13 Searching and Sorting 2.14 Graphs 2.15 Languages and Parsing Exercises 3. Overview of Gene Prediction 3.1 Genes, Exons, and Coding Segments 3.2 Orientation 3.3 Phase and Frame 3.4 Gene Finding as Parsing 3.5 Common Assumptions in Gene Prediction Exercises4. Gene Finder Evaluation 4.1 Testing Protocols 4.2 Evaluation Metrics Exercises 5. A Toy Exon Finder 5.1 The Toy Genome and its Toy Genes 5.2 Random Exon Prediction as a Baseline 5.3 Predicting Exons Based on {G,C} Bias 5.4 Predicting Exons Based on Codon Bias 5.5 Predicting Exons Based on Codon Bias and WMM Score 5.6 Summary Exercises 6. Hidden Markov Models 6.1 Introduction to HMM's 6.1.1 An Illustrative Example 6.1.2 Representing HMM's 6.2 Decoding and Similar Problems 6.2.1 Finding the Most Probable Path 6.2.2 Computing the Probability of a Sequence 6.3 Training with Labeled Sequences 6.4 Example: Building an HMM for Gene Finding 6.5 Case Study: VEIL and UNVEIL 6.6 Using Ambiguous Models 6.6.1 Viterbi Training 6.6.2 Merging Submodels 6.6.3 Baum-Welch Training 6.6.3.1 Naive Baum-Welch Algorithm 6.6.3.2 Baum-Welch with Scaling 6.7 Higher-order HMM's 6.7.1 Labeled Sequence Training for Higher-order HMM's 6.7.2 Decoding with Higher-order HMM's 6.8 Variable-order HMM's 6.8.1 Back-off Models 6.8.2 Example: Incorporating Variable-order Emissions 6.8.3 Interpolated Markov Models 6.9 Discriminative Training of HMM's 6.10 Posterior Decoding of HMM's Exercises 7. Signal and Content Sensors 7.1 Overview of Feature Sensing 7.2 Content Sensors 7.2.1 Markov Chains 7.2.2 Markov Chain Implementation 7.2.3 Improved Markov Chain Implementation 7.2.4 Three-periodic Markov Chains 7.2.5 Interpolated Markov Chains 7.2.6 Nonstationary Markov Chains 7.3 Signal Sensors 7.3.1 Weight Matrices 7.3.2 Weight Array Matrices 7.3.3 Windowed Weight Array Matrices 7.3.4 Local Optimility Criterion 7.3.5 Coding-Noncoding Boundaries 7.3.6 Case Study: GeneSplicer 7.3.7 Maximal Dependence Decomposition 7.3.8 Probabilistic Tree Models 7.3.9 Case Study: Signal Sensing in GENSCAN 7.4 Other Methods of Feature Sensing 7.5 Case Study: Bacterial Gene Finding Exercises 8. Generalized Hidden Markov Models 8.1 Generalization and its Advantages 8.2 Typical Model Topologies 8.2.1 One Exon Model or Four? 8.2.2 One Strand or Two? 8.3 Decoding with a GHMM 8.3.1 PSA Decoding 8.3.2 DSP Decoding 8.3.3 Equivalence of DSP and PSA 8.3.4 A DSP Example 8.3.5 Shortcomings of DSP and PSA 8.4 Higher-fidelity Modeling 8.4.1 Modeling Isochores 8.4.2 Explicit Modeling of Noncoding Lengths 8.5 Prediction with an ORF Graph 8.5.1 Building the Graph 8.5.2 Decoding with a Graph 8.5.3 Extracting Suboptimal Parses 8.5.4 Posterior Decoding for GHMM's 8.5.5 The ORF Graph as a Data Interchange Format 8.6 Training a GHMM 8.6.1 Maximum Likelihood Training for GHMM's 8.6.2 Discriminative Training for GHMM's 8.7 Example: GHMM Versus HMM Exercises 9. Comparative Gene Finding 9.1 Informant Techniques 9.1.1 Case Study: TWINSCAN 9.1.2 Case Study: GenomeScan 9.1.3 Case Study: SGP-2 9.1.4 Case Study: HMMgene 9.1.5 Case Study: GENIE 9.2 Combiners 9.2.1 Case Study: JIGSAW 9.2.2 Case Study: GAZE 9.3 Alignment-based Prediction 9.3.1 Case Study: ROSETTA 9.3.2 Case Study: SGP-1 9.3.3 Case Study: CEM 9.4 Pair HMM's 9.4.1 Case Study: Doublescan 9.5 Generalized Pair HMM's 9.5.1 Case Study: TWAIN 9.6 Phylogenomic Gene Finding 9.6.1 Phylogenetic HMM's 9.6.2 Decoding with a PhyloHMM 9.6.3 Evolution Models 9.6.4 Parameterization of Rate Matrices 9.6.5 Estimation of Evolutionary Parameters 9.6.6 Modeling Higher-order Dependencies 9.6.7 Enhancing Discriminative Power 9.6.8 Selection of Informants 9.7 Auto-annotation Pipelines 9.8 Looking Toward the Future Exercises 10. Machine Learning Methods 10.1 Overview of Automatic Classification 10.2 K-Nearest Neighbors 10.3 Naive Bayes Models 10.4 Bayesian Networks 10.5 Neural Networks 10.5.1 Case Study: GRAIL 10.6 Decision Trees 10.6.1 Case Study: GlimmerM 10.7 Linear Discriminant Analysis 10.8 Quadratic Discriminant Analysis 10.9 Multivariate Regression 10.10 Logistic Regression 10.11 Regularized Logistic Regression 10.12 Genetic Programming 10.13 Simulated Annealing 10.14 Support Vector Machines 10.15 Hill Climbing with the GSL 10.16 Feature Selection and Dimensionality Reduction 10.17 Applications Exercises 11. Tips and Tricks 11.1 Boosting 11.2 Bootstrapping 11.3 Modeling Additional Gene Features 11.4 Masking Repeats Exercises12. Advanced Topics 12.1 Alternative Splicing and Transcription 12.2 Prediction of Noncoding Genes 12.3 Promoter Prediction 12.4 Generative Versus Discriminative Modeling 12.5 Parallelization and Grid Computing Exercises Appendix A - Online Resources A.1 Official Book Website A.2 Open Source Gene Finders A.3 Gene-finding Web Sites A.4 Gene-finding Bibliographies References Index 

Edition details

• Publisher: Cambridge University Press
• Publication date: 2007
• ISBN 10: 0521706947
• ISBN 13: 9780521706940
• Binding: Paperback
• Language: English
• Edition number: 1
• Number of pages: 448