Bioinformatics Vol. 19 no. 2 2003
Pages 219-227
© 2003 Oxford University Press
Gene finding with a hidden Markov model of genome structure and evolution
1 Bioinformatics Research Center, Department of Genetics and Ecology,
The Institute of Biological Sciences, University of Aarhus,
Building 550, Ny Munkegade, 8000 Aarhus C, Denmark
2 Department of Statistics,
Oxford University, The Peter Medawar Building for Pathogen Research,
South Parks Road, Oxford OX1 3SY, UK
Received on March 28, 2002
; revised on June 3, 2002
; accepted on July 17, 2002
Motivation: A growing number of genomes are sequenced. The differences in evolutionary pattern between functional regions can thus be observed genome-wide in a whole set of organisms. The diverse evolutionary pattern of different functional regions can be exploited in the process of genomic annotation. The modelling of evolution by the existing comparative gene finders leaves room for improvement.
Results: A probabilistic model of both genome structure and evolution is designed. This type of model is called an Evolutionary Hidden Markov Model (EHMM), being composed of an HMM and a set of region-specific evolutionary models based on a phylogenetic tree. All parameters can be estimated by maximum likelihood, including the phylogenetic tree. It can handle any number of aligned genomes, using their phylogenetic tree to model the evolutionary correlations. The time complexity of all algorithms used for handling the model are linear in alignment length and genome number. The model is applied to the problem of gene finding. The benefit of modelling sequence evolution is demonstrated both in a range of simulations and on a set of orthologous human/mouse gene pairs.
Availability: Free availability over the Internet on www server: http://www.birc.dk/Software/evogene.
Contact: jsp{at}daimi.au.dk
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  W. H. Majoros and U. Ohler Complexity reduction in context-dependent DNA substitution models Bioinformatics, January 15, 2009; 25(2): 175 - 182. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. Barquist and I. Holmes xREI: a phylo-grammar visualization webserver Nucleic Acids Res., July 1, 2008; 36(suppl_2): W65 - W69. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. McCauley, S. de Groot, T. Mailund, and J. Hein Annotation of selection strengths in viral genomes Bioinformatics, November 15, 2007; 23(22): 2978 - 2986. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. DeCaprio, J. P. Vinson, M. D. Pearson, P. Montgomery, M. Doherty, and J. E. Galagan Conrad: Gene prediction using conditional random fields Genome Res., September 1, 2007; 17(9): 1389 - 1398. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. de Groot, T. Mailund, and J. Hein Comparative annotation of viral genomes with non-conserved gene structure Bioinformatics, May 1, 2007; 23(9): 1080 - 1089. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
O. Mirabeau, E. Perlas, C. Severini, E. Audero, O. Gascuel, R. Possenti, E. Birney, N. Rosenthal, and C. Gross Identification of novel peptide hormones in the human proteome by hidden Markov model screening Genome Res., March 1, 2007; 17(3): 320 - 327. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. C. King, J. Taylor, L. Elnitski, F. Chiaromonte, W. Miller, and R. C. Hardison Evaluation of regulatory potential and conservation scores for detecting cis-regulatory modules in aligned mammalian genome sequences Genome Res., August 1, 2005; 15(8): 1051 - 1060. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. D'Avenio, M. Grigioni, G. Orefici, and R. Creti SWIFT (sequence-wide investigation with Fourier transform): a software tool for identifying proteins of a given class from the unannotated genome sequence Bioinformatics, July 1, 2005; 21(13): 2943 - 2949. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. H. Majoros, M. Pertea, and S. L. Salzberg Efficient implementation of a generalized pair hidden Markov model for comparative gene finding Bioinformatics, May 1, 2005; 21(9): 1782 - 1788. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. S. Pedersen, I. M. Meyer, R. Forsberg, P. Simmonds, and J. Hein A comparative method for finding and folding RNA secondary structures within protein-coding regions Nucleic Acids Res., September 24, 2004; 32(16): 4925 - 4936. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Birney, M. Clamp, and R. Durbin GeneWise and Genomewise Genome Res., May 1, 2004; 14(5): 988 - 995. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Siepel and D. Haussler Phylogenetic Estimation of Context-Dependent Substitution Rates by Maximum Likelihood Mol. Biol. Evol., March 1, 2004; 21(3): 468 - 488. [Abstract] [Full Text] [PDF]
|
|