Multiple organism gene finding by collapsed gibbs sampling

ABSTRACT

The Gibbs sampling method has been widely used for sequence analysis after it was successfully applied to the problem of identifying regulatory motif sequences upstream of genes. Since then numerous variants of the original idea have emerged, however in all cases the application has been to finding short motifs in collections of short sequences (typically less than 100 nucleotides long). In this paper we introduce a Gibbs sampling approach for identifying genes in multiple large genomic sequences up to hundreds of kilobases long. This approach leverages the evolutionary relationships between the sequences to improve the gene predictions, without explicitly aligning the sequences. We have applied our method to the analysis of genomic sequence from 14 genomic regions, totaling roughly 1.8Mb of sequence in each organism. We show that our approach compares favorably with existing ab-initio approaches to gene finding, including pairwise comparison based gene prediction methods which make explicit use of alignments. Furthermore, excellent performance can be obtained with as little as 4 organisms, and the method overcomes a number of difficulties of previous comparison based gene finding approaches: it is robust with respect to genomic rearrangements, can work with draft sequence, and is fast (linear in the number and length of the sequences). It can also be seamlessly integrated with Gibbs sampling motif detection methods.

REFERENCES

• 1: Alexandersson, M., Cawley, S., Pachter, L. (2003). SLAM: Cross-species gene finding and alignment with a generalized pair hidden Markov model. Genome Research, 13, 496--502.
• 2: Boffelli, D., McAuliffe, J., Ovcharenko, D., Lewis, K. D., Ovcharenko, I., Pachter, L., Rubin, E.M. (2003). Phylogenetic shadowing of primate sequences to find functional regions of the human genome. Science, 299, 1391--4.
• 3: Burge, C., Karlin, S. (1997). Prediction of complete gene structures in human genomic DNA. Journal of Molecular Biology, 268,78--94.
• 4: Cawley, S., Pachter, L. (2003). HMM sampling and applications to gene finding and alternative splicing. Bioinformatics supplement for the European Conference on Computational Biology 2003, 36--41.
• 5: Kent W. J. (2002) BLAT-the BLAST-like alignment tool. Genome Research, 12, 656--64.
• 6: Durbin, R., Eddy, S., Krogh, A., Mitchison, G. (1998). Biological Sequence Analysis, Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
• 7: Göttgens, B., Barton, L. M., Chapman, M. A., Sinclair, A. M., Knudsen, B., Grafham, D., Gilbert, J. G. R, Rogers, J., Bentley, D. R., Green, R. (2002). Transcriptional Regulation of the Stem Cell Leukemia Gene (SCL) - Comparative Analysis of Five Vertebrate SCL Loci. Genome Research, 12, 749--759.
• 8: Korf, I., Flicek, P., Duan, D., Brent, M. R. (2001). Integrating genomic homology into gene structure prediction. Bioinformatics, 17, S140--8.
• 9: David Kulp , David Haussler , Martin G. Reese , Frank H. Eeckman, A Generalized Hidden Markov Model for the Recognition of Human Genes in DNA, Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology, p.134-142, June 12-15, 1996
• 10: Lawrence, C.E., Altschul, S. F., Boguski, M. S., Liu, J. S., Neuwald, A. F., Wootton, J. C. (1993). Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science, 262, 208--14.
• 11: Liu, J. S. (1994). The collapsed Gibbs sampler with applications to a gene regulation problem. Journal of the American Statistical Association, 89, 958--966.
• 12: Liu, J. S., Neuwald, A. F., Lawrence, C. E. (1995) Bayesian Models for Multiple Local Sequence Alignment and Gibbs Sampling Strategies. Journal of the American Statsitical Association, 90, 1156--1170.
• 13: Parra G., Agarawal, P., Abril J.F., Wiehe, T., Fickett, J.W., Guig'o, R. (2003) Comparative Gene Prediction in Human and Mouse Genome Research, 13, 108--117.
• 14: Rat Genome Sequencing Consortium (2004). Evolution of the Mammalian Genome: Sequence of the Genome of the Brown Norway Rat. Nature, submitted.
• 15: Tanner, M.A., Wong, W. H., (1987). The Calculation of Posterior Distributions by Data Augmentation. Journal of the American Statistical Association, 82, 528--550.
• 16: Thomas J.W. et al. (2003) Comparative analyses of multi-species sequences from targeted genomic regions. em Nature 424 788--793.
• 17: Waterston, R. H. et al. (2002). Initial sequencing and comparative analysis of the mouse genome. Nature, 420, 520--62.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design, Theory

Keywords:
gene finding, gibbs sampling, hidden markov model