Multi-class protein fold recognition using large margin logic based divide and conquer learning

ABSTRACT

Inductive Logic Programming (ILP) systems have been successfully applied to solve complex biological problem by viewing them as binary classification tasks. It remains an open question how an accurate solution to a multi-class problem can be obtained by using a logic based learning method. In this paper we present a novel logic based approach to solve complex and challenging multi-class classification problems in bioinformatics by focusing on a particular task, namely protein fold recognition. Our technique is based on the use of large margin kernel-based methods in conjunction with first order rules induced by an ILP system. The proposed approach learns a multi-class classifier by using a divide and conquer reduction strategy that splits multi-classes into binary groups and solves each individual problem recursively hence generating an underlying decision list structure. The method is applied to assigning protein domains to folds. Experimental evaluation of the method demonstrates the efficacy of the proposed approach to solving complex multi-class classification problems in bioinformatics.

REFERENCES

• 1: Ke Chen , Lukasz Kurgan, PFRES, Bioinformatics, v.23 n.21, p.2843-2850, November 2007 [doi>10.1093/bioinformatics/btm475]
• 2: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 3: C. H. Ding and I. Dubchak. Multi-class protein fold recognition using support vector machines and neural networks. Bioinformatics, 17:349--358, 2001.
• 4: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 5: Wim Van Laer , Luc De Raedt , Saso Dzeroski, On Multi-class Problems and Discretization in Inductive Logic Programming, Proceedings of the 10th International Symposium on Foundations of Intelligent Systems, p.277-286, October 15-18, 1997
• 6: Niels Landwehr , Andrea Passerini , Luc De Raedt , Paolo Frasconi, kFOIL: learning simple relational kernels, Proceedings of the 21st national conference on Artificial intelligence, p.389-394, July 16-20, 2006, Boston, Massachusetts
• 7: S. Muggleton, H. Lodhi, A. Amini, and M. J. E. Sternberg. Support Vector Inductive Logic Programming. In Proceedings of the Eighth International Conference on Discovery Science, volume 735 of LNAI, pages 163--175. Springer Verlag, 2005.
• 8: A. G. Murzin, S. E. Brenner, T. Hubbard, and C. Chothia. SCOP: a structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol., 247(536--540), 1995.
• 9: Ulrich Rückert , Stefan Kramer, Margin-based first-order rule learning, Machine Learning, v.70 n.2-3, p.189-206, March 2008 [doi>10.1007/s10994-007-5034-6]
• 10: Mohammad Tabrez Anwar Shamim , Mohammad Anwaruddin , H.A. Nagarajaram, Support Vector Machine-based classification of protein folds using the structural properties of amino acid residues and amino acid residue pairs, Bioinformatics, v.23 n.24, p.3320-3327, December 2007 [doi>10.1093/bioinformatics/btm527]
• 11: Hong-Bin Shen , Kuo-Chen Chou, Ensemble classifier for protein fold pattern recognition, Bioinformatics, v.22 n.14, p.1717-1722, July 2006 [doi>10.1093/bioinformatics/btl170]
• 12: M. Turcotte, S. Muggleton, and J. E. Sternberg. Automated discovery of structural signatures of protein fold and function. J. Mol. Biol., 306:591--605, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation

Keywords:
bioinformatics, evaluation, inductive logic programming, multi-class classification, protein fold recognition, support vector inductive logic programming, support vector machines