Solving the contact map overlap problem via tree decomposition and a DEE-like pruning strategy

This paper proposes a new algorithm for protein structure alignment in the case where a protein structure is represented by a contact map graph and the sequential order of residues is strictly enforced in the alignment. The time complexity of the algorithm, O(n(2n+w)!/((2n)!w!)) where n is the maximum number of residues in two proteins and w = O((D_u/D_l) n^2/3 log n) is the treewidth of a contact graph. In particular, D_u is the contact distance cutoff and D_c is the minimum inter-residue distance in a typical protein. If the distance between two matched residues after two proteins are superimposed is bounded by a parameter D_c, then the time complexity is O((n/epsivD_c)⁶((n+w)!/(n!w!)Delta^w)) where e is a small constant and Delta = (1 + (2D_c/D_l))³. This algorithm consists of two major components: tree-decomposition and a DEE-like pruning strategy. The tree-decomposition method exploits the geometric feature of a protein structure and guarantees to terminate within subexponential time. The DEE-like pruning strategy exploits the sequential constraint and can quickly eliminate non-optimal alignments from a large search space. Based on these two techniques, we have developed a structure alignment program TreeAlign to find the globally optimal solution of the contact map overlap problem. The preliminary experimental results indicate that on a Linux PC with 2.5 GHz CPU, TreeAlign can align two similar proteins within seconds and two dissimilar proteins within minutes.