GR-Align

GR-Align aligns and compares protein tertiary structures by maximizing Contact Map Overlap (CMO) using graphlet-based node similarity within a modified Needleman-Wunsch scoring framework.

Key Features:

• Heuristic approach: Employs a fast heuristic procedure to maximize Contact Map Overlap (CMO) for rapid structure comparison.
• Graphlet-based similarity measure: Uses graphlets (small induced subgraphs) generalized to ordered graphs to compute sensitive topological similarity between residues and networks.
• Needleman-Wunsch foundation: Implements a modified Needleman-Wunsch algorithm where the cost of matching two residues is determined by their graphlet degree similarity.
• Flexible alignments: Supports flexible alignment strategies demonstrated on datasets such as Astral-40 (11,154 protein domains).

Scientific Applications:

• Database searches: Suited for large-scale database searches and rapid comparison across protein domain datasets such as Proteus_300 (44,850 domain pairs) and Astral-40.
• Structural classification correlation: Produces similarity scores that correlate with structural classification and facilitate information transfer between well-studied and less-studied proteins.
• Benchmarking and comparative performance: Demonstrated superior runtime on Proteus_300 compared with CMO solvers Apurva, MSVNS, and AlEigen7, and on a 3,207,270-domain-pair gold-standard benchmark was faster than TM-Align, DaliLite, MATT, and Yakusa while achieving comparable classification performance.

Methodology:

Maximizes Contact Map Overlap (CMO) via a fast heuristic; computes graphlet degree similarity using graphlets generalized to ordered graphs; and applies a modified Needleman-Wunsch algorithm where match costs are determined by graphlet degree similarity.