Sparsifying Distance Matrices for Protein-Protein Structure Alignments
A. Mucherino, I. Wohlers, G.W. Klau, R. Andonov

The problem of finding similarities between native protein conformations can be formulated as the problem of aligning inter-residue distance matrices. Recently proposed exact algorithms are able to solve this problem for large proteins only if the considered distance matrices are sparse. We propose a strategy for sparsifying distance matrices in which we keep the distances needed for uniquely reconstructing the conformations of the proteins.