Enhancements to Hidden Markov Models for Gene Finding and Other Biological Applications by Tomas Vinar A thesis presented to the University of Waterloo in fulfilment of the thesis requirement for the degree of Doctor of Philosophy in Computer Science Waterloo, Ontario. 2005 © Tomas Vina 2005 ivi Library and Archives Canada Bibliotheque et Archives Canada Published Heritage Direction du Branch Patrimoine de l'édition 395 Wellington Street 395, rue Wellington Ottawa ON K1A 0N4 Ottawa ON K1A ON4 Canada Canada Your file Votre référence ISBN: 0-494-14634-6 Our file Notre référence ISBN: 0-494-14634-6 NOTICE: AVIS: The author has granted a non- L'auteur a accordé une licence non exclusive exclusive license allowing Library permettant a la Bibliotheque et Archives and Archives Canada to reproduce, Canada de reproduire, publier, archiver, publish, archive, preserve, conserve, sauvegarder, conserver, transmettre au public communicate to the public by par télécommunication ou par I'Internet, préter, telecommunication or on the Internet, distribuer et vendre des theses partout dans loan, distribute and sell theses le monde, a des fins commerciales ou autres, worldwide, for commercial or non- sur support microforme, papier, électronique commercial purposes, in microform, et/ou autres formats. paper, electronic and/or any other formats. The author retains copyright L'auteur conserve la propriété du droit d'auteur ownership and moral rights in et des droits moraux qui protége cette these.
Neither the thesis Ni la thése ni des extraits substantiels de nor substantial extracts from it celle-ci ne doivent étre imprimés ou autrement may be printed or otherwise reproduits sans son autorisation. reproduced without the author's permission. In compliance with the Canadian Conformément a la loi canadienne Privacy Act some supporting sur la protection de la vie privée, forms may have been removed quelques formulaires secondaires from this thesis. ont été enlevés de cette these.
While these forms may be included Bien que ces formulaires in the document page count, aient inclus dans la pagination, their removal does not represent il n'y aura aucun contenu manquant. any loss of content from the thesis. Canada AUTHOR’S DECLARATION FOR ELECTRONIC SUBMISSION OF A THESIS I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.
I understand that my thesis may be made electronically available to the public. il Abstract In this thesis, we present enhancements of hidden Markov models for the problem of finding genes in DNA sequences. Genes are the parts of DNA that serve as a template for synthesis of proteins. Thus, gene finding is a crucial step in the analysis of DNA sequencing data.
Hidden Markov models are a key tool used in gene finding. Yhis thesis presents three methods for extending the capabilities of hidden Markov models to better capture the sta- tistical properties of DNA sequences. In all three, we encounter limiting factors that lead to trade-offs between the model accuracy and those limiting factors. First, we build better models for recognizing biological signals in DNA sequences.
Our new models capture non-adjacent dependencies within these signals. In this case, the main limiting factor is the amount of training data: more training data allows more complex models. Second, we design methods for better representation of length distributions in hidden Markov models, where we balance the accuracy of the representation against the running time needed to find genes in novel sequences. Finally, we show that creating hidden Markov models with complex topologies may be detrimental to the prediction accuracy, unless we use more complex prediction algorithms.
However, such algorithms require longer running time, and in many cases the prediction problem is NP-hard. For gene finding this means that incorporating some of the prior biological knowledge into the model would require impractical running times. However, we also demonstrate that our methods can be used for solving other biological problems, where input sequences are short. As a model example to evaluate our methods, we built a gene finder ExonHunter that outperforms programs commonly used in genome projects.
ill Acknowledgements I would like to thank all the people, who contributed to this thesis. Thanks to both of my supervisors Ming Li and Dan Brown. During my years of PhD studies, they provided me with tremendous amount of support and extraordinary freedom to pursue my own curiosity, yet they were always eager to work on the problems with me and give me a guidance: to Brona Brejova. my wife, my best friend.
and also my closest research collaborator. I would also like to thank members of my committee Therese Bied], Ian Munro, Burkhard Morgenstern, and Romy Shioda for their guidance and insightful comments. Special thanks to people who helped me in the beginnings of my research career by many hours spent in helpful discussions: Jonathan Badger, Haoyvong Zhang, John Tsang, and Michael Hu. Thanks to Martin Demaine and Therese Biedl, who always encouraged me to start new things, and who helped me to set up bioinformatics problem sessions.
Special thanks to Therese, under whose guidance we wrote our first research paper. Thanks to all the other people with whom I had a pleasure to co-author research papers and reports: Jonathan Buss, Erik Demaine, Chrysanne DiMarco, Mohammadtaghi Haji- aghayi, Angele Hamel, Masud Hasan, lan Harrower, Sandra Romero Hidalgo, Gina Holguin, Joe D. Horton, Alejandro Lopez-Ortiz, and Cheryl Patten. but definitely not least, I would like to thank my parents, for supporting me and encouraging me in all my endeavors.
IV To my brother, who left us early.1 Sequence Annotation and Hidden Markov Models .1 Hidden Markov Models.2 Algorithms for Decoding Hidden Markov Models.1 Computing the Most Probable State Path.3 Combining Viterbi and Posterior Decoding.3 Training Hidden Markov Models.3 Beyond Maximum Likelihood .2 Introduction to Gene Finding .1 Statistical Properties of Genes in DNA Sequences .1 Differences in k-mer Composition .2 Conserved Signal Sequences .2 Previous Work: Programs for Ab Initio Gene Finding .3 Beyond Ab Initio Gene Finding .5 Experimental Verification of Gene Predictions .1 Methods Based on Random Sampling .2 Genome-Wide Analysis .3 Prediction Driven Methods .3 Hidden Markov Models for Gene Finding.3 Start and Stop Sites 2.4 Untranslated Regions and Intergenic Region .5 Putting the Pieces Together .0 vo VI 2 Higher Order Tree Models for Signal Recognition 35 2.1 Intra-signal Dependencies and HOT Models .2 Maximum Likelihood Training of£ HOT Models.1 HOT Models and Hypergraphs .2 Finding the Optimal Topology for Tree Models .3 Minimum Spanning Directed Hypertree is NP-hard .4 Finding the Optimal HOT Topology by Integer Programming .5 Greedy Heuristic for Finding a Good HOT Topology .1 Using Generative Models as Classifiers .3 Donor Site Experiments .4 Relationship Between Model Order and the Amount of Training Data 58 2.5 Acceptor Site Experiments.6 Signal Models in Gene Finding. an 63 Length Distributions in HMMs 65 3.1 Generalized HMMs with Explicit State Duration. Distributions with Geometric Tails 2. Maximum Likelihood Training.
Decoding HMMs with Geometric-Tail Lengths.3 Decoding Geometric-Tail Distributions with Large Values oft .4 Gadgets of States.1 Phase-type Distributions .2 Gadgets of States and the Viterbi Algorithm .5 Length Distributions of Complex Sub-models.1 A Viterbi Algorithm for Boxed HMMs. Boxed HMMs with Geometric-Tail Distributions.6 Summary and Experiments.000 00004 92 Finding the Most Probable Annotation 97 4.1 Comparing Decoding by the Most Probable Path and by the Most Probable Annotation 2.2 Finding the Most Probable Annotation is NP-hard .21 Proof of Lyngsø and Pedersen.2 Layered Graphs and the BEST-LAYER-COLORING Problem.3 From Laver Colorings toHMMs .4 Constructing a Small HIM that is NP-hard to Decode .3 Computing the Most Probable Annotation .1 Most Probable Extended Annotation .2 Critical Edge Condition .3 Silent States and the Critical Edge Condition .4 Applications of the EVA .5 Generalizing the EVA and the Critical Edge Condition. ee 126 5 Implementing ExonHunter 129 5.1 Hidden Markov Model of ExonHunter.2 Common Sequence Repeats. ga g k kg va 133 5.3 Performance of ExonHunter on Human Sequences .4 Performance of ExonHunter on Fruit Fly Sequences.
xa 136 6 Conclusion 137 A Datasets and Their Preparation 139 A.1 ENCODE Gene Prediction Workshop.2 Chromosome 22 Annotated with RefSeq .3 Augustus Training Set.4 SpliceDB Collection of Splice Site Signals.5 Fruit Fly Datasets 2. gà kg kg kg va 140 Bibliography 141 vill List of Figures 1.1 Example of a hidden Markov model.2 A simple HMM topology for transmembrane protein topology prediction .3 Central dogma of molecular biology .4 Translating nucleotide sequences to protein sequences .5 Summary of biological signals important for gene finding. cà và va kg na 19 1.7 Logo of 5’ (donor) splice site.8 Logo of 3’ (acceptor) splice site 2.9 Logo of region [—20, —5] before the acceptor splice site .10 Logo of translation start signal .11 Logo of translation stop signal.12 Example of exon model.13 Example oŸ an intron model.14 Start site model. gà kg kg kg vo 30 1.15 Stop site model .16 HMM for a sequence with a single gene on the forward strand .17 HMM for a multi gene sequence with genes on both strands .1 Pairwise dependencies in human donor splice site .2 Examples of different model topologies for donor signal .3 Minimum spanning directed hypertree is NP-hard .4 Minimum spanning directed hypertree is NP-hard (cont).9 Comparison of models inferred by integer programming and a greedy algorithm 50 2.6 Graphs comparing sensitivity and specificity .7 Comparison of donor site prediction for PWM-2 and HOT-2 .8 Detail of ROC curve for second order models of donor site.
actual fraction of true positives.10 The HOT-3 model dominates IDD model of donor site.11 Specificity of donor models at 90% sensitivity with increasing amount of train- ing data 2.12 Pairwise dependencies in human acceptor splice site .1 Length distributions in Human chromosome 22.2 Approximation of length distributions by geometric distributions.3 Example of a geometric-tail distribution .4 Approximation by geometric-tail distributions .9 Alternative implementation of geometric-tail distributions .6 Generalization capacity of geometric-tail distributions .7 Geometric-tail distribution gadget for large values of f.8 Step-function approximation of length distribution.9 Gadget generating non-geometric length distribution in HMM .10 Family of distributions generated by the gadget from Figure 3.11 Gadget with geometric length distribution replaces gadget from Figure 3.12 3-periodic Markov chains used for modeling exons .13 Alternative model of intron .14 Example of boxed HMM. gà và kg kg va 3.15 Intron lengths of fruit fy.1 The most probable path is different than the most probable annotation .2 HMM A: An HMM with the multiple path problem .3 HMM B: Simplified model of HMMA .4 Comparison of different decoding methods .5 NP hardness of the most probable labeling—gadget for vertexv .6 Example of the construction of Lyngso and Pedersen (2002) .7 Illustration of the BEST-LAYER-COLORING problem .8 Overview of NP-completeness proof of BEST-LAYER-COLORING .9 Part of SAT(c, y) component corresponding to one variable.10 Example of assembly of SAT components .11 Overview of ENCODE and EQ. c c c Q Q Q r ng Q2 2 TT va 4.12 One section of component MULT(#):a —2 @(#) .14 One section of component SQUARE(z):1—— K(n)—b(z).15 Encoding formulas and assignments for HAIAI solvingSAT.16 HAIM solving SẤT”. gà gà kg kg va 4.17 HMM with critical edges.18 An HMM violating critical edge condition .19 Usefulness of silent states.20 Simplified model of ESTScan .21 Simple model of exon/intron structure 2.22 TMHMM: prediction of topology of transmembrane proteins .23 HMM requiring generalized EVA algorithm.24 An HMM with unknown decoding algorithm.
List of Tables 1.1 Standard genetic code. wc gà va 15 1.2 Correlation of 3-mer composition of sequence elements in gene finding .3 Classification of objects in union of predicted and correct objects.1 Position weight matrix for donor site .2 Finding optimal solution with CPLEX (running time).3 Characteristics of data sets used for testing of signal models .4 Specificity at various sensitivity levels and reliability score of donor site models 54 2.5 Structures inferred for structured HƠI models.6 Specifcity and reliability seore of acceptor site models.7 Performance of signal models in gene finding.1 Overview of methods for modeling length distributions .2 Performance of non-geometric length distributions on gene finding in human 94 3.