Euclidean Distance Geometry And Applications

Euclidean distance geometry is the study of Euclidean geometry based on the concept of distance. This is useful in several applications where the input data consist of an incomplete set of distances and the output is a set of points in Euclidean space realizing those given distances. We survey the theory of Euclidean distance geometry and its most important applications, with special emphasis on molecular conformation problems. © 2014 Society for Industrial and Applied Mathematics.

Alexandrov, A., (1950) Convex Polyhedra, Gosudarstv. Izdat. Tekhn.-Theor. Lit., , Moscow

Alfakih, A., Khandani, A., Wolkowicz, H., Solving Euclidean distance matrix completion problems via semidefinite programming (1999) Comput. Optim. Appl., 12, pp. 13-30

Alves, R., Cassioli, A., Mucherino, A., Lavor, C., Liberti, L., Adaptive branching in iBP with Clifford algebra (2013) Proceedings of the Workshop on Distance Geometry and Applications, pp. 65-69. , A. Andrioni, C. Lavor, L. Liberti, A. Mucherino, N. Maculan, and R. Rodriguez, eds., Universidade Federal do Amazonas, Manaus

Anderson, B., Belhumeur, P., Eren, T., Goldenberg, D., Morse, S., Whiteley, W., Yang, R., Graphical properties of easily localizable sensor networks (2009) Wireless Networks, 15, pp. 177-191

Arabie, P., Was Euclid an unnecessarily sophisticated psychologist? (1991) Psychometrika, 56, pp. 567-587

Asimow, L., Roth, B., The rigidity of graphs (1978) Trans. Amer. Math. Soc., 245, pp. 279-289

Asimow, L., Roth, B., The rigidity of graphs II (1979) J. Math. Anal. Appl., 68, pp. 171-190

Aspnes, J., Eren, T., Goldenberg, D., Morse, S., Whiteley, W., Yang, R., Anderson, B., Belhumeur, P., A theory of network localization (2006) IEEE Trans. Mobile Comput., 5, pp. 1663-1678

Aspnes, J., Goldenberg, D., Yang, R., On the computational complexity of sensor network localization (2004) Algorithmic Aspects of Wireless Sensor Networks, pp. 32-44. , S. Nikoletseas and J. Rolim, eds., Lecture Notes in Comput. Sci. 3121, Springer, Berlin

Auslander, L., Mackenzie, R., (1977) Introduction to Differentiable Manifolds, , Dover, New York

Bahr, A., Leonard, J., Fallon, M., Cooperative localization for autonomous underwater vehicles (2009) Internat. J. Robotics Res., 28, pp. 714-728

Barvinok, A., Problems of distance geometry and convex properties of quadratic maps (1995) Discrete Comput. Geom., 13, pp. 189-202

Belkin, M., Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation (2003) Neural Comput., 15, pp. 1373-1396

Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A., Branching and bounds tightening techniques for non-convex MINLP (2009) Optim. Methods Softw., 24, pp. 597-634

Ben-Israel, A., Mond, B., What is invexity? (1986) J. Aust. Math. Soc. Ser. B, 28, pp. 1-9

Benedetti, R., Risler, J.-J., (1990) Real Algebraic and Semi-algebraic Sets, , Hermann, Paris

Berger, B., Kleinberg, J., Leighton, T., Reconstructing a three-dimensional model with arbitrary errors (1999) J. ACM, 46, pp. 212-235

Berman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., Bourne, P., The protein data bank (2000) Nucleic Acid Res., 28, pp. 235-242

Biggs, N., (1974) Algebraic Graph Theory, , Cambridge University Press, Cambridge, UK

Biggs, N., Lloyd, E., Wilson, R., (1976) Graph Theory 1736-1936, , Oxford University Press, Oxford

Biswas, P., (2007) Semidefinite Programming Approaches to Distance Geometry Problems, , Ph.D. thesis, Stanford University, Stanford, CA

Biswas, P., Lian, T., Wang, T., Ye, Y., Semidefinite programming based algorithms for sensor network localization (2006) ACM Trans. Sensor Networks, 2, pp. 188-220

Biswas, P., Liang, T.-C., Toh, K.-C., Wang, T.-C., Ye, Y., Semidefinite programming approaches for sensor network localization with noisy distance measurements (2006) IEEE Trans. Automation Sci. Engrg., 3, pp. 360-371

