Characterizing the Morphology of Protein Binding Patches with vorpatch and compatch

Characterizing the Morphology of Protein Binding Patches
with vorpatch and compatch

Content

This web site presents the keys features of the paper Characterizing the Morphology of Protein Binding Patches, see [MDBC11], and the accompanying software:

1. Shelling Protein Binding Patches Using vorpatch

1.1. Theory
1.2. Using vorpatch software

2. Comparing Protein Binding Patches Using Compatch

2.1. Theory
2.2. Using Compatch software

3. Bibliography
4. Downloading Executables

1. Shelling Protein Binding Patches Using vorpatch

1.1. Theory

Interface atoms and binding patches. Protein complexes underpin all biological functions. Given a binary complex involving a two partners, called the receptor and the ligand, a binding patch is the collection of atoms of a given partner which account for the interaction. The union of two such patches defines the interface of the complex. In practice, vorpatch uses the exact computation of interface atoms using the Voronoi interface model, see [CPBJ06], [BGNC09], [CL10].


Interface atoms of the complex 1acb, with partner A in blue and partner B in red.	2D illustration of the Voronoi interface model.

Shelling binding patches. The shelling process consist of describing the topology of a binding patch as an ordered rooted tree coding the relationship between the so-called shells. In 3D, the Solvent Accessible Surface (SAS) of a protein is composed of spherical polygons called faces. We define the shelling order (SO) of an interface face as its distance, in terms of faces, to non-interface faces. Since interface faces that are in direct contact with non-interface faces have a SO = 0, the SO is a non negative integer, typically in the range 1..10. A set of neighbor interface faces having same SO forms a shell. The neighborhood relationship between shells having consecutive shelling order is then encoded in the atom shelling tree.


Rotated view of 1acb partner B, non interface faces are in grey-blue, interface faces with SO=0 are in white, etc...	Corresponding atom shelling tree.

1.2. Using vorpatch

vorpatch is a (linux) command line tool that generates the two binding patches of a given protein complex. vorpatch requires the protein complex to be given in PDB format, and also requires the sets of chain IDs of the two partners.

The vorpatch flow.

As an example, assume that we wish to generate the binding patches of the complex 1q9q, whose partners are respectively described by the chains A and B on the one hand, and chain C on the other hand. If the input file is located in the directory say "./pdb", the following (minimal) command line generates the output in the "./output" directory:

vorpatch-64.exe -f ./pdb/1q9q.pdb -C AB -C C -D ./output/

The following six files are generated in "./output":

Two atom shelling trees: 1q9q_A.ast and 1q9q_B.ast
Two 2D illustrations of the shelling trees: 1q9q_A.eps and 1q9q_B.eps
Two 3D visualization files for VMD: 1q9q_A.vmd and 1q9q_B.vmd

The full set of options is available with the help option, that is running vorpatch-64.exe -h.

2. Comparing Protein Binding Patches Using Compatch

2.1. Theory

Tree-edit-distance. Encoding a binding patch as an ordered tree whose nodes contain shells paves the way to patch comparison using the so-called tree-edit-distance (TED) [B05]. The TED is based on three tree-edit-operations - namely node deletion, node insertion and node morphing - each associated to a cost. The TED computes a tree-edit-script, namely a sequence of tree-edit-operations transforming one tree into the other, with minimum sum of costs.

Editing tree T1 into tree T2 is done by the following tree-edit-script: (1) delete node [4] of T1, (2) morph node [1] of T1 into node [1'] of T2, (3) insert node [4'] of T2 into T1.

Depending on the cost that are associated to the tree-edit-operations, TED can either favor the topological or the geometric comparison of binding patches.

Topological comparison. To identify common patterns of nested shells encoded within the shelling tree, we compute the TED with the following costs.

Adding or deleting a node associated with a shell s has a cost of | s |, namely the number of atoms in the shell.
Morphing a shell s1 into a shell s2 corresponds to matching min( | s1 | , | s2 | ) atoms in-between the two shells, or equivalently, to a cost of max( | s1 | , | s2 | ) - min( | s1 | , | s2 | ).

At the patch level, the atoms matched by the TED calculation are called isotopologic.

Geometric comparison. Because a brute-force attempt to find isometric subset of atoms between two binding patches is intractable---it is equivalent to the NP-hard problem Max-Clique, the identification of isometric subsets is restricted to pairs of shells. That is, we define a second TED calculation as follows:

As previously, the cost of inserting/deleting a shell s is | s |.
The morphing cost between s1 and s2 is equal to the size of their symmetric difference, namely | s1 | + | s2 | - 2 | s1 ∩ s2 |, where | s1 ∩ s2 | is the number of isotopologic atoms between s1 and s2.

At the patch level, the atoms matched by the geometric TED calculation are both isotopologic and partially isometric.

2.2. Using Compatch

Compatch is a (linux) command line tool that compares two given atom shelling trees (.ast files) either by using the topological or the geometrical TED. The corresponding scores are printed into the console, and the corresponding tree-edit-script is written into a dedicated file (optional).

The Compatch flow.

As an example, assume that we wish to compare atom shelling trees 1q9q_A.ast with 1q9q_B.ast using the geometric TED (-m g), and to output the tree-edit-script files (-T) in "./output" folder (-D "directory"). The compatch command line is:

compatch-64.exe -q 1q9q_A.ast -t 1q9q_B.ast -m g -D ./output/ -T.

The output is:

Comparison between 1q9q_A.ast and 1q9q_B.ast: DIS_g = 0.55102 , |T1| = 63 , |T2| = 35 , TED = 54 , T(sec.) = 0.016487.

And this generates in ./output/ the file 1q9q_A__1q9q_B.tes which is the tree-edit-script.

The full set of options is available with the help option, that is running compatch-64.exe -h.

2.3. Implementation notes

vorpatch is implemented using the Computational Geometry Algorithms Library, and in particular the 3D spherical kernel described in [CCLT09].

3. Bibliography

[B05] A survey on tree edit distance and related problems; P. Bille; Theoretical computer science, 337(1-3):217--239, 2005.

[CPBJ06] Revisiting the Voronoi description of Protein-Protein interfaces; F. Cazals, F. Proust, and R. Bahadur, J. Janin; Protein Science, 15 (9), 2006.
[JBC08] Protein-protein interaction and quaternary structure; J. Janin and R. P. Bahadur and P. Chakrabarti; Quarterly reviews of biophysics, 41(2), 2008.

[BGNC09] Shelling the Voronoi interface of protein-protein complexes reveals patterns of residue conservation, dynamics and composition; Bouvier and R. Grunberg and M. Nilges and F. Cazals; Proteins: Structure, Function, and Bioinformatics, 76(3), 2009.
[CCLT09] Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere; P. M. M. De Castro and F. Cazals and S. Loriot and M. Teillaud; Computational Geometry: Theory and Applications, 42(6-7), 2009.

[CL10] Modeling macro-molecular interfaces with Intervor; S. Loriot and F. Cazals; Bioinformatics 26 (7); 2010. Also available as INRIA Tech report.
[MDBC11] Characterizing the Morphology of Protein Binding Patches; N. Malod-Dognin and A. Bansal and F. Cazals; INRIA Tech report 7743, 2011.

4. Downloading executables

Conditions: Free for use in academia, and subject to commercial license for other use.

Download page here (authentification required)

Group: Algorithms-Biology-Structure, INRIA Sophia-Antipolis-Mediterranee

Web: F. Cazals

Contact: abs-software@lists-sop.inria.fr