Please use this identifier to cite or link to this item: https://doi.org/10.1137/05062754X
Title: A Distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation
Authors: Biswas, P.
Toh, K.-C. 
Ye, Y.
Keywords: Anchor-free graph realization
Molecular conformation
Semidefinite programming
Issue Date: 2007
Citation: Biswas, P., Toh, K.-C., Ye, Y. (2007). A Distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM Journal on Scientific Computing 30 (3) : 1251-1277. ScholarBank@NUS Repository. https://doi.org/10.1137/05062754X
Abstract: We propose a distributed algorithm for solving Euclidean metric realization problems arising from large 3-D graphs, using only noisy distance information and without any prior knowledge of the positions of any of the vertices. In our distributed algorithm, the graph is first subdivided into smaller subgraphs using intelligent clustering methods. Then a semidefinite programming relaxation and gradient search method are used to localize each subgraph. Finally, a stitching algorithm is used to find affine maps between adjacent clusters, and the positions of all points in a global coordinate system are then derived. In particular, we apply our method to the problem of finding the 3-D molecular configurations of proteins ba.sed on a. limited number of given pairwise distances between atoms. The protein molecules, all with known molecular configurations, are taken from the Protein Data Bank. Our algorithm is able to reconstruct reliably and efficiently the configurations of large protein molecules from a limited number of pairwise distances corrupted by noise, without incorporating domain knowledge such as the minimum separation distance constraints derived from van der Waals interactions. © 2008 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Scientific Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/102634
ISSN: 10648275
DOI: 10.1137/05062754X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


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