Biswas, P., Toh, K.-C., Ye, Y., A distributed SDP approach for large-scale noisy anchorfree graph realization with applications to molecular conformation (2008) SIAM J. Sci. Comput., 30, pp. 1251-1277

Biswas, P., Ye, Y., Semidefinite programming for ad hoc wireless sensor network localization (2004) Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN04), pp. 46-54. , ACM, New York

Biswas, P., Ye, Y., A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization (2006) Multiscale Optimization Methods and Applications, pp. 69-84. , W. Hager et al., eds., Nonconvex Optim. Appl. 82, Springer, New York

Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G., (1993) Oriented Matroids, , Cambridge University Press, Cambridge, UK

Blumenthal, L., (1953) Theory and Applications of Distance Geometry, , Oxford University Press, Oxford

Bohr, H., Brunak, S., (1996) Protein Folds: A Distance Based Approach, , CRC Press, Boca Raton, FL

Bokowski, J., Sturmfels, B., On the coordinatization of oriented matroids (1986) Discrete Comput. Geom., 1, pp. 293-306

Borg, I., Groenen, P., (2010) Modern Multidimensional Scaling, , 2nd ed., Springer, New York

Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V., (1994) Linear Matrix Inequalities in System and Control Theory, , SIAM, Philadelphia

Breu, H., Kirkpatrick, D., Unit disk graph recognition is NP-hard (1998) Comput. Geom., 9, pp. 3-24

Canny, J., Emiris, I., A subdivision-based algorithm for the sparse resultant (2000) J. ACM, 47, pp. 417-451

Carroll, J., Chang, J., Analysis of individual differences in multidimensional scaling via an n-way generalization of "eckart-Young" decomposition (1970) Psychometrika, 35, pp. 283-319

Carvalho, R., Lavor, C., Protti, F., Extending the geometric build-up algorithm for the molecular distance geometry problem (2008) Inform. Process. Lett., 108, pp. 234-237

Cauchy, A.-L., Sur les polygones et les polyèdres (1813) J. Ecole Polytechnique, 16, pp. 87-99

Cayley, A., A theorem in the geometry of position (1841) Cambridge Math. J., 2, pp. 267-271

Chen, H., (2012) Distance Geometry for Kissing Balls, , preprint, arXiv:1203.2131v2

Chevalley, C., (1955) The Construction and Study of Certain Important Algebras, , The Mathematical Society of Japan, Tokyo

Clark, B., Colburn, C., Johnson, D., Unit disk graphs (1990) Discrete Math., 86, pp. 165-177

Clore, G., Gronenborn, A., Determination of three-dimensional structures of proteins and nucleic acids in solution by nuclear magnetic resonance spectroscopy (1989) Critical Reviews in Biochemistry and Molecular Biology, 24, pp. 479-564

Connelly, R., A counterexample to the rigidity conjecture for polyhedra (1978) Inst. Hautes Études Sci. Publ. Math., 47, pp. 333-338

Connelly, R., On generic global rigidity (1991) Applied Geometry and Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4, pp. 147-155. , AMS, Providence, RI

Connelly, R., Generic global rigidity (2005) Discrete Comput. Geom., 33, pp. 549-563

Conway, J., Sloane, N., (1993) Sphere Packings, , Lattices and Groups, Springer, Berlin

Coope, I., Reliable computation of the points of intersection of n spheres in Rn (2000) Aust. N. Z. Indust. Appl. Math. J., 42, pp. C461-C477

Costa, V., Lavor, C., Mucherino, A., Cassioli, A., Carvalho, L., Maculan, N., Discretization orders for protein side chains J. Global Optim., , to appear

Cremona, L., (1872) Le Figure Reciproche Nella Statica Grafica, , G. Bernardoni, Milano

Cremona, L., (1874) Elementi di Calcolo Grafico, , Paravia, Torino

Crippen, G., Distance geometry for realistic molecular conformations (2013) Distance Geometry: Theory, Methods, and Applications, pp. 315-328. , A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, eds., Springer, New York

Crippen, G., Havel, T., (1988) Distance Geometry and Molecular Conformation, , Wiley, New York

Crum Brown, A., On the theory of isomeric compounds (1864) Trans. Roy. Soc. Edinburgh, 23, pp. 707-719

Cucuringu, M., Lipman, Y., Singer, A., Sensor network localization by eigenvector synchronization over the Euclidean group (2012) ACM Trans. Sensor Networks, 8, pp. 1-42

