Bioinformatics: the machine learning approach

Bioinformatics AdaptiveComputation andMachineLearning ThomasDietterich, Editor Christopher Bishop, David Heckerman, Michael Jordan, and Michael Kearns, AssociateEditors Bioinformatics: TheMachineLearningApproach,PierreBaldi andSøren Brunak ReinforcementLearning: AnIntroduction,Richard S. Sutton andAndrew G. Barto Pierre Baldi Søren Brunak Bioinformatics The Machine Learning Approach ABradford Book TheMITPress Cambridge, Massachusetts London,England (cid:1)c 2001Massachusetts Institute ofTechnology All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. Thisbookwas setin Lucida bythe authors and was printed and bound in the United States ofAmerica. Library ofCongressCataloging-in-Publication Data Baldi,Pierre. Bioinformatics : the machinelearning approach /PierreBaldi, SørenBrunak.—2nd ed. p. cm.—(Adaptive computation and machinelearning) "ABradford Book" Includesbibliographical references(p. ). ISBN0-262-02506-X(hc. : alk. paper) 1. Bioinformatics. 2. Molecular biology—Computer simulation. 3. Molecular biology—Mathematical models. 4. Neural networks (Computer science). 5. Machinelearning. 6. Markovprocesses. I.Brunak,Søren. II.Title. III.Series. QH506.B35 2001 572.8(cid:2)01(cid:2)13—dc21 2001030210 Series Foreword The?rstbookinthenewseriesonAdaptive Computation andMachineLearn- ing, Pierre Baldi and Søren Brunak’s Bioinformatics provides a comprehensive introduction to the application of machine learning in bioinformatics. The development oftechniques for sequencingentire genomesis providing astro- nomical amounts of DNA and protein sequence data that have the potential to revolutionize biology. To analyze this data, new computational tools are needed—tools that apply machine learning algorithms to ?tcomplex stochas- tic models. Baldi and Brunak provide a clear and uni?edtreatment ofstatisti- cal and neural network models for biological sequencedata. Students and re- searchersinthe?eldsofbiologyandcomputersciencewill?ndthisavaluable andaccessible introduction tothesepowerful newcomputational techniques. The goal of building systems that can adapt to their environments and learn from their experience has attracted researchers from many ?elds, in- cluding computer science, engineering, mathematics, physics, neuroscience, andcognitivescience. Outofthisresearchhascomeawidevariety oflearning techniquesthathave thepotential totransform manyscienti?cand industrial ?elds. Recently, several research communities have begun to converge on a common set of issues surrounding supervised, unsupervised, and reinforce- ment learning problems. The MIT Press series on Adaptive Computation and MachineLearningseekstounifythemanydiversestrandsofmachinelearning researchand tofosterhighquality research and innovative applications. ThomasDietterich ix Contents SeriesForeword ix Preface xi 1 Introduction 1 1.1 Biological Data inDigital Symbol Sequences 1 1.2 Genomes—Diversity, Size, and Structure 7 1.3 Proteinsand Proteomes 16 1.4 OntheInformation ContentofBiological Sequences 24 1.5 Prediction ofMolecular Functionand Structure 43 2 Machine-LearningFoundations: The Probabilistic Framework 47 2.1 Introduction: Bayesian Modeling 47 2.2 TheCoxJaynesAxioms 50 2.3 Bayesian Inferenceand Induction 53 2.4 ModelStructures: Graphical Modelsand OtherTricks 60 2.5 Summary 64 3 Probabilistic ModelingandInference: Examples 67 3.1 TheSimplest SequenceModels 67 3.2 Statistical Mechanics 73 4 MachineLearningAlgorithms 81 4.1 Introduction 81 4.2 Dynamic Programming 82 4.3 Gradient Descent 83 4.4 EM/GEM Algorithms 84 4.5 Markov-Chain Monte-Carlo Methods 87 4.6 Simulated Annealing 91 4.7 Evolutionary andGenetic Algorithms 93 4.8 LearningAlgorithms: MiscellaneousAspects 94 v vi Contents 5 NeuralNetworks: TheTheory 99 5.1 Introduction 99 5.2 Universal Approximation Properties 104 5.3 Priorsand Likelihoods 106 5.4 LearningAlgorithms: Backpropagation 111 6 NeuralNetworks: Applications 113 6.1 Sequence EncodingandOutputInterpretation 114 6.2 Sequence Correlations and NeuralNetworks 119 6.3 Prediction ofProtein SecondaryStructure 120 6.4 Prediction ofSignal Peptides andTheir Cleavage Sites 133 6.5 Applications forDNAand RNANucleotideSequences 136 6.6 Prediction PerformanceEvaluation 153 6.7 Di?erentPerformance Measures 155 7 HiddenMarkovModels: TheTheory 165 7.1 Introduction 165 7.2 PriorInformation and Initialization 170 7.3 Likelihoodand BasicAlgorithms 172 7.4 LearningAlgorithms 177 7.5 Applications ofHMMs: General Aspects 184 8 HiddenMarkovModels: Applications 189 8.1 ProteinApplications 189 8.2 DNAand RNAApplications 209 8.3 Advantages and Limitations ofHMMs 222 9 Probabilistic GraphicalModelsinBioinformatics 225 9.1 TheZooofGraphical ModelsinBioinformatics 225 9.2 MarkovModelsandDNA Symmetries 230 9.3 MarkovModelsandGeneFinders 234 9.4 Hybrid Models and Neural Network Parameterization of Graphical Models 239 9.5 TheSingle-ModelCase 241 9.6 Bidirectional Recurrent Neural Networks for Protein Sec- ondary Structure Prediction 255 10Probabilistic Modelsof Evolution: PhylogeneticTrees 265 10.1 Introduction toProbabilistic ModelsofEvolution 265 10.2 Substitution Probabilities and Evolutionary Rates 267 10.3 Rates ofEvolution 269 10.4 Data Likelihood 270 10.5 Optimal Treesand Learning 273 Contents vii 10.6 Parsimony 273 10.7 Extensions 275 11Stochastic GrammarsandLinguistics 277 11.1 Introduction toFormal Grammars 277 11.2 Formal Grammars and theChomskyHierarchy 278 11.3 Applications ofGrammars toBiologicalSequences 284 11.4 PriorInformation and Initialization 288 11.5 Likelihood 289 11.6 LearningAlgorithms 290 11.7 Applications ofSCFGs 292 11.8 Experiments 293 11.9 FutureDirections 295 12MicroarraysandGeneExpression 299 12.1 Introduction toMicroarray Data 299 12.2 Probabilistic ModelingofArray Data 301 12.3 Clustering 313 12.4 GeneRegulation 320 13Internet Resources andPublic Databases 323 13.1 A Rapidly ChangingSetofResources 323 13.2 Databases overDatabases and Tools 324 13.3 Databases overDatabases inMolecular Biology 325 13.4 Sequence andStructure Databases 327 13.5 Sequence Similarity Searches 333 13.6 Alignment 335 13.7 Selected Prediction Servers 336 13.8 Molecular BiologySoftware Links 341 13.9 Ph.D. Coursesover theInternet 343 13.10 Bioinformatics Societies 344 13.11 HMM/NNsimulator 344 A Statistics 347 A.1 DecisionTheoryand LossFunctions 347 A.2 Quadratic LossFunctions 348 A.3 TheBias/Variance Trade-o? 349 A.4 CombiningEstimators 350 A.5 Error Bars 351 A.6 Su?cientStatistics 352 A.7 Exponential Family 352 A.8 Additional Useful Distributions 353 viii Contents A.9 Variational Methods 354 B Information Theory,Entropy,andRelative Entropy 357 B.1 Entropy 357 B.2 Relative Entropy 359 B.3 Mutual Information 360 B.4 Jensen’sInequality 361 B.5 Maximum Entropy 361 B.6 Minimum Relative Entropy 362 C Probabilistic GraphicalModels 365 C.1 Notation andPreliminaries 365 C.2 TheUndirected Case: MarkovRandom Fields 367 C.3 TheDirected Case: Bayesian Networks 369 D HMMTechnicalities,Scaling,Periodic Architectures, State Functions,andDirichlet Mixtures 375 D.1 Scaling 375 D.2 PeriodicArchitectures 377 D.3 State Functions: Bendability 380 D.4 Dirichlet Mixtures 382 E GaussianProcesses,Kernel Methods,andSupport Vector Machines 387 E.1 Gaussian ProcessModels 387 E.2 Kernel MethodsandSupport VectorMachines 389 E.3 TheoremsforGaussian Processesand SVMs 395 F SymbolsandAbbreviations 399 References 409 Index 447