DISCO -- a MATLAB software for distributed conformation of anchor-free graph realization problems: An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization. We propose the DISCO algorithm for graph realization in ℝ d , given sparse and noisy short-range intervertex 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 subconfigurations are stitched together, using the overlapping atoms, to form a configuration 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 moleculer structure. Tests are performed on molecules taken from the Protein Data Bank database. For each molecule, given 20–30% of the inter-atom distances less than 6Å 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 a root mean square deviation of 1.6Å.
Keywords for this software
References in zbMATH (referenced in 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
- Lu, Si-Tong; Zhang, Miao; Li, Qing-Na: Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints (2020)
- Sun, Defeng; Toh, Kim-Chuan; Yuan, Yancheng; Zhao, Xin-Yuan: SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0) (2020)
- Zhai, Fengzhen; Li, Qingna: A Euclidean distance matrix model for protein molecular conformation (2020)
- Wegner, Michael; Taubert, Oskar; Schug, Alexander; Meyerhenke, Henning: Maxent-stress optimization of 3D biomolecular models (2017)
- Fang, Xingyuan; Toh, Kim-Chuan: Using a distributed SDP approach to solve simulated protein molecular conformation problems (2013)
- Cucuringu, Mihai; Singer, Amit; Cowburn, David: Eigenvector synchronization, graph rigidity and the molecule problem (2012)
- Leung, Ngai-Hang Z.; Toh, Kim-Chuan: An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization (2009)