Cucuringu, M., Singer, A., Cowburn, D., Eigenvector synchronization, graph rigidity and the molecule problem (2012) Inform. Inference, 1, pp. 21-67

Dattorro, J., (2005) Convex Optimization and Euclidean Distance Geometry, , Mß oo, Palo Alto

Dattorro, J., Equality relating Euclidean distance cone to positive semidefinite cone (2008) Linear Algebra Appl., 428, pp. 2597-2600

De Leeuw, J., Heiser, W., Theory of multidimensional scaling (1982) Classification Pattern Recognition and Reduction of Dimensionality, pp. 285-316. , P. Krishnaiah and L. Kanal, eds., Handbook of Statist. 2, Elsevier

Demaine, E., Gomez-Martin, F., Meijer, H., Rappaport, D., Taslakian, P., Toussaint, G., Winograd, T., Wood, D., The distance geometry of music (2009) Comput. Geom., 42, pp. 429-454

Deza, M., Deza, E., (2009) Encyclopedia of Distances, , Springer, Berlin

Diestel, R., (2005) Graph Theory, , Springer, New York

Dirac, G., On rigid circuit graphs (1961) Abh. Math. Sem. Univ. Hamburg, 25, pp. 71-76

Doherty, L., Pister, K., El Ghaoui, L., Convex position estimation in wireless sensor networks (2001) Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 3 of INFOCOM, IEEE, pp. 1655-1663

Donald, B., (2011) Algorithms in Structural Molecular Biology, , MIT Press, Boston

Dong, Q., Wu, Z., A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances (2002) J. Global Optim., 22, pp. 365-375

Dong, Q., Wu, Z., A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data (2003) J. Global Optim., 26, pp. 321-333

Dress, A., Havel, T., Distance geometry and geometric algebra (1993) Found. Phys., 23, pp. 1357-1374

Dzemyda, G., Kurasova, O., Žilinskas, J., (2013) Multidimensional Data Visualiation: Methods and Applications, , Springer, New York

Dzhafarov, E., Colonius, H., Reconstructing distances among objects from their discriminability (2006) Psychometrika, 71, pp. 365-386

Eaton, J., (2002) GNU Octave Manual, , Network Theory Limited

Eckart, C., Young, G., The approximation of one matrix by another of lower rank (1936) Psychometrika, 1, pp. 211-218

Emiris, I., Mourrain, B., Computer algebra methods for studying and computing molecular conformations (1999) Algorithmica, 25, pp. 372-402

Eren, T., Goldenberg, D., Whiteley, W., Yang, Y., Morse, A., Anderson, B., Belhumeur, P., Rigidity, computation, and randomization in network localization (2004) IEEE Infocom Proc., 4, pp. 2673-2684

Everitt, B., Rabe-Hesketh, S., (1997) The Analysis of Proximity Data, , Arnold, London

Feferman, S., Dawson, J., Kleene, S., Moore, G., Solovay, R., Van Heijenoort, J., (1986) Kurt Gödel: Collected Works, 1. , Oxford University Press, Oxford

Fekete, Z., Jordán, T., Uniquely localizable networks with few anchors (2006) Algorithmic Aspects of Wireless Sensor Networks, pp. 176-183. , S. Nikoletseas and J. Rolim, eds., Lecture Notes in Comput. Sci. 4240, Springer, Berlin

Forman, G., Zahorjan, J., The challenges of mobile computing (1994) IEEE Comput., 27, pp. 38-47

Fudos, I., Hoffmann, C., A graph-constructive approach to solving systems of geometric constraints (1997) ACM Trans. Graphics, 16, pp. 179-216

Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NPCompleteness, , Freeman and Company, New York

Gibson, K., Scheraga, H., Energy minimization of rigid-geometry polypeptides with exactly closed disulfide loops (1997) J. Comput. Chem., 18, pp. 403-415

Gluck, H., Almost all simply connected closed surfaces are rigid (1975) Geometric Topology, pp. 225-239. , A. Dold and B. Eckmann, eds., Lecture Notes in Math. 438, Springer, Berlin

Glunt, W., Hayden, T.L., Hong, S., Wells, J., An alternating projection algorithm for computing the nearest Euclidean distance matrix (1990) SIAM J. Matrix Anal. Appl., 11, pp. 589-600

Gortler, S., Healy, A., Thurston, D., Characterizing generic global rigidity (2010) Amer. J. Math., 132, pp. 897-939

Gower, J., Some distance properties of latent root and vector methods in multivariate analysis (1966) Biometrika, 53, pp. 325-338

