Finding nearly optimal GDT scores

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)693-704
Journal / PublicationJournal of Computational Biology
Issue number5
Publication statusPublished - 1 May 2011
Externally publishedYes


Global Distance Test (GDT) is one of the commonly accepted measures to assess the quality of predicted protein structures. Given a set of distance thresholds, GDT maximizes the percentage of superimposed (or matched) residue pairs under each threshold, and reports the average of these percentages as the final score. The computation of GDT score was conjectured to be NP-hard. All available methods are heuristic and do not guarantee the optimality of scores. These heuristic strategies usually result in underestimated GDT scores. Contrary to the conjecture, the problem can be solved exactly in polynomial time, albeit the method would be too slow for practical usage. In this paper we propose an efficient tool called OptGDT to obtain GDT scores with theoretically guaranteed accuracies. Denote ℓ as the number of matched residue pairs found by OptGDT for a given threshold d. Let ℓ′ be the optimal number of matched residues pairs for threshold d/(1 + ε), where ε is a parameter in our computation. OptGDT guarantees that ℓ≥ℓ′. We applied our tool to CASP8 (The eighth Critical Assessment of Structure Prediction Techniques) data. For 87.3% of the predicted models, better GDT scores are obtained when OptGDT is used. In some cases, the number of matched residue pairs were improved by at least 10%. The tool runs in time O(n3 log n/ε 5) for a given threshold d and parameter ε. In the case of globular proteins, the tool can be improved to a randomized algorithm of O(n log2 n) runtime with probability at least 1 - O(1/n). Released under the GPL license and downloadable from ∼scli/OptGDT/. © Copyright 2011, Mary Ann Liebert, Inc. 2011.

Research Area(s)

  • algorithms, alignment, computational molecular biology, linear programming, protein folding

Citation Format(s)

Finding nearly optimal GDT scores. / Li, Shuai Cheng; Bu, Dongbo; Xu, Jinbo et al.
In: Journal of Computational Biology, Vol. 18, No. 5, 01.05.2011, p. 693-704.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review