How to evaluate the quality of models is a basic problem for the field of protein structure prediction. Numerous evaluation criteria have been proposed, and one of the most intuitive criteria requires us to find a  largest well-predicted subset -- a maximum subset of the model which matches the native structure [12]. The problem is solvable in  O ( n 7) time, albeit too slow for practical usage. We present a (1 +  i¾? ) d distance approximation algorithm that runs in time  O ( n 3log n / i¾? 5) for general protein structures. In the case of globular proteins, this result can be enhanced to a randomized  O ( n log2 n ) time algorithm with probability at least 1 i¾?  O (1/ n ). In addition, we propose a (1 +  i¾? )-approximation algorithm to compute the minimum distance to fit all the points of a model to its native structure in time  O ( n (loglog n + log1/ i¾? )/ i¾? 5). We have implemented our algorithms and results indicate our program finds much more matched pairs with less running time than TMScore, which is one of the most popular tools to assess the quality of predicted models.
['Shuai Cheng Li', 'Dongbo Bu', 'Jinbo Xu', 'Ming Li']
Finding Largest Well-Predicted Subset of Protein Structure Models