Optimization Online


An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization

Ngai-Hang Z. Leung (deutsixfive***at***gmail.com)
Kim-Chuan Toh (mattohkc***at***nus.edu.sg)

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 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.

Keywords: SDP, divide-and-conquer, molecular conformation, graph realization

Category 1: Applications -- Science and Engineering (Basic Sciences Applications )

Category 2: Global Optimization (Applications )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Preprint, Department of Mathematics, National University of Singapore, August 2008.

Download: [PDF]

Entry Submitted: 08/22/2008
Entry Accepted: 08/22/2008
Entry Last Modified: 08/22/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society