Aligning Protein Structures with GR-Align (GRaphlet-based Aligner)



Noel Malod-Dognin and Natasa Przulj



Corresponding author: Dr. N. Malod-Dognin, e-mail: n.malod-dognin [AT] cs.ucl.ac.uk


GR-Align is a fast heuristic procedure for aligning/comparing protein structures according to the Contact Map Opverlap maximization (CMO) paradigm. The algorithm is based on a Needleman-Wunch algorithm where the cost for matching two residues is their graphlet degree similarity.

Update. Outputs of the original software were hard to parse. In version 1.5, aligned residues are now labelled with their pdb-ids.




How to run GR-Align

GR-Align packages contains three software: CMap, DCount, and GR-Align:
  • CMap converts protein structures (.pdb) files into contact map graphs (leda graphs .gw)
  • DCount computes the graphlet degree signatures (.ndump files) from Contact Maps
  • GR-Align aligns protein structures (requieres both contact maps and signatures files)
Run each software without parameters (or with -h) and it will display usage directions



Sample Usage

Creating a contact map graph (.gw file) from the first chain (A) of structure 1amk (file 1amk.pdb)
  • ./CMap -i 1amk.pdb -c A -o 1amkA.gw -d 7.5
Computing the graphlet degree signature (.ndump file) from the above generated contact map (1amkA.gw)
  • ./DCount -i 1amkA.gw -o 1amkA.ndump
Aligning all structures from the Skolnick set, listed in skolnick.lst, the signatures and contact maps being in ./skolnick.
  • ./GR-Align -q skolnick.lst -r ./skolnick -o results.txt

optimal_matching


Other Contact Map Overlap maximization algorithms

bottom image