Finding nearly optimal GDT scores.

Area of Science:

• Computational Biology
• Structural Bioinformatics
• Protein Structure Prediction

Background:

• Global Distance Test (GDT) is a standard metric for assessing protein structure prediction quality.
• Current GDT computation methods are heuristic, often underestimating true scores and lacking optimality guarantees.
• The exact computation of GDT was previously considered NP-hard, limiting practical applications.

Purpose of the Study:

• To develop an efficient tool, OptGDT, for calculating GDT scores with theoretically guaranteed accuracy.
• To overcome the limitations of existing heuristic methods in protein structure quality assessment.
• To provide a practical solution for obtaining more accurate GDT scores.

Main Methods:

• Developed OptGDT, an algorithm that computes GDT scores with guaranteed accuracy relative to an optimal solution.
• The algorithm ensures the number of matched residue pairs (ℓ) is greater than or equal to the optimal number (ℓ') for a slightly smaller threshold.
• Applied OptGDT to CASP8 dataset for validation.

Main Results:

• OptGDT achieved improved GDT scores for 87.3% of predicted models in the CASP8 dataset.
• Significant improvements were observed, with some cases showing at least a 10% increase in matched residue pairs.
• The tool exhibits efficient runtime complexity: O(n³ log n/ε⁵) for general cases and O(n log² n) for globular proteins using a randomized approach.

Conclusions:

• OptGDT offers a significant advancement in accurately assessing protein structure prediction quality.
• The tool provides theoretically sound and practically improved GDT scores compared to existing heuristic methods.
• OptGDT is available under the GPL license, promoting its use in the field.