A distributed SDP-based algorithm for large noisy anchor-free graph realization

Abstract

We propose the DISCO algorithm for graph realization in $\real^d$,given sparse and noisy short-range inter-vertex distances as inputs.Our divide-and-conquer algorithm works as follows.When a group has a sufficiently small number of vertices,the basis step is to form a graph realizationby solving a semidefinite program.The recursive step is to break a large group of verticesinto two smaller groups with overlapping vertices.These two groups are solved recursively,and the sub-configurations are stitched together,using the overlapping atoms,to form a configurations for the larger group.At intermediate stages,the configurations are improvedby gradient descent refinement.The algorithm is applied to the problem ofdetermining protein molecule structure.Tests are performed on moleculestaken from the Protein Data Bank database.Given 20--30\% of the inter-atom distances less than 6 \AA\that are corrupted by a high level of noise,DISCO is able to reliably and efficientlyreconstruct the conformation of large molecules.In particular,given 30\% of distances with 20\% multiplicative noise,a 13000-atom conformation problem is solvedwithin an hour with an RMSD of 1.6 \AA.