Eigenvector synchronization, graph rigidity and the molecule problem
Open Access
- 1 December 2012
- journal article
- research article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 1 (1) , 21-67
Abstract
The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. In this paper, we extend the previous work and propose the 3D-As-Synchronized-As-Possible (3D-ASAP) algorithm, for the graph realization problem in ℝ3, given a sparse and noisy set of distance measurements. 3D-ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch, there corresponds an element of the Euclidean group, Euc(3), of rigid transformations in ℝ3, and the goal was to estimate the group elements that will properly align all the patches in a globally consistent way. Furthermore, 3D-ASAP successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose 3D-spectral-partitioning (SP)-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a pre-processing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that 3D-ASAP and 3D-SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably with similar state-of-the-art localization algorithms.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite ProgrammingSIAM Journal on Imaging Sciences, 2011
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- The HADDOCK web server for data-driven biomolecular dockingNature Protocols, 2010
- A remark on global positioning from local distancesProceedings of the National Academy of Sciences, 2008
- Extending the Power of Quantum Chemistry to Large Systems with the Fragment Molecular Orbital MethodThe Journal of Physical Chemistry A, 2007
- ARIA2: Automated NOE assignment and data integration in NMR structure calculationBioinformatics, 2006
- NMR in the SPINE Structural Proteomics projectActa Crystallographica Section D Structural Biology, 2006
- Weak alignment NMR: a hawk-eyed view of biomolecular structureCurrent Opinion in Structural Biology, 2005
- NMR studies of structure and function of biological macromolecules (Nobel Lecture)*Journal of Biomolecular NMR, 2003
- Least-Squares Fitting of Two 3-D Point SetsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1987