Geometric Methods for Protein Structure Comparison

In this paper, we review some of the theoretical results on the computa- tional complexity of the algorithms designed to obtain optimal solutions to the problem of matching sets of points using specific metrics. From a theo- retical point of view, the problem has been extensively studied in the area of computational geometry, where it is often formulated as the problem of find- ing correspondences between sets of geometric features (for instance, points or segments). From these studies it appears that, in most practical cases, exact algorithms are too time consuming to be useful. Thus, approximate algorithms are considered that are computationally practical and at the same time are guaranteed to produce solutions that are within a certain bound from optimal. Furthermore, we discuss methods for the estimation of rigid transforma- tions under different metrics such as the Root Mean Square Deviation (RMSD) and the Hausdorff distance. Geometric indexing techniques prove their effec- tiveness in searching large protein databases and they are presented in details. Finally graph-theoretic protein modeling is reviewed as it is useful in designing algorithms for substructure identification and comparison.