Discretization orders and efficient computation of Cartesian coordinates for distance geometry. (English) Zbl 1302.90177
Summary: Distance geometry is a class of problems where the position of points in space is to be identified by using information about some relative distances between these points. Although continuous approaches are usually employed, problems belonging to this class can be discretized when some particular assumptions are satisfied. These assumptions strongly depend on the order in which the points to be positioned are considered. We discuss new discretization assumptions that are weaker than previously proposed ones, and present a greedy algorithm for an automatic identification of discretization orders. The use of these weaker assumptions motivates the development of a new method for computing point coordinates. Computational experiments show the effectiveness and efficiency of the proposed approaches when applied to protein instances.
MSC:
| 90C27 | Combinatorial optimization |
Keywords:
distance geometry; combinatorial optimization; discretization orders; coordinate computation; molecular conformationsReferences:
| [1] | Alipanahi, B., Krislock, N., Ghodsi, A., Wolkowicz, H., Donaldson, L., Li, M.: Determining protein structures from noesy distance constraints by semidefinite programming. J. Comput. Biol. 20(4), 296-310 (2013) · doi:10.1089/cmb.2012.0089 |
| [2] | Berman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., Bourne, P.: The protein data bank. Nucleic Acids Res. 28, 235-242 (2000) · doi:10.1093/nar/28.1.235 |
| [3] | Biswas, P., Lian, T., Wang, T., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sen. Netw. 2, 188-220 (2006) · doi:10.1145/1149283.1149286 |
| [4] | Cassioli, A., Günlük, O., Lavor, C., Liberti, L.: Discretization vertex orders in distance geometry, working paper (2014) · Zbl 1321.05029 |
| [5] | Coope, I.D.: Reliable computation of the points of intersection of \[n\] n spheres in \[n\] n-space. ANZIAM J. 42, 461-477 (2000) · Zbl 0977.65016 |
| [6] | Costa, V., Mucherino, A., Lavor, C., Carvalho, L.M., Maculan, N.: On suitable orders for discretizing molecular distance geometry problems related to protein side chains. In: IEEE Conference Proceedings, pp. 397-402. Workshop on Computational Optimization (WCO12), FedCSIS12, Wroclaw, Poland (2012) · Zbl 1258.90096 |
| [7] | Crippen, G.M., Havel, T.F.: Distance Geometry and Molecular Conformation. John Wiley & Sons, New York (1988) · Zbl 1066.51500 |
| [8] | Gonçalves, D., Mucherino, A., Lavor, C.: Energy-based pruning devices for the bp algorithm for distance geometry. In: IEEE Conference Proceedings, pp. 335-340. Workshop on Computational Optimization (WCO13), FedCSIS13, Krakow, Poland (2013) · Zbl 1272.90074 |
| [9] | Grosso, A., Locatelli, M., Schoen, F.: Solving molecular distance geometry problems by global optimization algorithms. Comput. Optim. Appl. 43(1), 23-37 (2009) · Zbl 1176.90567 · doi:10.1007/s10589-007-9127-8 |
| [10] | Lavor, C., Lee, J., John, A.L.S., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization orders for distance geometry problems. Optim. Lett. 6(4), 783-796 (2012) · Zbl 1258.90096 · doi:10.1007/s11590-011-0302-6 |
| [11] | Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52, 115-146 (2012) · Zbl 1259.90153 · doi:10.1007/s10589-011-9402-6 |
| [12] | Lavor, C., Liberti, L., Mucherino, A.: The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances. J. Glob. Optim. 56(3), 855-871 (2013) · Zbl 1272.90074 · doi:10.1007/s10898-011-9799-6 |
| [13] | Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Review 56(1), to appear (2014) · Zbl 1292.51010 |
| [14] | Linge, J.P., Nilges, M.: Influence of non-bonded parameters on the quality of nmr structures: a new force field for nmr structure calculation. J. Biomol. NMR 13(1), 51-59 (1999) · doi:10.1023/A:1008365802830 |
| [15] | Malliavin, T.E., Mucherino, A., Nilges, M.: Distance geometry in structural biology: new perspectives. In [19] pp. 329-350 (2013) · Zbl 1366.92095 |
| [16] | Moré, J.J., Wu, Z.: Distance geometry optimization for protein structures. J. Glob. Optim. 15, 219-223 (1999) · Zbl 0944.92012 · doi:10.1023/A:1008380219900 |
| [17] | Mucherino, A.: On the identification of discretization orders for distance geometry with intervals. In: Proceedings of Geometric Science of Information (GSI13). Lecture Notes in Computer Science 8085, pp. 231-238. France, Paris (2013) · Zbl 1405.51008 |
| [18] | Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. 6(8), 1671-1686 (2012) · Zbl 1258.90100 · doi:10.1007/s11590-011-0358-3 |
| [19] | Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.): Distance Geometry: Theory, Methods and Applications, p 410. Springer, New York (2013) · Zbl 1256.51002 |
| [20] | Thompson, H.B.: Calculation of cartesian coordinates and their derivatives from internal molecular coordinates. J. Chem. Phys. 47, 3407-3410 (1967) · doi:10.1063/1.1712406 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
