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 realization by solving a semidefinite program. The recursive step is to break a large group of vertices into 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 improved by gradient descent refinement. The algorithm is applied to the problem of determining protein molecule structure. Tests are performed on molecules taken 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 efficiently reconstruct the conformation of large molecules. In particular, given 30\% of distances with 20\% multiplicative noise, a 13000-atom conformation problem is solved within an hour with an RMSD of 1.6\AA.
Citation
Preprint, Department of Mathematics, National University of Singapore, August 2008.
Article
View An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization