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.