An Expectation-Maximization Algorithm for Analysis of Evolution of Exon-Intron Structure of Eukaryotic Genes

  • Liran Carmel
  • Igor B. Rogozin
  • Yuri I. Wolf
  • Eugene V. Koonin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3678)


We propose a detailed model of evolution of exon-intron structure of eukaryotic genes that takes into account gene-specific intron gain and loss rates, branch-specific gain and loss coefficients, invariant sites incapable of intron gain, and rate variability of both gain and loss which is gamma-distributed across sites. We develop an expectation-maximization algorithm to estimate the parameters of this model, and study its performance using simulated data.


Terminal Node Eukaryotic Gene Intron Gain Spliceosomal Intron Adjacent Intron 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Nixon, J.E., Wang, A., Morrison, H.G., McArthur, A.G., Sogin, M.L., Loftus, B.J., Samuelson, J.: A Spliceosomal Intron in Giardia Lamblia. Proc. Natl. Acad. Sci. USA 99, 3701–3705 (2002)CrossRefGoogle Scholar
  2. 2.
    Gilbert, W.: The Exon Theory of Genes. Cold Spring Harb. Symp. Quant. Biol. 52, 901–905 (1987)Google Scholar
  3. 3.
    Cho, G., Doolittle, R.F.: Intron Distribution in Ancient Paralogs Supports Random Insertions and Not Random Loss. J. Mol. Evol. 44, 573–584 (1997)CrossRefGoogle Scholar
  4. 4.
    Lynch, M.: Intron Evolution as a Population-genetic Process. Proc. Natl. Acad. Sci. USA 99, 6118–6123 (2002)CrossRefGoogle Scholar
  5. 5.
    Rogozin, I.B., Wolf, Y.I., Sorokin, A.V., Mirkin, B.G., Koonin, E.V.: Remarkable Interkingdom Conservation of Intron Positions and Massive. Lineage-Specific Intron Loss and Gain in Eukaryotic Evolution. Curr. Biol. 13, 1512–1517 (2003)Google Scholar
  6. 6.
    Qui, W.-G., Schisler, N., Stoltzfus, A.: The Evolutionary Gain of Spliceosomal Introns: Sequence and Phase Preferences. Mol. Biol. Evol. 21, 1252–1263 (2004)CrossRefGoogle Scholar
  7. 7.
    Roy, S.W., Gilbert, W.: Complex Early Genes. Proc. Natl. Acad. Sci. USA 102, 1986–1991 (2005)CrossRefGoogle Scholar
  8. 8.
    Dibb, N.J.: Proto-Splice Site Model of Intron Origin. J. Theor. Biol. 151, 405–416 (1991)CrossRefGoogle Scholar
  9. 9.
    Friedman, N., Ninio, M., Pe’er, I., Pupko, T.: A Structural EM Algorithm for Phylogenetic Inference. J. Comput. Biol. 9, 331–353 (2002)CrossRefGoogle Scholar
  10. 10.
    Holmes, I.: Using Evolutionary Expectation Maximisation to Estimate Indel Rates. Bioinformatics 21, 2294–2300 (2005)CrossRefGoogle Scholar
  11. 11.
    Brooks, D.J., Fresco, J.R., Singh, M.: A Novel Method for Estimating Ancestral Amino Acid Composition and Its Application to Proteins of the Last Universal Ancestor. Bioinformatics 20, 2251–2257 (2004)CrossRefGoogle Scholar
  12. 12.
    Siepel, A., Haussler, D.: Phylogenetic Estimation of Context-Dependent Substitution Rates by Maximum Likelihood. Mol. Biol. Evol. 21, 468–488 (2004)CrossRefGoogle Scholar
  13. 13.
    Yang, Z.: Maximum Likelihood Phylogenetic Estimation from DNA Sequences with Variable Rates over Sites: Approximate Methods. J. Mol. Evol. 39, 306–314 (1994)CrossRefGoogle Scholar
  14. 14.
    Felsenstein, J.: Evolutionary Trees from DNA Sequences: A Maximum Likelihood Approach. J. Mol. Evol. 17, 368–376 (1981)CrossRefGoogle Scholar
  15. 15.
    Mourier, T., Jeffares, D.C.: Eukaryotic Intron Loss. Science 300, 1393 (2003)CrossRefGoogle Scholar
  16. 16.
    Sverdlov, A.V., Babenko, V.N., Rogozin, I.B., Koonin, E.V.: Preferential Loss and Gain of Introns in 3’ Portions of Genes Suggests a Reverse-Transcription Mechanism of Intron Insertion. Gene 338, 85–91 (2004)CrossRefGoogle Scholar
  17. 17.
    Roy, S.W., Gilbert, W.: The Pattern of Intron Loss. Proc. Natl. Acad. Sci. USA 102, 713–718 (2005)CrossRefGoogle Scholar
  18. 18.
    Cho, S., Jin, S.-W., Cohen, A., Ellis, R.E.: A Phylogeny of Caenorhabditis Reveals Frequent Loss of Introns During Nematode Evolution. Genome Res. 14, 1207–1220 (2004)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Liran Carmel
    • 1
  • Igor B. Rogozin
    • 1
  • Yuri I. Wolf
    • 1
  • Eugene V. Koonin
    • 1
  1. 1.National Center for Biotechnology Information, National Library of MedicineNational Institutes of HealthBethesdaUSA

Personalised recommendations