Bioinformatics 20(10) © Oxford University Press 2004; all rights reserved.
GCB Conference Paper |
Using convex hulls to extract interaction interfaces from known structures
1 Department of Computing, City University, London, EC1V 0HB, UK, 2 Medical Research Council, Dunn Human Nutrition Unit, Cambridge, CB2 2QH, UK, 3 Biomatics Lab, BioSystems Department, DaeJeon, KAIST, Korea and 4 Biotec and Department of Computing, TU Dresden, 108 01307 Dresden, Germany
Received on October 12, 2003; accepted on February 3, 2004
Motivation: Protein interactions provide an important context for the understanding of function. Experimental approaches have been complemented with computational ones, such as PSIMAP, which computes domain–domain interactions for all multi-domain and multi-chain proteins in the Protein Data Bank (PDB). PSIMAP has been used to determine that superfamilies occurring in many species have many interaction partners, to show examples of convergent evolution through shared interaction partners and to uncover complexes in the interaction map.
To determine an interaction, the original PSIMAP algorithm checks all residue pairs of any domain pair defined by classification systems such as SCOP. The computation takes several days for the PDB. The computation of PSIMAP has two shortcomings: first, the original PSIMAP algorithm considers only interactions of residue pairs rather than atom pairs losing information for detailed analysis of contact patterns. At the atomic level the original algorithm would take months. Second, with the superlinear growth of PDB, PSIMAP is not sustainable.
Results: We address these two shortcomings by developing a family of new algorithms for the computation of domain–domain interactions based on the idea of bounding shapes, which are used to prune the search space. The best of the algorithms improves on the old PSIMAP algorithm by a factor of 60 on the PDB. Additionally, the algorithms allow a distributed computation, which we carry out on a farm of 80 Linux PCs. Overall, the new algorithms reduce the computation at atomic level from months to 20 min. The combination of pruning and distribution makes the new algorithm scalable and sustainable even with the superlinear growth in PDB.
Contact: panos{at}alumni.doc.ic.ac.uk
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  E. R. Jefferson, T. P. Walsh, T. J. Roberts, and G. J. Barton SNAPPI-DB: a database and API of Structures, iNterfaces and Alignments for Protein-Protein Interactions Nucleic Acids Res., January 12, 2007; 35(suppl_1): D580 - D589. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Henschel, W. K. Kim, and M. Schroeder Equivalent binding sites reveal convergently evolved interaction motifs Bioinformatics, March 1, 2006; 22(5): 550 - 555. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Winter, A. Henschel, W. K. Kim, and M. Schroeder SCOPPI: a structural classification of protein-protein interfaces Nucleic Acids Res., January 1, 2006; 34(suppl_1): D310 - D314. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. S. Moon, J. Bhak, K. H. Lee, and D. Lee Architecture of basic building blocks in protein and domain structural interaction networks Bioinformatics, April 15, 2005; 21(8): 1479 - 1486. [Abstract] [Full Text] [PDF]
|
|