Gower, J., Euclidean distance geometry (1982) Math. Sci., 7, pp. 1-14

Gramacho, W., Mucherino, A., Lavor, C., Maculan, N., A parallel BP algorithm for the discretizable distance geometry problem (2012) Proceedings of the Workshop on Parallel Computing and Optimization, Shanghai, pp. 1756-1762. , IEEE

Graver, J., Rigidity matroids (1991) SIAM J. Discrete Math., 4, pp. 355-368

Graver, J., Servatius, B., Servatius, H., (1993) Combinatorial Rigidity, , AMS, Providence, RI

Grippo, L., Sciandrone, M., On the convergence of the block nonlinear Gauss-Seidel method under convex constraints (2000) Oper. Res. Lett., 26, pp. 127-136

Grone, R., Johnson, C., De Sá, E., Wolkowicz, H., Positive definite completions of partial Hermitian matrices (1984) Linear Algebra Appl., 58, pp. 109-124

Grosso, A., Locatelli, M., Schoen, F., Solving molecular distance geometry problems by global optimization algorithms (2009) Comput. Optim. Appl., 43, pp. 23-27

Havel, T., Metric matrix embedding in protein structure calculations (2003) Magnetic Resonance Chem., 41, pp. 537-550

Havel, T., Kuntz, I., Crippen, G., The theory and practice of distance geometry (1983) Bull. Math. Biol., 45, pp. 665-720

Hendrickson, B., Conditions for unique graph realizations (1992) SIAM J. Comput., 21, pp. 65-84

Hendrickson, B., The molecule problem: Exploiting structure in global optimization (1995) SIAM J. Optim., 5, pp. 835-857

Henneberg, L., (1886) Statik der Starren Systeme, , Bergstræsser, Darmstadt

Henneberg, L., (1911) Die Graphische Statik der Starren Systeme, , Teubner, Leipzig

Hoai An, L., Solving large scale molecular distance geometry problems by a smoothing technique via the Gaussian transform and D.C. Programming (2003) J. Global Optim., 27, pp. 375-397

Hoai An, L.T., Dinh Tao, P., Large-scale molecular optimization from distance matrices by a d.c. Optimization approach (2003) SIAM J. Optim., 14, pp. 77-114

Huang, H.-X., Liang, Z.-A., Pardalos, P., Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems (2003) J. Global Optim., 25, pp. 3-21

Hunt, K., (1990) Kinematic Geometry of Mechanisms, , Oxford University Press, Oxford

Izrailev, S., Zhu, F., Agrafiotis, D., A distance geometry heuristic for expanding the range of geometries sampled during conformational search (2006) J. Comput. Chem., 26, pp. 1962-1969

Jackson, B., Jordán, T., Connected rigidity matroids and unique realization of graphs (2005) J. Combin. Theory Ser. B, 94, pp. 1-29

Jackson, B., Jordán, T., On the rigidity of molecular graphs (2008) Combinatorica, 28, pp. 645-658

Jackson, B., Jordán, T., Graph theoretic techniques in the analysis of uniquely localizable sensor networks (2009) Localization Algorithms and Strategies for Wireless Sensor Networks: Monitoring and Surveillance Techniques for Target Tracking, pp. 146-173. , G. Mao and B. Fidan, eds., IGI Global

Johnson, C., Kroschel, B., Wolkowicz, H., An interior-point method for approximate positive semidefinite completions (1998) Comput. Optim. Appl., 9, pp. 175-190

Jolliffe, I., (2010) Principal Component Analysis, , 2nd ed., Springer, Berlin

Kostrowicki, J., Piela, L., Diffusion equation method of global minimization: Performance for standard test functions (1991) J. Optim. Theory Appl., 69, pp. 269-284

Krishnaiah, P., Kanal, L., (1982) Theory of Multidimensional Scaling, 2. , North-Holland

Krislock, N., (2010) Semidefinite Facial Reduction for Low-Rank Euclidean Distance Matrix Completion, , Ph.D. thesis, University of Waterloo

Krislock, N., Wolkowicz, H., Explicit sensor network localization using semidefinite representations and facial reductions (2010) SIAM J. Optim., 20, pp. 2679-2708

Kruskal, J., Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis (1964) Psychometrika, 29, pp. 1-27

Kruskal, J., Nonmetric multidimensional scaling: A numerical method (1964) Psychometrika, 29, pp. 115-129

