Sequence kernels for predicting protein essentiality

ABSTRACT

The problem of identifying the minimal gene set required to sustain life is of crucial importance in understanding cellular mechanisms and designing therapeutic drugs. This work describes several kernel-based solutions for predicting essential genes that outperform existing models while using less training data. Our first solution is based on a semi-manually designed kernel derived from the Pfam database, which includes several Pfam domains. We then present novel and general domain-based sequence kernels that capture sequence similarity with respect to several domains made of large sets of protein sequences. We show how to deal with the large size of the problem -- several thousands of domains with individual domains sometimes containing thousands of sequences -- by representing and efficiently computing these kernels using automata. We report results of extensive experiments demonstrating that they compare favorably with the Pfam kernel in predicting protein essentiality, while requiring no manual tuning.

REFERENCES

• 1: Allauzen, C., & Mohri, M. (2007). OpenKernel library. http://www.openkernel.org.
• 2: Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., & Mohri, M. (2007). OpenFst: a general and efficient weighted finite-state transducer library. CIAA 2007 (pp. 11--23). Springer. http://www.openfst.org.
• 3: Ben-Hur, A., & Brutlag, D. L. (2003). Remote homology detection: a motif based approach. ISMB (Supplement of Bioinformatics) (pp. 26--33).
• 4: Asa Ben-Hur , William Stafford Noble, Kernel methods for predicting protein--protein interactions, Bioinformatics, v.21 n.1, p.38-46, January 2005 [doi>10.1093/bioinformatics/bti1016]
• 5: Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 6: Yu Chen , Dong Xu, Understanding protein dispensability through machine-learning analysis of high-throughput data, Bioinformatics, v.21 n.5, p.575-581, March 2005 [doi>10.1093/bioinformatics/bti058]
• 7: Collins, M., & Duffy, N. (2001). Convolution kernels for natural language. NIPS 2001 (pp. 625--632).
• 8: Corinna Cortes , Patrick Haffner , Mehryar Mohri, Rational Kernels: Theory and Algorithms, The Journal of Machine Learning Research, 5, p.1035-1062, 12/1/2004
• 9: Corinna Cortes , Mehryar Mohri, Moment Kernels for Regular Distributions, Machine Learning, v.60 n.1-3, p.117-134, September 2005 [doi>10.1007/s10994-005-0919-8]
• 10: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 11: Eskin, E., & Snir, S. (2005). The Homology Kernel: A Biologically Motivated Sequence Embedding into Euclidean Space. CIBCB (pp. 179--186).
• 12: Gustafson, A., Snitkin, E., Parker, S., DeLisi, C., & Kasif, S. (2006). Towards the identification of essential genes using targeted genome sequencing and comparative analysis. BMC:Genomics, 7, 265.
• 13: Haussler, D. (1999). Convolution Kernels on Discrete Structures (Technical Report UCSC-CRL-99-10). University of California at Santa Cruz.
• 14: Lanckriet, G., Deng, M., Cristianini, N., Jordan, M., & Noble, W. (2004). Kernel-based data fusion and its application to protein function prediction in yeast. Pacific Symposium on Biocomputing (pp. 300--311).
• 15: Christina Leslie , Rui Kuang, Fast String Kernels using Inexact Matching for Protein Sequences, The Journal of Machine Learning Research, 5, p.1435-1455, 12/1/2004
• 16: Huma Lodhi , Craig Saunders , John Shawe-Taylor , Nello Cristianini , Chris Watkins, Text classification using string kernels, The Journal of Machine Learning Research, 2, p.419-444, 3/1/2002 [doi>10.1162/153244302760200687]
• 17: Platt, J. (2000). Probabilities for support vector machines. In Advances in large margin classifiers. Cambridge, MA: MIT Press.
• 18: Arto Salomaa , M. Soittola, Automata: Theoretic Aspects of Formal Power Series, Springer-Verlag New York, Inc., Secaucus, NJ, 1978
• 19: Sonnhammer, E., Eddy, S., & Durbin, R. (1997). Pfam: A comprehensive database of protein domain families based on seed alignments. Proteins: Structure, Function and Genetics, 28, 405--420.
• 20: Zien, A., Rätsch, G., Mika, S., Schölkopf, B., Lengauer, T., & Müüller, K.-R. (2000). Engineering Support Vector Machine Kernels That Recognize Translation Initiation Sites. Bioinformatics, 16, 799--807.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory