  


An SDPbased divideandconquer algorithm for large scale noisy anchorfree graph realization
NgaiHang Z. Leung (deutsixfivegmail.com) Abstract: We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy shortrange intervertex distances as inputs. Our divideandconquer 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 subconfigurations 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 2030\% of the interatom 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 13000atom conformation problem is solved within an hour with an RMSD of 1.6\AA. Keywords: SDP, divideandconquer, 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 (Semidefinite Programming ) Citation: Preprint, Department of Mathematics, National University of Singapore, August 2008. Download: [PDF] Entry Submitted: 08/22/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  