BioSysBio:abstracts/2007/Alper Kucukural

• Add or delete the sections that you require.

Discrimination of Proteins Using Graph Theoretic Properties

Author(s): Alper Küçükural, Uğur Sezerman
Affiliations: Sabancı University
Contact:email: kucukural@su.sabanciuniv.edu
Keywords: 'Graph Theory' 'Bioinformatics' 'Delaunay Tesselation' 'Contact Maps'

Abstract

Graph theoretic properties of proteins can be used to perceive the differences between correctly folded proteins and well designed decoy sets. Graphs are used to representation of 3D protein structures. We used two different graph representations of protein structures which are Delaunay tessellations of proteins and contact map graphs. Graph theoretic properties for both graph types showed high classification accuracy to discrimination of proteins. Fisher, linear, quadratic, neural network and support vector classifiers were used to classification of the protein structures. The best classifier accuracy was about %97.5. The results showed that characteristic features of graph theoretic properties can be used many fields such as prediction of fold recognition, structure alignment and comparison, detection of similar domains, and definition of structural motifs in high accuracy.

Results

Results of the Delaunay Tessellated Graphs

---

Results of the Contact Maps

References

1. Taylor T., Vaisman I.I. (2006) Graph theoretic properties of networks formed by the Delaunay tessellation of protein structures. . Phys Rev E Stat Nonlin Soft Matter Phys.: 73: 041925.
2. Miyazawa, S. & Jernigan, R. L. (1996) J. Mol. Biol. 256, 623–644.
3. McConkey, B.J., Sobolev, V., and Eldman, M. 2003. Discrimination of native protein structures using atom–atom contact scoring. Proc. Natl. Acad. Sci. 100: 3215–3220.
4. Uğur Sezerman, Finding Common Domains of Proteins Using Parallelized Attributed Inexact Sub-graph Matching Algorithm, TAM 2006.
5. M. Vendruscolo et al., Phys. Rev. E 65, 061910 2002.
6. Watts, D. J. and Strogatz, S. H. (1998). Collective Dynamics of 'Small-World' Networks. Nature 393, 440--442.
7. Erdös, P. and A. Renyi, On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 1960. 5: p. 17-61.
8. Liang, J.and K.A. Dill, Are proteins Well-Packed? Biophys, J.,2001. 81:p. 751-766.
9. Soyer, A., J. Chomiller, J.-P. Mornon, R. Jullien, and J.-F. Sadoc, Voronoi Tesselation Reveals the Condensed Matter Character of Folded Proteins. Phys. Rev. Lett., 2000. 85:p.3532-3535.
10.Vendruscolo, M., E. Kussel, and E. Domany, Recovery of Protein Structure from Contact Maps. Structure Fold. Des., 1997. 2:p.295-306.
11.Fariselli, P. and R. Casadio, A Neural Network Based predictor of Residue Contacts in Proteins. Protein Eng., 1996. 9:p.941-948.
12.Bishop, C.M., Neural Networks in Pattern Recognition. 1996, New York:Oxford University Press.
13.Strogatz S.H.,Exploring Complex Networks, 2001.410:p.268-276.
14.Petersen, T.N., C. Lundegaard, M. Nielsen, H. Bohr, S. Brunak, G.P. Gippert, and O. Lund, Prediction of Protein Secondary Structure at 80% Accuracy. Proteins,2000.41:p.17-20.
15.Albert, R. and Barabasi, A.-L., Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 47–97 (2002).
16.A Measure of Betweenness Centrality Based on Random Walks, M. E. J. Newman, DOI: cond-mat/0309045, arXiv, 2003-09-01.
17.U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177, 2001.
18.Zhao, Y., Karypis, G.: Prediction of contact maps using support vector machines. In: Proceedings of the IEEE Symposium on BioInformatics and BioEngineering, IEEE Computer Society (2003).
19.Ferdi van der Heijden, Robert P.W. Duin, Dick de Ridder and David M.J. Tax, John Wiley & Sons, Classification, parameter estimation and state estimation - an engineering approach using Matlab, 424 pages, ISBN 0470090138, 2004.