On the optimality of finding DMDGP symmetries. (English) Zbl 1476.51012
Summary: The Discretizable Molecular Distance Geometry Problem (DMDGP) is a subclass of the Distance Geometry Problem, which aims to embed a weighted simple undirected graph in a Euclidean space, such that the distances between the points correspond to the values given by the weighted edges in the graph. The search space of the DMDGP is combinatorial, based on a total vertex order that implies symmetry properties related to partial reflections around planes defined by the Cartesian coordinates of three immediate and consecutive vertices that precede the so-called symmetry vertices. Since these symmetries allow us to know a priori the cardinality of the solution set and to calculate all the DMDGP solutions, given one of them, it would be relevant to identify these symmetries efficiently. Exploiting mathematical properties of the vertices associated with these symmetries, we present an optimal algorithm that finds such vertices.
MSC:
| 51K05 | General theory of distance geometry |
| 68R05 | Combinatorics in computer science |
| 05C90 | Applications of graph theory |
References:
| [1] | Billinge, S.; Duxbury, P.; Gonçalves, D.; Lavor, C.; Mucherino, A., Assigned and unassigned distance geometry: applications to biological molecules and nanostructures, 4OR, 14, 337-376 (2016) · Zbl 1364.51005 · doi:10.1007/s10288-016-0314-2 |
| [2] | Billinge, S.; Duxbury, P.; Gonçalves, D.; Lavor, C.; Mucherino, A., Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures, Ann Oper Res, 271, 161-203 (2018) · Zbl 1429.51011 · doi:10.1007/s10479-018-2989-6 |
| [3] | Carvalho, R.; Lavor, C.; Protti, F., Extending the geometric build-up algorithm for the molecular distance geometry problem, Inf Process Lett, 108, 234-237 (2008) · Zbl 1191.68772 · doi:10.1016/j.ipl.2008.05.009 |
| [4] | Cassioli, A.; Gunluk, O.; Lavor, C.; Liberti, L., Discretization vertex orders in distance geometry, Discret Appl Math, 197, 27-41 (2015) · Zbl 1321.05029 · doi:10.1016/j.dam.2014.08.035 |
| [5] | Cassioli, A.; Bordiaux, B.; Bouvier, G.; Mucherino, A.; Alves, R.; Liberti, L.; Nilges, M.; Lavor, C.; Malliavin, T., An algorithm to enumerate all possible protein conformations verifying a set of distance constraints, BMC Bioinform, 16, 16-23 (2015) · doi:10.1186/s12859-015-0451-1 |
| [6] | Crippen, G.; Havel, T., Distance geometry and molecular conformation (1988), Oxford: Wiley, Oxford · Zbl 1066.51500 |
| [7] | Fidalgo, F.; Gonçalves, D.; Lavor, C.; Liberti, L.; Mucherino, A., A symmetry-based splitting strategy for discretizable distance geometry problems, J Global Optim, 71, 717-733 (2018) · Zbl 1405.90134 · doi:10.1007/s10898-018-0610-9 |
| [8] | Lavor C, Liberti L, Maculan N (2005) Grover’s algorithm applied to the molecular distance geometry problem. In: Proceedings of the 7th Brazilian congress of neural networks · Zbl 1136.92037 |
| [9] | Lavor, C.; Liberti, L.; Maculan, N.; Pintér, J., Computational experience with the molecular distance geometry problem, Global optimization: scientific and engineering case studies, 213-225 (2006), Berlin: Springer, Berlin · Zbl 1129.90389 · doi:10.1007/0-387-30927-6_9 |
| [10] | Lavor, C.; Lee, J.; Lee-St, JA; Liberti, L.; Mucherino, A.; Sviridenko, M., Discretization orders for distance geometry problems, Optim Lett, 6, 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.; Maculan, N.; Mucherino, A., Recent advances on the discretizable molecular distance geometry problem, Eur J Oper Res, 219, 698-706 (2012) · Zbl 1253.05132 · doi:10.1016/j.ejor.2011.11.007 |
| [13] | Lavor, C.; Liberti, L.; Lodwick, W.; da Costa, TM, An introduction to distance geometry applied to molecular geometry (2017), Berlin: Springer, Berlin · Zbl 1403.92001 · doi:10.1007/978-3-319-57183-6 |
| [14] | Lavor, C.; Liberti, L.; Donald, B.; Worley, B.; Bardiaux, B.; Malliavin, T.; Nilges, M., Minimal NMR distance information for rigidity of protein graphs, Discret Appl Math, 256, 91-104 (2019) · Zbl 1405.05178 · doi:10.1016/j.dam.2018.03.071 |
| [15] | Lavor, C.; Souza, M.; Mariano, L.; Liberti, L., On the polinomiality of finding \(^K\) DMDGP re-orders, Discret Appl Math, 267, 190-194 (2019) · Zbl 1419.05037 · doi:10.1016/j.dam.2019.07.021 |
| [16] | Liberti, L.; Lavor, C., Six mathematical gems from the history of distance geometry, Int Trans Oper Res, 23, 897-920 (2016) · Zbl 1362.51002 · doi:10.1111/itor.12170 |
| [17] | Liberti, L.; Lavor, C., Euclidean distance geometry: an introduction (2017), Berlin: Springer, Berlin · Zbl 1492.51002 · doi:10.1007/978-3-319-60792-4 |
| [18] | Liberti, L.; Lavor, C.; Migalas, A.; Pardalos, P., Open research areas in distance geometry, Open problems in optimization and data analysis, 183-223 (2018), Berlin: Springer, Berlin · Zbl 1420.51011 · doi:10.1007/978-3-319-99142-9_11 |
| [19] | Liberti, L.; Lavor, C.; Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem, Int Trans Oper Res, 15, 1-17 (2008) · Zbl 1136.92037 · doi:10.1111/j.1475-3995.2007.00622.x |
| [20] | Liberti, L.; Lavor, C.; Mucherino, A.; Maculan, N., Molecular distance geometry methods: from continuous to discrete, Int Trans Oper Res, 18, 33-51 (2010) · Zbl 1219.90177 · doi:10.1111/j.1475-3995.2009.00757.x |
| [21] | Liberti, L.; Lavor, C.; Alencar, J.; Resende, G., Counting the number of solutions of \(^K\) DMDGP instances, Lect Notes Comput Sci, 8085, 224-230 (2013) · Zbl 1405.05083 · doi:10.1007/978-3-642-40020-9_23 |
| [22] | Liberti, L.; Lavor, C.; Maculan, N.; Mucherino, A., Euclidean distance geometry and applications, SIAM Rev, 56, 3-69 (2014) · Zbl 1292.51010 · doi:10.1137/120875909 |
| [23] | Liberti, L.; Masson, B.; Lee, J.; Lavor, C.; Mucherino, A., On the number of realizations of certain Henneberg graphs arising in protein conformation, Discret Appl Math, 165, 213-232 (2014) · Zbl 1288.05121 · doi:10.1016/j.dam.2013.01.020 |
| [24] | Malliavin, T.; Mucherino, A.; Lavor, C.; Liberti, L., Systematic exploration of protein conformational space using a distance geometry approach, J Chem Inf Model, 59, 4486-4503 (2019) · doi:10.1021/acs.jcim.9b00215 |
| [25] | Marquezino, F.; Portugal, R.; Lavor, C., A primer on quantum computing (2019), Berlin: Springer, Berlin · Zbl 1430.81001 · doi:10.1007/978-3-030-19066-8 |
| [26] | Mucherino, A.; Lavor, C.; Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem, J Bioinform Comput Biol, 10, 1242009 (2012) · Zbl 1258.90100 · doi:10.1142/S0219720012420097 |
| [27] | Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Distance geometry: theory, methods, and applications (2013), Berlin: Springer, Berlin · Zbl 1405.51008 |
| [28] | Nucci, P.; Nogueira, L.; Lavor, C.; Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Solving the discretizable molecular distance geometry problem by multiple realization trees, Distance geometry: theory, methods, and applications, 161-176 (2013), New York: Springer, New York · Zbl 1366.92096 · doi:10.1007/978-1-4614-5128-0_9 |
| [29] | Wüthrich, K., Protein structure determination in solution by nuclear magnetic resonance spectroscopy, Science, 243, 45-50 (1989) · doi:10.1126/science.2911719 |
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.
