Comparative Gene Finding: Models, Algorithms and Implementation (Computational Biology)

Comparative genomics is an emerging field, which is being fed by an explosion in the number of possible biological sequences. This has led to an immense demand for faster, more efficient and more robust computer algorithms to analyze this large amount of data. This unique text/reference describes the state of the art in computational gene finding, with a particular focus on comparative approaches. Providing both an overview of the various methods that are applied in the field, and a concise guide on how computational gene finders are built, the book covers a broad range of topics from probability theory, statistics, information theory, optimization theory and numerical analysis. The text assumes the reader has some background in bioinformatics, especially in mathematics and mathematical statistics. A basic knowledge of analysis, probability theory and random processes would also aid the reader. **Topics and features:** * Describes how algorithms and sequence alignments can be combined to improve the accuracy of gene finding * Introduces the basic biological terms and concepts in genetics, and provides an historical overview of algorithm development * Explores the gene features most commonly captured by a computational gene model, and describes the most important sub-models used * Discusses the algorithms most commonly used for single-species gene finding * Investigates approaches to pairwise and multiple sequence alignments * Explains the basics of parameter training, covering a number of the different parameter estimation and optimization techniques commonly used in gene finding * Illustrates how to implement a comparative gene finder, explaining the different steps and various accuracy assessment measures used to debug and benchmark the software A useful text for postgraduate students, this book provides valuable insights and examples for researchers wishing to enter the field quickly. In addition to the specific focus on the algorithmic details surrounding computational gene finding, readers obtain an introduction to the fundamentals of computational biology and biological sequence analysis, as well as an overview of the important mathematical and statistical applications in bioinformatics. **Dr. Marina Axelson-Fisk** is an Associate Professor at the Department of Mathematical Sciences of Chalmers University of Technology, Gothenburg, Sweden. Springer cover-large.jpg 1 front-matter.pdf 2 Preface 7 Acknowledgments 9 Contents 10 Acronyms 14 fulltext.pdf 15 Introduction 15 Some Basic Genetics 15 The Central Dogma 17 The Structure of a Gene 19 How Many Genes Do We Have? 21 Problems of Gene Definitions 25 The Gene Finding Problem 26 Comparative Gene Finding 28 History of Algorithm Development 29 To Build a Gene Finder 32 References 35 fulltext_2.pdf 41 Single Species Gene Finding 41 Hidden Markov Models (HMMs) 41 Markov Chains 42 Discrete-Time Markov Chains 42 Stationarity and Reversibility 48 Continuous-Time Markov Chains 50 Hidden Markov Models 53 Dynamic Programming 56 Silent Begin and End States 58 The Forward Algorithm 59 The Backward Algorithm 59 The Viterbi Algorithm 61 EasyGene: A Prokaryotic Gene Finder 63 Posterior Decoding 65 Statistical Significance of Predictions 65 Generalized Hidden Markov Models (GHMMs) 66 Preliminaries 66 The Forward and Backward Algorithms 68 The Forward Variables 68 The Backward Variables 70 The Viterbi Algorithm 70 Genscan: A GHMM-Based Gene Finder 71 Sequence Generation Algorithm 74 Reducing Computational Complexity 74 Exon Probabilities 78 Interpolated Markov Models (IMMs) 81 Preliminaries 81 Linear and Rational Interpolation 82 GLIMMER: A Microbial Gene Finder 83 Gene Prediction 84 Training the IMM 85 GlimmerM 86 Neural Networks 86 Biological Neurons 87 Artificial Neurons and the Perceptron 88 Multi-Layer Neural Networks 90 GRAIL: A Neural Network-Based Gene Finder 91 Decision Trees 93 Classification 94 Decision Tree Learning 95 MORGAN: A Decision Tree-Based Gene Finder 99 References 100 fulltext_3.pdf 103 Sequence Alignment 103 Pairwise Sequence Alignment 103 Dot Plot Matrix 105 Nucleotide Substitution Models 106 The Jukes-Cantor Model 108 The Kimura Model 109 The Felsenstein Model 110 The Tamura and Nei Model 111 General Time-Reversible (GTR) Model 111 Amino Acid Substitution Models 112 The PAM Matrix 113 The BLOSUM Matrix 117 The GONNET matrix 120 Gap Models 120 The Needleman-Wunsch Algorithm 122 Needleman-Wunsch Using Affine Gaps 124 The Smith-Waterman Algorithm 126 Pair Hidden Markov Models (PHMMs) 128 Preliminaries 128 The Forward, Backward, and Viterbi Algorithms 130 Database Similarity Searches 132 FASTA 132 BLAST 134 Gapped BLAST 136 PSI-BLAST 136 The Significance of Alignment Scores 137 Multiple Sequence Alignment 138 Scoring Schemes 139 Sum-of-Pairs (SP) 141 Weighted Sum-of-Pairs (WSP) 141 Minimum Entropy 141 Gap Costs 142 Phylogenetic Trees 143 The Neighbor-Joining Method 143 Fitch-Margoliash 144 Dynamic Programming 145 The MSA Package 145 Progressive Alignments 147 Iterative Methods 150 Hidden Markov Models 153 SAM-Sequence Alignment and Modeling 153 Genetic Algorithms 155 Simulated Annealing 158 Alignment Profiles 161 Standard Profiles 161 Profile HMMs 163 Scoring a New Sequence 164 References 165 fulltext_4.pdf 170 Comparative Gene Finding 170 Similarity-Based Gene Finding 170 GenomeScan: GHMM-Based Gene Finding Using Homology 171 Twinscan: GHMM-Based Gene Finding Using Informant Sequences 173 Heuristic Cross-Species Gene Finding 175 ROSETTA 175 Pair Hidden Markov Models (PHMMs) 176 DoubleScan: A PHMM-Based Comparative Gene Finder 177 The State Space 177 The Stepping Stone Algorithm 179 Generalized Pair Hidden Markov Models (GPHMMs) 180 Preliminaries 180 The Forward, Backward and Viterbi Algorithms 181 SLAM: A GPHMM-Based Comparative Gene Finder 183 The State Space 183 Reducing Computational Complexity 185 Gene Mapping 187 Projector: A Gene Mapping Tool 187 GeneMapper-Reference Based Annotation 188 Multiple Sequence Gene Finding 189 N-SCAN: A Multiple Informant-Based Gene Finder 190 References 192 fulltext_5.pdf 194 Gene Structure Submodels 194 The State Space 194 The Exon States 195 Splice Sites 197 Introns and Intergenic Regions 198 Untranslated Regions (UTRs) 199 Promoters and PolyA-signals 200 State Length Distributions 201 Geometric and Negative Binomial Lengths 201 Empirical Length Distributions 204 Acyclic Discrete Phase Type Distributions 205 Sequence Content Sensors 209 GC-Content Binning 209 Start Codon Recognition 210 Codon and Amino Acid Usage 211 K-Tuple Frequency Analysis 213 Markov Chain Content Sensors 214 Interpolated Markov Models 216 Splice Site Detection 217 Weight Matrices and Weight Array Models 217 Variable-Length Markov Models (VLMMs) 220 Maximal Dependence Decomposition (MDD) 222 The Position with the Strongest Influence 223 Score a New Sequence 227 Neural Networks 228 Linear Discriminant Analysis 230 Quadratic Discriminant Analysis (QDA) 230 Linear Discriminant Analysis (LDA) 231 Maximum Entropy 234 The Maximum Entropy Method 235 Application to Splice Site Detection 238 Iterative Scaling 239 Bayesian Networks 240 Preliminaries 240 Some Bayesian Theory 241 Training a Bayesian Network 244 Application to Splice Site Detection 245 Support Vector Machines 246 Linearly Separable Classes 247 Nearly Linear SVMs 250 Nonlinear SVMs 250 SVMs in Splice Site Detection 253 References 255 fulltext_6.pdf 258 Parameter Training 258 Introduction 258 Pseudocounts 259 The SAM Regularizer 260 Maximum Likelihood Estimation 261 HMM Training on Labeled Sequences 264 The Expectation-Maximization (EM) Algorithm 267 The Baum-Welch Algorithm 274 The Forward-Backward Algorithm 274 The Baum-Welch Algorithm 276 Gradient Ascent/Descent 278 The Backpropagation Algorithm 281 The Feed-Forward Step 283 The Backpropagation Step 285 The Gradient Descent Step 286 Several Training Patterns 286 Discriminative Training 287 Conditional Maximum Likelihood 287 Maximum Mutual Information 288 Minimum Classification Error 289 Gibbs Sampling 291 Gibbs Sampling for HMM Training 292 Simulated Annealing 293 Simulated Annealing for Training of HMMs 296 References 296 fulltext_7.pdf 298 Implementation of a Comparative Gene Finder 298 Program Structure 298 Command Line Arguments 299 Parameter Files 301 Candidate Exon Boundaries 303 Output Files 304 The GPHMM Model 305 Modeling Intron and Intergenic Pairs 305 Modeling Exon Pairs 307 Approximate Alignment 308 Accuracy Assessment 309 Possible Model Extensions 310 References 311 back-matter.pdf 312 Index 312 ISBN-13:,9781849961035 Comparative genomics is a new and emerging ?eld, and with the explosion of ava- able biological sequences the requests for faster, more ef?cient and more robust algorithms to analyze all this data are immense. This book is meant to serve as a self-contained instruction of the state-of-the-art of computational gene ?nding in general and of comparative approaches in particular. It is meant as an overview of the various methods that have been applied in the ?eld, and a quick introduction into how computational gene ?nders are built in general. A beginner to the ?eld could use this book as a guide through to the main points to think about when constructing a gene ?nder, and the main algorithms that are in use. On the other hand, the more experienced gene ?nder should be able to use this book as a reference to different methods and to the main components incorporated in these methods. I have focused on the main uses of the covered methods and avoided much of the technical details and general extensions of the models. In exchange I have tried to supply references to more detailed accounts of the different research areas touched upon. The book, however, makes no claim on being comprehensive. "Comparative genomics is an emerging field, which is being fed by an explosion in the number of possible biological sequences. This has led to an immense demand for faster, more efficient and more robust computer algorithms to analyze this large amount of data." "This unique text/reference describes the state of the art in computational gene finding, with a particular focus on comparative approaches. Providing both an overview of the various methods that are applied in the field, and a concise guide on how computational gene finders are built, the book covers a broad range of topics from probability theory, statistics, information theory, optimization theory and numerical analysis. The text assumes the reader has some background in bioinformatics, especially in mathematics and mathematical statistics. A basic knowledge of analysis, probability theory and random processes would also aid the reader."--Résumé de l'éditeur "Comparative genomics is an emerging field, which is being fed by an explosion in the number of possible biological sequences. This has led to an immense demand for faster, more efficient and more robust computer algorithms to analyze this large amount of data." "This unique text/reference describes the state of the art in computational gene finding, with a particular focus on comparative approaches. Providing both an overview of the various methods that are applied in the field, and a concise guide on how computational gene finders are built, the book covers a broad range of topics from probability theory, statistics, information theory, optimization theory and numerical analysis. The text assumes the reader has some background in bioinformatics, especially in mathematics and mathematical statistics. A basic knowledge of analysis, probability theory and random processes would also aid the reader."--Jacket Front Matter....Pages I-XV Introduction....Pages 1-26 Single Species Gene Finding....Pages 27-88 Sequence Alignment....Pages 89-155 Comparative Gene Finding....Pages 157-180 Gene Structure Submodels....Pages 181-244 Parameter Training....Pages 245-284 Implementation of a Comparative Gene Finder....Pages 285-298 Back Matter....Pages 299-304