Kucherenko, S., Belotti, P., Liberti, L., Maculan, N., New formulations for the kissing number problem (2007) Discrete Appl. Math., 155, pp. 1837-1841

Kucherenko, S., Sytsko, Y., Application of deterministic low-discrepancy sequences in global optimization (2004) Comput. Optim. Appl., 30, pp. 297-318

Laman, G., On graphs and rigidity of plane skeletal structures (1970) J. Engrg. Math., 4, pp. 331-340

Laurent, M., Cuts, matrix completions and graph rigidity (1997) Math. Program., 79, pp. 255-283

Laurent, M., Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems (2000) SIAM J. Matrix Anal. Appl., 22, pp. 874-894

Laurent, M., Matrix completion problems (2009) Encyclopedia of Optimization, pp. 1967-1975. , 2nd ed., C. Floudas and P. Pardalos, eds., Springer, New York

Lavor, C., On generating instances for the molecular distance geometry problem (2006) Global Optimization: From Theory to Implementation, pp. 405-414. , L. Liberti and N.Maculan, eds., Springer, Berlin

Lavor, C., Lee, J., Lee-St. John, A., Liberti, L., Mucherino, A., Sviridenko, M., Discretization orders for distance geometry problems (2012) Optim. Lett., 6, pp. 783-796

Lavor, C., Liberti, L., Maculan, N., Grover's algorithm applied to the molecular distance geometry problem (2005) Proceedings of the 7th Brazilian Congress of Neural Networks, Natal, Brazil

Lavor, C., Liberti, L., Maculan, N., Computational experience with the molecular distance geometry problem (2006) Global Optimization: Scientific and Engineering Case Studies, pp. 213-225. , J. Pintér, ed., Springer, Berlin

Lavor, C., Liberti, L., Maculan, N., (2006) The Discretizable Molecular Distance Geometry Problem, , preprint, arXiv:q-bio/0608012

Lavor, C., Liberti, L., Maculan, N., Molecular distance geometry problem (2009) Encyclopedia of Optimization, pp. 2305-2311. , 2nd ed., C. Floudas and P. Pardalos, eds., Springer, New York

Lavor, C., Liberti, L., Maculan, N., A note on "a Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem" (2011) Internat. Trans. Oper. Res., 18, pp. 751-752

Lavor, C., Liberti, L., Maculan, N., Mucherino, A., The discretizable molecular distance geometry problem (2012) Comput. Optim. Appl., 52, pp. 115-146

Lavor, C., Liberti, L., Maculan, N., Mucherino, A., Recent advances on the discretizable molecular distance geometry problem (2012) European J. Oper. Res., 219, pp. 698-706

Lavor, C., Liberti, L., Mucherino, A., The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances (2013) J. Global Optim., 56, pp. 855-871

Lavor, C., Liberti, L., Mucherino, A., Maculan, N., On a discretizable subclass of instances of the molecular distance geometry problem (2009) Proceedings of the 24th Annual ACM Symposium on Applied Computing, pp. 804-805. , D. Shin, ed., ACM, New York

Lavor, C., Mucherino, A., Liberti, L., Maculan, N., An artificial backbone of hydrogens for finding the conformation of protein molecules (2009) Proceedings of the Computational Structural Bioinformatics Workshop, pp. 152-155. , Washington D.C., IEEE

Lavor, C., Mucherino, A., Liberti, L., Maculan, N., Computing artificial backbones of hydrogen atoms in order to discover protein backbones (2009) Proceedings of the International Multiconference on Computer Science and Information Technology, Mragowo, Poland, IEEE, pp. 751-756

Lavor, C., Mucherino, A., Liberti, L., Maculan, N., Discrete approaches for solving molecular distance geometry problems using NMR data (2010) Internat. J. Comput. Biosci., 1, pp. 88-94

Lavor, C., Mucherino, A., Liberti, L., Maculan, N., On the solution of molecular distance geometry problems with interval data (2010) Proceedings of the International Workshop on Computational Proteomics, Hong Kong, IEEE, pp. 77-82

Lavor, C., Mucherino, A., Liberti, L., Maculan, N., On the computation of protein backbones by using artificial backbones of hydrogens (2011) J. Global Optim., 50, pp. 329-344

Lavor, C., Mucherino, A., Liberti, L., Maculan, N., Finding low-energy homopolymer conformations by a discrete approach (2012) Proceedings of the Global Optimization Workshop, , D. Aloise, P. Hansen, and C. Rocha, eds., Universidade Federal do Rio Grande do Norte, Natal

