A polynomial time algorithm for computing the area under a GDT curve. Issue 1 (December 2015)

• Record Type: Journal Article
• Authors: Poleksic, Aleksandar
• Is Part Of: Algorithms for molecular biology. Volume 10:Issue 1(2015)
• Page Start: 1
• Page End: 8
• Publication Date: 2015-12
• Subjects: Protein structure -- Structure modeling -- Structure prediction -- Model quality; Molecular biology -- Mathematical models -- Periodicals; Algorithms -- Periodicals; Bioinformatics -- Periodicals; 572.8015118
• DOI: 10.1186/s13015-015-0058-0
• Languages: English
• ISSNs: 1748-7188

Abstract

Abstract Background Progress in the field of protein three-dimensional structure prediction depends on the development of new and improved algorithms for measuring the quality of protein models. Perhaps the best descriptor of the quality of a protein model is theGDT function that maps each distance cutoffθ to the number of atoms in the protein model that can be fit under the distanceθ from the corresponding atoms in the experimentally determined structure. It has long been known that the area under the graph of this function (GDT _A ) can serve as a reliable, single numerical measure of the model quality. Unfortunately, while the well-knownGDT _TS metric provides a crude approximation ofGDT _A, no algorithm currently exists that is capable of computing accurate estimates ofGDT _A . Methods We prove thatGDT_A is well defined and that it can be approximated by the Riemann sums, using available methods for computing accurate (near-optimal)GDT function values. Results In contrast to theGDT_TS metric, GDT _A is neither insensitive to large nor oversensitive to small changes in model's coordinates. Moreover, the problem of computingGDT _A is tractable. More specifically, GDT _A can be computed in cubic asymptotic time in the size of the protein model. Conclusions This paper presents the first algorithm capable of computing the near-optimal estimates of the area under theGDT function for a protein model. We believe that the techniques implemented in our algorithm will pave ways for the development of more practical and reliable procedures for estimating 3D model quality.