Abstract
Gene structure prediction is to predict the complete gene structure, especially the precise exon-intron structure of a gene in an eukaryotic genomic DNA sequence. There might be a fairly large number of human genes that remain to be identified. In response to this challenge, computational gene structure prediction approaches have proliferated. However, the performance is still far from satisfactory. Previous ab initio gene prediction approaches are investigated, and a biological process by which information from a gene is used in the synthesis of a functional gene product, called the gene expression, is reexamined. In this study, a stochastic content-free grammar (SCFG) is proposed to model the gene structure of genomic DNA sequences from the gene expression process, and is reduced to a weakly equivalent grammar associated with a hidden semi-Markov model (HSMM). To improve the submodels for the gene structure prediction approach, the signal sensors for donor sites and acceptor sites are developed by using a dependency graph model to fully capture the intrinsic cyclic inter-dependency between base positions in a splice site. To facilitate statistical inference, the dependency graph (which is usually a graph with cycles that make probabilistic reasoning very difficult, if not impossible) is expanded into a Bayesian network (which is a directed acyclic graph that facilitates statistical reasoning). In addition, first-order and second-order Markov chain models of amino acids are investigated to model the content sensors for exons, instead of the widely used 3-periodic fifth-order inhomogeneous Markov chain model of DNA nucleotides. Finally, a modified trellis-based parsing algorithm for stochastic context-free grammars with state-duration nonterminal symbols is introduced to predict gene structure.