Le Grand, S., Elofsson, A., Eisenberg, D., The effect of distance-cutoff on the performance of the distance matrix error when used as a potential function to drive conformational search (1996) Protein Folds: A Distance Based Approach, pp. 105-113. , H. Bohr and S. Brunak, eds., CRC Press, Boca Raton, FL

Lee, J., Verleysen, M., (2010) Nonlinear Dimensionality Reduction, , Springer, Berlin

Leung, N.-H.Z., Toh, K.-C., An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization (2009) SIAM J. Sci. Comput., 31, pp. 4351-4372

Liberti, L., (2004) Reformulation and Convex Relaxation Techniques for Global Optimization, , Ph.D. thesis, Imperial College London, London

Liberti, L., Reformulations in mathematical programming: Definitions and systematics (2009) RAIRO Oper. Res., 43, pp. 55-85

Liberti, L., Dražic, M., Variable neighbourhood search for the global optimization of constrained NLPs (2005) Proceedings of GO Workshop, Almeria, Spain

Liberti, L., Kucherenko, S., (2004) Comparison of Deterministic and Stochastic Approaches to Global Optimization, , Tech. Rep. 2004.25, DEI, Politecnico di Milano

Liberti, L., Lavor, C., On a relationship between graph realizability and distance matrix completion (2013) Optimization Theory, Decision Making, and Operational Research Applications, pp. 39-48. , A. Migdalas, A. Sifaleras, C. Georgiadis, J. Papathanaiou, and E. Stiakakis, eds., Proc. Math. Statist. 31, Springer, Berlin

Liberti, L., Lavor, C., Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem (2008) Internat. Trans. Oper. Res., 15, pp. 1-17

Liberti, L., Lavor, C., Maculan, N., Marinelli, F., Double variable neighbourhood search with smoothing for the molecular distance geometry problem (2009) J. Global Optim., 43, pp. 207-218

Liberti, L., Lavor, C., Mucherino, A., The discretizable molecular distance geometry problem seems easier on proteins (2013) Distance Geometry: Theory, Methods, and Applications, pp. 47-60. , A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, eds., Springer, New York

Liberti, L., Lavor, C., Mucherino, A., Maculan, N., Molecular distance geometry methods: From continuous to discrete (2010) Internat. Trans. Oper. Res., 18, pp. 33-51

Liberti, L., Masson, B., Lavor, C., Lee, J., Mucherino, A., (2010) On the Number of Solutions of the Discretizable Molecular Distance Geometry Problem, , preprint, arXiv:1010.1834v1 [cs.DM]

Liberti, L., Masson, B., Lavor, C., Mucherino, A., Branch-and-prune trees with bounded width (2011) Proceedings of Cologne/Twente Workshop, , G. Nicosia and A. Pacifici, eds., Università di Roma 2-Tor Vergata, Rome

Liberti, L., Masson, B., Lee, J., Lavor, C., Mucherino, A., On the number of solutions of the discretizable molecular distance geometry problem (2011) Combinatorial Optimization, Constraints and Applications (COCOA11), Lecture Notes in Comput. Sci. 6831, pp. 322-342. , Springer, New York

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., , to appear

Liberti, L., Tsiakis, P., Keeping, B., Pantelides, C., (2001) OoOPS, , Centre for Process Systems Engineering, Chemical Engineering Department, Imperial College London, London

Lovász, L., Yemini, Y., On generic rigidity in the plane (1982) SIAM J. Algebraic Discrete Methods, 3, pp. 91-98

Ma, Y., Fu, Y., (2012) Manifold Learning Theory and Applications, , CRC Press, Boca Raton, FL

Malliavin, T., Mucherino, A., Nilges, M., Distance geometry in structural biology (2013) Distance Geometry: Theory, Methods, and Applications, pp. 329-350. , A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, eds., Springer, New York

Man-Cho So, A., Ye, Y., Theory of semidefinite programming for sensor network localization (2007) Math. Program. Ser. B, 109, pp. 367-384

Manocha, D., Canny, J., Efficient inverse kinematics for general 6R manipulators (1994) IEEE Trans. Robotics Automation, 10, pp. 648-657

Maxwell, J., On reciprocal figures and diagrams of forces (1864) Philos. Mag., 27, pp. 250-261

Maxwell, J., On the calculation of the equilibrium and stiffness of frames (1864) Philos. Mag., 27, pp. 294-299

