DISCO -- a MATLAB software for distributed conformation of anchor-free graph realization problems

Kim-Chuan Toh (corresponding author), and Ngai-Hang Z. Leung.

The software was first released on 25 Nov 2009. It was last updated in Dec 2012 with some bugs corrected. The software is designed to solve anchor-free graph realization problems based on semidefinite programming (SDP) relexation of the following nonconvex minimization problem:

\( \qquad \min \big\{ \sum_{(i,j)\in {\cal E}} |\|x_i-x_i\|^2-d_{ij}^2| - \lambda \sum_{ij} \|x_i-x_j\|^2 \big\} \)

where \(\lambda\) is a positive regularization parameter.

The given data is \( \{ d_{ij} \mid (i,j) \in {\cal E} \}\) with \( {\cal E}\) being a sparse subset of the set of all short-range distances given by \( \{ (ij) :\mid \|x_i-x_j\| \leq R \}\), and \(R\) is the cut-off radius.
For molecular conformation of protein molecules, \(R\) is typically set to 6 Angstrom.

Important note: this is a research software. It is not intended nor designed to be a general purpose software.
For more details, see:
  • N.-H. Z. Leung and K.-C. Toh, An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization, SIAM J. Scientific Computing, 31 (2009), pp. 4351--4372.
  • X.Y. Fang and K.C. Toh, Using a distributed SDP approach to solve simulated protein molecular conformation problems, in Distance Geometry: Theory, Methods, and Applications, A. Mucherino, C. Lavor, L. Liberti, and N. Maculan eds., Springer, 2013, pp. 351--376.
  • A movie showing how the divide-and-conquer algorithm computes the conformation of a protein molecule.

  • Sparse distance data generated from some protein molecules: MolecularData.zip. The folder contains several problems such as 1PTQ.mat which contains two structure arrays (called prob and probchem) each encoding several sparse distance matrices such as
          prob.Dmat30, prob.Lmat30, prob.Umat30.
    prob.Dmat30 corresponds to the sparse distance matrix containing 30% of distances (without noise) within the cut-off radius of 6.
    prob.Lmat30 is the corresponding lower bound for the true distances.
    prob.Umat30 is the corresponding upper bound for the true distances.
    prob.A is the true coordinates of the atoms.
    probchem is the same as prob except that the pairwise distances between neighboring atoms on the backbone and some pairwise distances of covalently bonded atoms on the side chains are also included in probchem.Dmat30, etc.