×

zbMATH — the first resource for mathematics

A Euclidean distance matrix model for protein molecular conformation. (English) Zbl 1436.90112
Summary: Protein molecular conformation is an important and challenging problem in biophysics. It is to recover the structure of proteins based on limited information such as noised distances, lower and upper bounds on some distances between atoms. In this paper, based on the recent progress in numerical algorithms for Euclidean distance matrix (EDM) optimization problems, we propose a EDM model for protein molecular conformation. We reformulate the problem as a rank-constrained least squares problem with linear equality constraints, box constraints, as well as a cone constraint. Due to the nonconvexity of the problem, we develop a majorized penalty approach to solve the problem. We apply the accelerated block coordinate descent algorithm proposed in [D. Sun et al., SIAM J. Optim. 26, No. 2, 1072–1100 (2016; Zbl 1346.90658)] to solve the resulting subproblem. Extensive numerical results demonstrate the efficiency of the proposed model.

MSC:
90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfakih, AY; Wolkowicz, H., Euclidean Distance Matrices and the Molecular Conformation Problem (2002), Waterloo: Faculty of Mathematics, University of Waterloo, Waterloo
[2] Biswas, P.; Toh, KC; Ye, Y., A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation, SIAM J. Sci. Comput., 30, 3, 1251-1277 (2008) · Zbl 1161.49028
[3] Biswas, P.; Liang, TC; Toh, KC; Ye, Y.; Wang, TC, Semidefinite programming approaches for sensor network localization with noisy distance measurements, IEEE Trans. Autom. Sci. Eng., 3, 4, 360-371 (2006)
[4] Biswas, P.; Ye, Y.; Hager, WW; Pardalos, PM; Huang, S-J, A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization, Multiscale Optimization Methods and Applications, 69-84 (2006), Boston: Springer, Boston · Zbl 1100.90029
[5] Cao, M.Z., Li, Q.N.: An ordinal weighted EDM model for nonmetric multidimensional scaling: an application to image ranking. Technical report, Beijing Institute of Technology (2018)
[6] Cox, TF; Cox, MAA, Multidimensional Scaling (2000), Boca Raton: Chapman and hall/CRC, Boca Raton
[7] Ding, C.; Qi, HD, Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation, Comput. Optim. Appl., 66, 1, 187-218 (2017) · Zbl 1369.90120
[8] Ding, C.; Qi, HD, Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction, Math. Program., 164, 1-2, 341-381 (2017) · Zbl 1391.90472
[9] Dattorro, J., Convex Optimization and Euclidean Distance Geometry (2005), Palo Alto: Meboo publish Google Scholar, Palo Alto
[10] Dokmanic, I.; Parhizkar, R.; Ranieri, J.; Vetterli, M., Euclidean distance matrices: essential theory, algorithms, and applications, IEEE Signal Process. Mag., 32, 6, 12-30 (2015)
[11] Dai, Y.J., Yao, Z.Q., Li, Q.N., Xie, D.: Innovative posture sensing method for large engineering manipulators based on nearest Euclidean distance matrix. Technical report, Xiangtan University (2018)
[12] Fang, XY; Toh, KC, Using a Distributed SDP Approach to Solve Simulated Protein Molecular Conformation Problems, 351-376 (2013), New York: Springer, New York · Zbl 1271.68233
[13] Gansner, ER; Hu, Y.; North, S., A maxent-stress model for graph layout, IEEE Trans. Vis. Comput. Gr., 19, 6, 927-940 (2013)
[14] Gao, Y.: Structured low rank matrix optimization problems: a penalized approach. PhD thesis, National University of Singapore, August (2010)
[15] Jiang, KF; Sun, DF; Toh, KC, A partial proximal point algorithm for nuclear norm regularized matrix least squares problems, Math. Program. Comput., 6, 281-325 (2014) · Zbl 1327.90109
[16] Huang, HX; Liang, ZA; Pardalos, PM, Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems, J. Glob. Optim., 25, 1, 3-21 (2003) · Zbl 1037.15015
[17] Hoai An, LT, Solving large scale molecular distance geometry problems by a smoothing technique via the Gaussian transform and D.C. programming, J. Glob. Optim., 27, 4, 375-397 (2003) · Zbl 1064.90036
[18] Kelder, DD; Gabriëlle, M., Distance geometry and molecular conformation, Trends Pharmacol. Sci., 10, 4, 164 (1988)
[19] Lavor, C.; Alves, R.; Figueiredo, W.; Petraglia, A.; Maculan, N., Clifford algebra and the discretizable molecular distance geometry problem, Adv. Appl. Clifford Algebras, 25, 4, 925-942 (2015) · Zbl 1327.15052
[20] Li, QN; Li, DH, A projected semismooth Newton method for problems of calibrating least squares covariance matrix, Oper. Res. Lett., 39, 2, 103-108 (2011) · Zbl 1218.90220
[21] Liberti, L.; Lavor, C.; Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem, Int. Trans. Oper. Res., 15, 1, 1-17 (2008) · Zbl 1136.92037
[22] Li, QN; Qi, HD, An inexact smoothing Newton method for Euclidean distance matrix optimization under ordinal constraints, J. Comput. Math., 35, 4, 467-483 (2017)
[23] Leung, NHZ; Toh, KC, An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization, SIAM J. Sci. Comput., 31, 6, 4351-4372 (2009) · Zbl 1203.93157
[24] Liberti, L.; Lavor, C.; Maculan, N.; Mucherino, A., Euclidean distance geometry and applications, Siam Rev., 56, 1, 3-69 (2014) · Zbl 1292.51010
[25] Li, XD; Sun, DF; Toh, KC, QSDPNAL: a two-phase proximal augmented Lagrangian method for convex quadratic semidefinite programming, Math. Program. Comput., 10, 1-41 (2018) · Zbl 1411.90213
[26] Li, XD; Sun, DF; Toh, KC, A block symmetric Gauss-Seidel decomposition theo for convex composite quadratic programming and its applications, Math. Program., 16, 1-24 (2017)
[27] Moré, JJ; Wu, Z., Distance geometry optimization for protein structures, J. Glob. Optim., 15, 3, 219-234 (1999) · Zbl 0944.92012
[28] Qi, HD, A semismooth Newton method for the nearest Euclidean distance matrix problem, SIAM J. Matrix Anal. Appl., 34, 1, 67-93 (2013) · Zbl 1266.49052
[29] Qi, HD; Xiu, NH; Yuan, XM, A lagrangian dual approach to the single-source localization problem, IEEE Trans. Signal Process., 61, 15, 3815-3826 (2013) · Zbl 1393.94401
[30] Qi, HD; Yuan, XM, Computing the nearest Euclidean distance matrix with low embedding dimensions, Math. program., 147, 1-2, 351-389 (2014) · Zbl 1304.49051
[31] Schoenberg, IJ, Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espaces distanciés vectoriellement applicable sur l’espace de Hilbert”, Ann. Math., 36, 3, 724-732 (1935) · Zbl 0012.30703
[32] Sun, DF; Toh, KC; Yang, LQ, An efficient inexact ABCD method for least squares semidefinite programming, SIAM J. Optim., 26, 2, 1072-1100 (2016) · Zbl 1346.90658
[33] Toh, KC, An inexact primal-dual path-following algorithm for convex quadratic SDP, Math. Program., 112, 1, 221-254 (2008) · Zbl 1136.90027
[34] Toh, K.C.: User guide for QSDP-0—a Matlab software package for convex quadratic semidefinite programming. Technical report, Department of Mathematics, National University of Singapore, Singapore (2010)
[35] Tütüncü, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program. Ser. B, 95, 2, 189-217 (2003) · Zbl 1030.90082
[36] Wegner, M., Taubert, O., Schug, A., Meyerhenke, H.: Maxent-stress optimization of 3D biomolecular models. arXiv preprint arXiv:1706.06805 (2017)
[37] Young, G.; Householder, AS, Discussion of a set of points in terms of their mutual distances, Psychometrika, 3, 1, 19-22 (1938) · JFM 64.1302.04
[38] Yu, PP; Li, QN, Ordinal distance metric learning with MDS for image ranking, Asia Pac. J. Oper. Res., 35, 1, 1850007 (2018) · Zbl 1386.68144
[39] Zou, Z.; Bird, RH; Schnabel, RB, A stochastic/perturbation global optimization algorithm for distance geometry problems, J. Glob. Optim., 11, 1, 91-105 (1997) · Zbl 0891.90173
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.