Maximum entropy modeling of short sequence motifs with applications to RNA splicing signals

ABSTRACT

We propose a framework for modeling sequence motifs based on the Maximum Entropy principle (MEP).We recommend approximating short sequence motif distributions with the Maximum Entropy Distribution (MED) consistent with low-order marginal constraints estimated from available data, which may include dependencies between non-adjacent as well as adjacent positions.Finally, we suggest mechanistically-motivated ways of comparing models.

REFERENCES

• 1: M. Arita, K. Tsuda, and K. Asai. Modeling splicing sites with pairwise correlations. Bioinformatics, 18(2):S27--S34, 2002.
• 2: K. H. B. Lam. A general role for splicing enhancers in exon definition. RNA, 10:1233--41, 2002.
• 3: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 4: D. Brown. A Note on Approximations to Discrete Probability Distributions. Information and Control, 2:386--392, 1959.
• 5: E. Buehler and L. Ungar. Maximum Entropy Methods for Biological Sequence Modeling. Workshop on Data Mining in Bioinformatics, BIOKDD, 2001.
• 6: M. Bulyk, P. Johnson, and G. Church. Nucleotides of transcription factor binding sites exert interdependent effects on the binding affinities of transcription factors. Nucleic Acids Res, 30(5):1255--61, 2002.
• 7: C. Burge. Chapter 8. Modeling dependencies in pre-mRNA splicing signals. S.L. Salzberg, D.B. Searls, S. Kasif (Eds.), Computational Methods in Molecular Biology, Elsevier Science, pages 129--164, 1998.
• 8: C. Burge and S. Karlin. Prediction of complete gene structures in human genomic DNA. J. Mol. Biol., 268:78--94, 1997.
• 9: C. Burge, T. Tuschl, and P. Sharp. Chapter 20. Splicing of Precursors to mRNAs by the Spliceosomes. R. Gesteland and T. Cech and J. Atkins (Eds.), The Nature of Modern RNA Suggests a Prebiotic RNA, Cold Spring Harbor Laboratory Press, Cold Spring Harbor, New York, pages 525--560, 1999.
• 10: D. Cai, A. Delcher, B. Kao, and S. Kasif. Modeling splice sites with Bayes Networks . Bioinformatics, 16(2):152--158, 2000.
• 11: H. Du and M. Rosbash. The U1 snRNP protein U1C recognizes the 5' splice site in the absence of base pairing. Nature, 419(6902):86--90, 2002.
• 12: R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998.
• 13: W. Fairbrother and L. Chasin. Human Genomic Sequences that Inhibit Splicing. Molecular and Cellular Biology, 20(18):6816--6825, 2000.
• 14: W. Fairbrother, R. Yeh, P. Sharp, and C. Burge. Predictive identification of exonic splicing enhancers in human genes. Science, 297(5583):1007--13, 2002.
• 15: C. Ireland and S. Kullback. Contingency tables with given marginals. Biometrika, 55(1):179--188, 1968.
• 16: E. Jaynes. Information theory and statistical mechanics I. Physics Review, 106:620--630, 1957.
• 17: Anders Krogh, Two Methods for Improving Performance of a HMM and their Application for Gene Finding, Proceedings of the 5th International Conference on Intelligent Systems for Molecular Biology, p.179-186, June 21-26, 1997
• 18: A. Krogh, M. Brown, I. Mian, K. Sjolander, and D. Haussler. Hidden Markov models in computational biology. Applications to protein modeling. Journal of Molecular Biology, 235(5):1501--31, 1994.
• 19: A. Krogh and G. Mitchison. Maximum Entropy Weighting of Aligned Sequences of Proteins or DNA. In Proc. Third Int. Conf. Intelligent Systems for Molecular Biology, Eds. C. Rawlings et al. AAAI Press, pages 215--221, 1995.
• 20: 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
• 21: P. Lewis. Approximating Probability Distributions to Reduce Storage Requirements. Information and Control, 2:214--225, 1959.
• 22: E. Miriami, J. Sperling, and R. Sperling. Heat shock affects 5' splice site selection, cleavage and ligation of CAD pre-mRNA in hamster cells, but not its packaging in InRNP particles. Nucleic Acids Research, 22:3084--3091, 1994.
• 23: A. Newman. The role of U5 snRNP in pre-mRNA splicing. EMBO, 16(19):5797--800, 1997.
• 24: M. Pertea, X. Lin, and S. Salzberg. GeneSplicer: a new computational method for splice site prediction. Nucleic Acids Research, 29(5):1185--1190, 2001.
• 25: M. Shapiro and P. Senapathy. RNA splice junctions of different classes of eukaryotes: sequence statistics and functional implicatinos in gene expression. Nucleic Acids Research, 15(17):7155--7174, 1987.
• 26: J. Shore and R. Johnson. Axiomatic Derivation of the Principle of Maximum Entropy and the Principle of Minimum Cross-Entropy . IEEE Transactions on Information Theory, 26(1):26--37, 1980.
• 27: J. Swets. Measuring the accuracy of diagnostic systems. Science, 240(4857):1285--1293, 1988.
• 28: T. Thanaraj. Positional characterisation of false positives from computational prediction of human splice sites. Nucleic Acids Research, 28(3):744--754, 2000.
• 29: L. Varani, M. Hasegawa, M. Spillantini, M. Smith, J. Murrell, B. Ghetti, A. Klug, M. Goedert, and G. Varani. Structure of tau exon 10 splicing regulatory element RNA and destabilization by mutations of frontotemporal dementia and parkinsonism linked to chromosome 17. Proc Natl Acad Sci USA, 96(14):8229--34, 1999.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Stochastic processes

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Markov models, maximal dependence decomposition, maximum entropy, molecular sequence analysis, non-neighboring dependencies, regulatory elements, splice sites