Revisiting of the Computational Complexity of Distance Matrix Based Structure Alignment

Proteins of similar structures are likely to share similar functions. Comparing the structures of proteins allows us to study protein functions, which are important to the biological and medical sciences. There is no standard approach or criterion for comparing the similarity between structures. We consider the approaches called structural alignment and model comparison. Several comparison measures are actively used by bioinformaticists in these approaches. Here, we focus on the Squared Euclidean Distance, TM-score, and the GDT, among several other measures. These measures are typically assumed to be hard to compute, due to similarity between the underlying problems with known NP-hard problems; all but a few proposed algorithms offer theoretically guaranteed accuracy in their results. This becomes a problem when accuracy is critical, or when authoritative results are needed. In this study we reexamine the complexity in computing these measures, in an attempt to devise better algorithms for these computations.