Evidence Combination in Hidden Markov Models for Gene Prediction by Bronislava Brejová 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, Canada, 2005 © Bronislava Brejové 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-14466-1 Our file Notre référence ISBN: 0-494-14466-1 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.
ii Abstract This thesis introduces new techniques for finding genes in genomic sequences. Genes are regions of a genome encoding proteins of an organism. Identification of genes in a genome is an important step in the annotation process after a new genome is sequenced. The prediction accuracy of gene finding can be greatly improved by using experimental evidence.
This evidence includes homologies between the genome and databases of known proteins, or evolutionary conservation of genomic sequence in different species. We propose a flexible framework to incorporate several different sources of such evidence into a gene finder based on a hidden Markov model. Various sources of evidence are expressed as partial probabilistic statements about the annotation of positions in the sequence, and these are combined with the hidden Markov model to obtain the final gene prediction. The opportunity to use partial statements allows us to handle missing information transparently and to cope with the heterogeneous character of individual sources of evidence.
On the other hand, this feature makes the combination step more difficult. We present a new method for combining partial probabilistic statements and prove that it is an extension of existing methods for combining complete probability statements. We evaluate the performance of our system and its individual components on data from the human and fruit fly genomes. The use of sequence evolutionary conservation as a source of evidence in gene finding requires efficient and sensitive tools for finding similar regions in very long sequences.
We present a method for improving the sensitivity of existing tools for this task by careful modeling of sequence properties. In particular, we build a hidden Markov model representing a typical homology between two protein coding regions and then use this model to optimize a component of a heuristic algorithm called a spaced seed. The seeds that we discover significantly improve the accuracy and running time of similarity search in protein coding regions, and are directly applicable to our gene finder. ill Acknowledgements I would like to thank my supervisors Ming Li and Dan Brown for their support, encouragement, and guidance.
Dan Brown carefully read many drafts of this thesis and his comments have greatly improved the presentation. Thanks to my spouse Tomds Vinai for collaborating with me on this research project and for his love, care, and support. I would also like to thank members of my committee Ian Munro, Dale Schuurmans, Mary Thompson, and Franco Preparata for their time. Special thanks to Dale Schuurmans for asking difficult questions and for many helpful discussions about machine learning.
Therese Biedl also read the thesis and provided useful comments. Thanks to many people at the University of Waterloo for inspiration, advice, encouragement and a great open atmosphere. Therese Biedl was a coauthor of my first research paper and taught me a lot in the process. Together with Erik Demaine they organized problem solving sessions that spread contagious enthusiasm for research.
Jonathan Buss and Paul Kearney have provided support during the absence of my supervisor. Also thanks to Jianwei Niu, Mike Hu, Alex Hudek, and Mirela Andronescu for being great office mates. Finally, I would like to thank my parents for their love and for encouraging my interest in science and mathematics. iv Contents 1 Introduction 1 1.1 The problem of eukaryotic gene finding.1 Properties of protein coding genes that aid gene prediction .2 Hidden Markov models and their algorithms.21 Hidden Markov models for sequence annotation.22 The Viterbi algorithm for HMM decoding.23 Generalized hidden Markov models.3 Ab imilio gene ñnding .v kg vi k k va 9 18.1 Dynamic programming algorithms .2 The use of hidden Markov models for gene finding .4 Sources of additional evidence in gene finding.
LH ng ng.4 Genome comparÌi§OnS. kg va lỗ 1.5 Other sources of information .5 Methods for combining evidence in gene finding.1 Hidden Markov models with multiple outputs.2 Positional score modification ©.3 Pair hidden Markov models .4 Rule-based systems.c c Q cu ng nà La ngà và kia 21 1.6 Evaluation of gene finding accuracy.aa la IMHaa 23 2 Evidence Combination in Gene Finding 25 2.1 Overview of advisor architecture 2. ee ee ee 25 2.1 The base hidden Markov model for gene finding.2 Advisors and the super-advisor .2 Combination of hidden Markov model and super-advisor.1 Linear and logarithmic opinion pool .2 Algorithm to incorporate super-advisor into HMM .3 Expressing evidence as advisors. uc Q H n nu ng gu ng kg va j1 2.
Combination of advisors into super-adViSOT .1 Combining advisors to minimize distance to the super-advisor.1 Quadratic programming in advisor combination .2 Properties of advisor combination .0 eee eee ee 2.1 Linear combination as a special case of advisor combination 2.2 Advisors with binary partitions and the influence of priors .3 Under-constrained advisor combination .5 Variants of advisor combination.1 Distance measured by Li and Log 2.2 Distance measured by relative entropy. HQ vn va 2.3 Naive advisor combinatiOn.4 Experimental comparison of advisor combination methods.6 Training ofadvisor welghiSs. cv kg v V T ky 2.1 Weights for linear combination .2 Weights for linear combination including some vacuous advice.8 Experiments ng THHAda.7 Addressing the independence assumption. eee ee es 2.1 Selection of super-advisor positions.2 Choice of exponent @ ©.
ch gà g va 2.4 Relaxing the position independence assumption.8 Other approaches to incomplete information.1 Dempster-Shafer theory of evidence .2 Maximum entropy principle. L c cu ng ng Q ấy và ki kg kia P' 1 n - -dd<ä đa Spaced Seeds for Protein Coding Regions 3.1 Introduction to spaced seeds. Q Q Q Q Q gu ung g v v vi A kia SP.1 Expressiveness OÍ vectOr seed§s. c c Q ch Q Q n kg g và ki v va 3.2 Identifying hits in a sequence database.3 Predicted performance of vector seeds .3 Probabilistic models of conserved coding regions .2 Dependencies within codon.
c Q rà gà Q cv v v va 3. cu kg kia 3. c Q Q Q ng vn ng và và xi nt 3.4 Algorithm for computing sensitivity of vector seeds underanHMM. cu cv cv ng 2 kg gà gi k ki v v va 3.1 Datasets and models .2 Our models as predictors of seed performance.3 Optimal spaced seeds for homologous coding regions .4 Vector seeds for homologous coding regions .1 Theoretical properties of seeds 2.
Q Q Q LH ng ng gà và va vì 3.2 Generalized spaced seeds. LG LH nu vn gà và và 96 3.3 Probabilistic models of alignments. ad đá 99 4 ExonHunter: a Comprehensive Eukaryotic Gene Finder 101 4.1 Extended HMM for gene finding. Q Q Q Q Q b Q vn ng gi v kg v vi v v.
c Q L v vn nu ngà g g g v v k va va 104 4.3 Signal and content models.4 Dependence on GC content. eee eee Woe 107 4.2 Training and testing datasets.1 Interval representation of alignment-based advisors.2 Advisors based on protein alignments .3 Advisors based on EST alignments .4 Advisors based on genome alignments .5 Advisors based on sequence repeats .1 Performance on short single-gene human sequences.2 Performance on longer human genomic sequences.3 Contribution of individual advisors.4 Performance on the fruit fly genome .aaaAŨ 129 5 Conclusion 131 vii List of Figures 1.1 Translation of a gene toa protein.2 Standard genetiC cOde. Q Q Q Q Q c LH ng ng g v v AT v và va 1.3 Example of a labeling representing gene structUT®.4 Typical signals in a multi-exon gene 2.5 A toy hidden Markov model for gene fñnding.6 Example of the topology of an HMM for gene ñnding.7 Example of a local alignment of two sequences.8 A hidden Markov model represented as a Bayesian network .9 Probabilistic model of TwinScan gene finder as a Bayesian network .10 Phylogenetic hidden Markov model.1 Overview of model architecture.2 Experimental comparison of advisor combination methods .3 Bayesian network for training weights of the naive combination method .4 Bayesian network for training weights of the improved naive combination method .1 Example of hits of a spaced seed in an alignment.2 Computation of probability of two consecutive hits of aspaced seed .3 Performance of vector seeds under the simple Bernoulli model.4 A hidden Markov model representing model ).9 A simple hidden Markov model representing the model M® ,.6 A small hidden Markov model representing the model M® .7 A hidden Markov model representing the model M¢*8) ,,.8 Graphical overview of the algorithm for computing vector seed sensitivity .9 Example of execution of the algorithm for computing vector seed sensitivity .10 Example of a trie representing sequences needed to compute the sensitivity of a L2) 0 ee 3.11 A hidden Markov model equivalent toa Markov chan .12 Several alignments of coding regions corresponding to one protein alignment.13 Comparison of real and predicted sensitivity of spaced seeds.1 Overall scheme of the HMM used in ExonHunter.2 Transitions between exon and intron statesinthe HMM .3 Topology of intron submodel .4 Geometric length distribution of human exons and introns .5 Geometric length distribution of human intergenic regions .6 Transitions between the final exon and the stop codon signalinthe HMM .7 Comparison of GC content in coding and non-coding regions .8 Interval score buckets minimizing weighted entropy .9 True positive rate of protein advisors as a function of distance from alignment boundary 113 4.10 Comparison of total alignment score and score per position in protein alignments .11 Intervals produced from alignments with one protein .12 True positive rates of exon protein advisors .13 True positive rates of intron protein advisors.14 True positive rates of EST intron advisors for different label set partitions .15 True positive rates of genome alignment advisors .0 00 ee Na 122 ix List of Tables 1.