Frequent-subsequence-based prediction of outer membrane proteins

ABSTRACT

A number of medically important disease-causing bacteria (collectively called Gram-negative bacteria) are noted for the extra "outer" membrane that surrounds their cell. Proteins resident in this membrane (outer membrane proteins, or OMPs) are of primary research interest for antibiotic and vaccine drug design as they are on the surface of the bacteria and so are the most accessible targets to develop new drugs against. With the development of genome sequencing technology and bioinformatics, biologists can now deduce all the proteins that are likely produced in a given bacteria and have attempted to classify where proteins are located in a bacterial cell. However such protein localization programs are currently least accurate when predicting OMPs, and so there is a current need for the development of a better OMP classifier. Data mining research suggests that the use of frequent patterns has good performance in aiding the development of accurate and efficient classification algorithms. In this paper, we present two methods to identify OMPs based on frequent subsequences and test them on all Gram-negative bacterial proteins whose localizations have been determined by biological experiments. One classifier follows an association rule approach, while the other is based on support vector machines (SVMs). We compare the proposed methods with the state-of-the-art methods in the biological domain. The results demonstrate that our methods are better both in terms of accurately identifying OMPs and providing biological insights that increase our understanding of the structures and functions of these important proteins.

REFERENCES

• 1: Ali K., Manganaris S. and Srikant R., Partial classification using association rules, KDD'97, p. 115--118, 1997.
• 2: Boeckmann B., Bairoch A., Apweiler R., Blatter M.-C., Estreicher A., Gasteiger E., Martin M. J., Michoud K., O'Donovan C., Phan I., Pilbout S., Schneider M. The SWISS-PROT protein knowledgebase and its supplement TrEMBL in 2003, Nucleic Acids Res. 31:365--370, 2003.
• 3: Mukund Deshpande , George Karypis, Evaluation of Techniques for Classifying Biological Sequences, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.417-431, May 06-08, 2002
• 4: Diederichs K., Freigang J., Umhau S., Zeth K. and Breed J., Prediction by a neural network of outer membrane β-strand topology, Protein Science, 7, p. 2413--2420, 1998.
• 5: Eisenhaber F. and Bork P., Wanted: subcellular localization of proteins based on sequences, Trends in Cell Biology, 8, p. 169--170, 1998.
• 6: Hua S. and Sun Z., Support vector machine approach for protein subcellular localization prediction, Bioinformatics, 17(8), p. 721--728, 2001.
• 7: Lucas Chi Kwong Hui, Color Set Size Problem with Application to String Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.230-243, April 29-May 01, 1992
• 8: Jacoboni I., Martelli P., Fariselli P., De Pinto V. and Casadio R., Prediction of the transmembrane regions of β-barrel membrane proteins with a neural network-based predictor, Protein Science, 10, p. 779--787, 2001.
• 9: Joachims T., Learning to Classify Text Using Support Vector Machines. Dissertation, Kluwer, 2002. software downloadable at http://svmlight.joachims.org/
• 10: G. M. Landau , U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, v.10 n.2, p.157-169, June 1989 [doi>10.1016/0196-6774(89)90010-2]
• 11: Neal Lesh , Mohammed J. Zaki , Mitsunori Ogihara, Mining features for sequence classification, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.342-346, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312275]
• 12: Leslie C., Eskin E. and Noble W., The spectrum kernel: A string kernel for SVM protein classification, Proceedings of the Pacific Symposium on Biocomputing, p. 564--575, 2002.
• 13: Liu B., Hsu W. and Ma Y., Integrating classification and association rule mining, KDD'98, New York, NY, 1998.
• 14: Martelli P., Fariselli P., Krogh A. and Casadio R., A sequence-profile-based HMM for predicting and discrimating β barrel membrane proteins, Bioinformatics, 18(1) 2002, S46-S53, 2002.
• 15: Nakashima H. and Nishikawa K., Discrimination of intracellular and extracellular proteins using amino acid composition and residue-pair frequencies, Journal of Molecular Biology, 238, p. 54--61, 1994.
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: Reinhardt A. and Hubbard T., Using neural networks for prediction of the subcellular location of proteins, Nucleic Acids Research, 26(9), p. 2230--2236, 1998.
• 18: Rulequest Research, Information on See5/C5.0, at <u>http://www.rulequest.com/see5-info.html</u>
• 19: Schirmer T. and Cowan S., Prediction of membrane-spanning β-strands and its application to maltoporin, Protein Science, 2, p. 1361--1363, 1993.
• 20: Schulz G., β-barrel membrane proteins, Curr. Opin. Struct. Biology, 10, p. 443--447, 2000.
• 21: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 22: Vert J.-P., Support vector machine prediction of signal peptide cleavage site using a new class of kernels for strings, Proceedings of the Pacific Symposium on Biocomputing, p. 649--660, 2002.
• 23: Jason Tsong-Li Wang , Gung-Wei Chirn , Thomas G. Marr , Bruce Shapiro , Dennis Shasha , Kaizhong Zhang, Combinatorial pattern discovery for scientific data: some preliminary results, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.115-125, May 24-27, 1994, Minneapolis, Minnesota, United States
• 24: Ke Wang , Senqiang Zhou , Yu He, Growing decision trees on support-less association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.265-269, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347147]
• 25: Wimley W., Toward genomic identification of β-barrel membrane proteins: Composition and architecture of known structures, Protein Science, 11, p. 301--312, 2002.
• 26: Ming-Hsuan Yang , Dan Roth , Narendra Ahuja, A Tale of Two Classifiers: SNoW vs. SVM in Visual Recognition, Proceedings of the 7th European Conference on Computer Vision-Part IV, p.685-699, May 28-31, 2002
• 27: Yuan Z., Prediction of protein subcellular locations using Markov chain models, FEBS Lett., 451, p. 23--26, 1999.
• 28: Zhai Y. and Saier M., The β-barrel finder (BBF) program, allowing identification of outer membrane β-barrel proteins encoded within prokaryotic genomes, Protein Science, 11, p. 2196--2207, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
association rule, classification, outer membrane protein, subcellular localization, support vector machine