Please use this identifier to cite or link to this item:
Title: A distributed SDP-based algorithm for large noisy anchor-free graph realization
Keywords: molecular conformation, semidefinite programming, graph localization
Issue Date: 23-Jul-2009
Citation: LEUNG NGAI-HANG ZACHARY (2009-07-23). A distributed SDP-based algorithm for large noisy anchor-free graph realization. ScholarBank@NUS Repository.
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.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
mol-conf.pdf1.58 MBAdobe PDF



Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.