×
Lavor, Carlile; Souza, Michael; Carvalho, Luiz Mariano; Liberti, Leo

On the polynomiality of finding \(^K\text{DMDGP}\) re-orders. (English) Zbl 1419.05037

Discrete Appl. Math. 267, 190-194 (2019).
Summary: In [A. Cassioli et al., Discrete Appl. Math. 197, 27–41 (2015; Zbl 1321.05029)], the complexity of finding \(^K\text{DMDGP}\) re-orders was stated to be NP-complete by inclusion, which fails to provide a complete picture. In this paper we show that this problem is indeed NP-complete for \(K = 1\), but it is in P for each fixed \(K \geq 2\).

Cited in 10 Documents

MSC:

05B25 Combinatorial aspects of finite geometries
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C90 Applications of graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
92D20 Protein sequences, DNA sequences

Keywords:

distance geometry; discretizable molecular distance geometry problem; vertex orders

Citations:

Zbl 1321.05029
Cite Review PDF
Full Text: DOI

References:

[1] Alves, R.; Lavor, C., Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem, Adv. Appl. Clifford Algebr., 27, 439-452 (2017) · Zbl 1373.92148
[2] Alves, R.; Lavor, C.; Souza, C.; Souza, M., Clifford algebra and discretizable distance geometry, Math. Methods Appl. Sci., 41, 3999-4346 (2018) · Zbl 1397.92523
[3] 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
[4] 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
[5] Carvalho, R.; Lavor, C.; Protti, F., Extending the geometric build-up algorithm for the molecular distance geometry problem, Inform. Process. Lett., 108, 234-237 (2008) · Zbl 1191.68772
[6] 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 Bioinformatics, 16, 16-23 (2015)
[7] Cassioli, A.; Gunluk, O.; Lavor, C.; Liberti, L., Discretization vertex orders in distance geometry, Discrete Appl. Math., 197, 27-41 (2015) · Zbl 1321.05029
[8] Costa, V.; Mucherino, A.; Lavor, C.; Cassioli, A.; Carvalho, L.; Maculan, N., Discretization orders for protein side chains, J. Global Optim., 60, 333-349 (2014) · Zbl 1312.90069
[9] Crippen, G.; Havel, T., Distance Geometry and Molecular Conformation (1988), Wiley: Wiley New York · Zbl 1066.51500
[10] Dambrosio, C.; Ky, V.; Lavor, C.; Liberti, L.; Maculan, N., New error measures and methods for realizing protein graphs from distance data, Discrete Comput. Geom., 57, 371-418 (2017) · Zbl 1358.05085
[11] Donald, B., Algorithms in Structural Molecular Biology (2011), MIT Press: MIT Press Boston
[12] 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
[13] Gonçalves, D.; Mucherino, A., Discretization orders and efficient computation of Cartesian coordinates for distance geometry, Optim. Lett., 8, 2111-2125 (2014) · Zbl 1302.90177
[14] Gonçalves, D.; Mucherino, A.; Lavor, C.; Liberti, L., Recent advances on the interval distance geometry problem, J. Global Optim., 69, 525-545 (2017) · Zbl 1382.90084
[15] Lavor, C.; Alves, R., Oriented conformal geometric algebra and the molecular distance geometry problem, Adv. Appl. Clifford Algebr., 29, 1-19 (2019) · Zbl 1410.92086
[16] Lavor, C.; Lee, J.; Lee-St. John, A.; Liberti, L.; Mucherino, A.; Sviridenko, M., Discretization orders for distance geometry problems, Optim. Lett., 6, 783-796 (2012) · Zbl 1258.90096
[17] Lavor, C.; Liberti, L.; Donald, B.; Worley, B.; Bardiaux, B.; Malliavin, T.; Nilges, M., Minimal NMR distance information for rigidity of protein graphs, Discrete Appl. Math., 256, 91-104 (2019) · Zbl 1405.05178
[18] Lavor, C.; Liberti, L.; Lodwick, W.; Mendonça da Costa, T., (An Introduction to Distance Geometry Applied to Molecular Geometry. An Introduction to Distance Geometry Applied to Molecular Geometry, SpringerBriefs (2017), Springer: Springer New York) · Zbl 1403.92001
[19] Lavor, C.; Liberti, L.; Maculan, N.; Mucherino, A., The discretizable molecular distance geometry problem, Comput. Optim. Appl., 52, 115-146 (2012) · Zbl 1259.90153
[20] Lavor, C.; Liberti, L.; Maculan, N.; Mucherino, A., Recent advances on the discretizable molecular distance geometry problem, European J. Oper. Res., 219, 698-706 (2012) · Zbl 1253.05132
[21] Lavor, C.; Liberti, L.; Mucherino, A., The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances, J. Global Optim., 56, 855-871 (2013) · Zbl 1272.90074
[22] Liberti, L.; Lavor, C., Six mathematical gems from the history of distance geometry, Int. Trans. Oper. Res., 23, 897-920 (2016) · Zbl 1362.51002
[23] Liberti, L.; Lavor, C., Euclidean Distance Geometry: An Introduction (2017), Springer: Springer New York · Zbl 1492.51002
[24] Liberti, L.; Lavor, C.; Alencar, J.; Resende, G., (Counting the Number of Solutions of \({}^K\) DMDGP Instances. Counting the Number of Solutions of \({}^K\) DMDGP Instances, Lecture Notes in Computer Science, vol. 8085 (2013)), 224-230 · Zbl 1405.05083
[25] 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
[26] Liberti, L.; Lavor, C.; Maculan, N.; Mucherino, A., Euclidean distance geometry and applications, SIAM Rev., 56, 3-69 (2014) · Zbl 1292.51010
[27] 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
[28] Liberti, L.; Masson, B.; Lee, J.; Lavor, C.; Mucherino, A., On the number of realizations of certain Henneberg graphs arising in protein conformation, Discrete Appl. Math., 165, 213-232 (2014) · Zbl 1288.05121
[29] Mucherino, A.; Lavor, C.; Liberti, L., The discretizable distance geometry problem, Optim. Lett., 6, 1671-1686 (2012) · Zbl 1258.90100
[30] Mucherino, A.; Lavor, C.; Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem, J. Bioinform. Comput. Biol., 10, Article 1242009 pp. (2012), (1-15) · Zbl 1258.90100
[31] (Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Distance Geometry: Theory, Methods and Applications (2013), Springer: Springer New York) · Zbl 1256.51002
[32] Sallaume, S.; Martins, S.; Ochi, L.; Gramacho, W.; Lavor, C.; Liberti, L., A discrete search algorithm for finding the structure of protein backbones and side chains, Int. J. Bioinform. Res. Appl., 9, 261-270 (2013)
[33] Souza, M.; Lavor, C.; Muritiba, A.; Maculan, N., Solving the molecular distance geometry problem with inaccurate distance data, BMC Bioinformatics, 14, S71-S76 (2013)
[34] Souza, M.; Xavier, A.; Lavor, C.; Maculan, N., Hyperbolic smoothing and penalty techniques applied to molecular structure determination, Oper. Res. Lett., 39, 461-465 (2011) · Zbl 1235.90121
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.