Menger, K., Untersuchungen über allgemeine Metrik (1928) Math. Ann., 100, pp. 75-163

Menger, K., New foundation of Euclidean geometry (1931) Amer. J. Math., 53, pp. 721-745

Mishra, B., Computational real algebraic geometry (2004) Handbook of Discrete and Computational Geometry, pp. 743-764. , 2nd ed., J. Goodman and J. O'Rourke, eds., CRC Press, Boca Raton, FL

Moré, J., Wu, Z., Global continuation for distance geometry problems (1997) SIAM J. Optim., 7, pp. 814-836

Moré, J., Wu, Z., Distance geometry optimization for protein structures (1999) J. Global Optim., 15, pp. 219-234

Mucherino, A., Lavor, C., The branch and prune algorithm for the molecular distance geometry problem with inexact distances (2009) Proceedings of the International Conference on Computational Biology, 58, pp. 349-353. , World Academy of Science, Engineering and Technology

Mucherino, A., Lavor, C., Liberti, L., A symmetry-driven BP algorithm for the discretizable molecular distance geometry problem (2011) Proceedings of Computational Structural Bioinformatics Workshop, IEEE, pp. 390-395

Mucherino, A., Lavor, C., Liberti, L., The discretizable distance geometry problem (2012) Optim. Lett., 6, pp. 1671-1686

Mucherino, A., Lavor, C., Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem (2012) J. Bioinform. Comput. Biol., 10, pp. 289-302

Mucherino, A., Lavor, C., Liberti, L., Maculan, N., Strategies for solving distance geometry problems with inexact distances by discrete approaches (2010) Proceedings of the Toulouse Global Optimization Workshop, pp. 93-96. , S. Cafieri, E. Hendrix, L. Liberti, and F. Messine, eds., Toulouse

Mucherino, A., Lavor, C., Liberti, L., Maculan, N., On the discretization of distance geometry problems (2012) Proceedings of the Conference on Mathematics of Distances and Applications, pp. 160-168. , M. Deza, M. Petitjean, and K. Markov, eds., ITHEA, Varna

Mucherino, A., Lavor, C., Liberti, L., Maculan, N., (2013) Distance Geometry: Theory, Methods, and Applications, , Springer, New York

Mucherino, A., Lavor, C., Liberti, L., Talbi, E.-G., A parallel version of the branch & prune algorithm for the molecular distance geometry problem (2010) ACS/IEEE International Conference on Computer Systems and Applications (AICCSA10), Hammamet, Tunisia, IEEE, pp. 1-6

Mucherino, A., Lavor, C., Maculan, N., The molecular distance geometry problem applied to protein conformations (2009) Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 337-340. , S. Cafieri, A. Mucherino, G. Nannicini, F. Tarissan, and L. Liberti, eds., École Polytechnique, Paris

Mucherino, A., Lavor, C., Malliavin, T., Liberti, L., Nilges, M., Maculan, N., Influence of pruning devices on the solution of molecular distance geometry problems (2011) Experimental Algorithms, pp. 206-217. , P. Pardalos and S. Rebennack, eds., Lecture Notes in Comput. Sci. 6630, Springer, Berlin

Mucherino, A., Liberti, L., Lavor, C., MD-jeep: An implementation of a branch-andprune algorithm for distance geometry problems (2010) Mathematical Software, pp. 186-197. , K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, eds., Lecture Notes in Comput. Sci. 6327, Springer, New York

Mucherino, A., Liberti, L., Lavor, C., Maculan, N., Comparisons between an exact and a metaheuristic algorithm for the molecular distance geometry problem (2009) Proceedings of the Genetic and Evolutionary Computation Conference, pp. 333-340. , F. Rothlauf, ed., Montreal, ACM, New York

Nielsen, J., Roth, B., On the kinematic analysis of robotic mechanisms (1999) Internat. J. Robotics Res., 18, pp. 1147-1160

Nilges, M., Macias, M., O'Donoghue, S., Oschkinat, H., Automated NOESY interpretation with ambiguous distance restraints: The refined NMR solution structure of the Pleckstrin homology domain from β-spectrin (1997) J. Molecular Biol., 269, pp. 408-422

Nucci, P., Nogueira, L., Lavor, C., Solving the discretizable molecular distance geometry problem by multiple realization trees (2013) Distance Geometry: Theory, Methods, and Applications, pp. 161-176. , A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, eds., Springer, New York

