with vorpatch and compatch
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.|
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.|
The full set of options is available with the help option, that is running vorpatch-64.exe -h.
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  of T1, (2) morph node  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.
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:
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.
The full set of options is available with the help option, that is running compatch-64.exe -h.
Group: Algorithms-Biology-Structure, INRIA Sophia-Antipolis-Mediterranee
Web: F. Cazals