Improved Algorithms for Matching r-Separated Sets with Applications to Protein Structure Alignment

The Largest Common Point-set (LCP) and the Pattern Matching (PM) problems have received much attention in the fields of pattern matching, computer vision and computational biology. Perhaps, the most important application of these problems is the protein structural alignment, which seeks to find a superposition of a pair of input proteins that maximizes a given protein structure similarity metric. Although it has been shown that LCP and PM are both tractable problems, the running times of existing algorithms are high-degree polynomials. Here, we present novel methods for finding approximate and exact threshold-LCP and threshold-PM for r-separated sets, in general, and protein 3D structures, in particular. Improved running times of our methods are achieved by building upon several different, previously published techniques.