Petitjean, M., Sphere unions and intersections and some of their applications in molecular modeling (2013) Distance Geometry: Theory, Methods, and Applications, pp. 61-83. , A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, eds., Springer, New York

Pong, T., Tseng, P., (Robust) edge-based semidefinite programming relaxation of sensor network localization (2011) Math. Program. Ser. A, 130, pp. 321-358

Porta, J., Ros, L., Thomas, F., Inverse kinematics by distance matrix completion (2005) Proceedings of the 12th International Workshop on Computational Kinematics, pp. 1-9

Porta, J., Ros, L., Thomas, F., Torras, C., A branch-and-prune solver for distance constraints (2005) IEEE Trans. Robotics, 21, pp. 176-187

Rao, R., Asaithambi, A., Agrawal, S., Inverse kinematic solution of robot manipulators using interval analysis (1998) ASME J. Mech. Design, 120, pp. 147-150

Reams, R., Chatham, G., Glunt, W., McDonald, D., Hayden, T., Determining protein structure using the distance geometry program APA (1999) Computers and Chemistry, 23, pp. 153-163

Recski, A., A network theory approach to the rigidity of skeletal structures. Part 2. Laman's theorem and topological formulae (1984) Discrete Appl. Math., 8, pp. 63-68

Rojas, N., (1989) Distance-Based Formulations for the Position Analysis of Kinematic Chains, , Ph.D. thesis, Universitat Politecnica de Catalunya

Rose, D.J., Tarjan, R.E., Lueker, G.S., Algorithmic aspects of vertex elimination on graphs (1976) SIAM J. Comput., 5, pp. 266-283

Roth, B., Rigid and flexible frameworks (1981) Amer. Math. Monthly, 88, pp. 6-21

Roth, B., Freudenstein, F., Synthesis of path-generating mechanisms by numerical methods (1963) J. Engrg. Industry, 85, pp. 298-307

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 (2013) Internat. J. Bioinform. Res. Appl., 9, pp. 261-270

Santana, R., Larrañaga, P., Lozano, J., Side chain placement using estimation of distribution algorithms (2007) Art. Intell. Med., 39, pp. 49-63

Saviotti, C., Nouvelles méthodes pour le calcul des travures réticulaires (1885) Appendix to L. Cremona, "les Figures Réciproques en Statique Graphique", pp. 37-100. , Gauthier-Villars, Paris

Saviotti, C., (1888) La Statica Grafica: Lezioni, , U. Hoepli, Milano

Savvides, A., Han, C.-C., Strivastava, M., Dynamic fine-grained localization in ad-hoc networks of sensors (2001) Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, MobiCom '01, ACM, pp. 166-179. , New York

Saxe, J., Embeddability of weighted graphs in k-space is strongly NP-hard (1979) Proceedings of the 17th Allerton Conference in Communications, Control and Computing, pp. 480-489

Schlick, T., (2002) Molecular Modelling and Simulation: An Interdisciplinary Guide, , Springer, New York

Schoenberg, I., 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" (1935) Ann. of Math., 36, pp. 724-732

Servatius, B., Servatius, H., Generic and abstract rigidity (2002) Rigidity Theory and Applications, pp. 1-19. , M. Thorpe and P. Duxbury, eds., Fundamental Materials Research, Springer, New York

Shepard, R., The analysis of proximities: Multidimensional scaling with an unknown distance function, Part i (1962) Psychometrika, 27, pp. 125-140

Shepard, R., The analysis of proximities: Multidimensional scaling with an unknown distance function, Part II (1962) Psychometrika, 27, pp. 219-246

Shepard, R., Metric structures in ordinal data (1966) J. Math. Psych., 3, pp. 287-315

Singer, A., Angular synchronization by eigenvectors and semidefinite programming (2011) Appl. Comput. Harmon. Anal., 30, pp. 20-36

Singer, A., Cucuringu, M., Uniqueness of low-rank matrix completion by rigidity theory (2010) SIAM J. Matrix Anal. Appl., 31, pp. 1621-1641

Singer, A., Zhao, Z., Shkolnisky, Y., Hadani, R., Viewing angle classification of cryoelectron microscopy images using eigenvectors (2011) SIAM J. Imaging Sci., 4, pp. 723-759

Sippl, M., Scheraga, H., Solution of the embedding problem and decomposition of symmetric matrices (1985) Proc.

Materias

Mostrar el registro completo del ítem