Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

A New Approach to the Discretization of Multidimensional Scaling

, , ,

DOI: http://dx.doi.org/10.15439/2016F213

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 591–599 ()

Full text

Abstract. Given a set of points in a Euclidean space having dimension K > 0, we are interested in the problem of finding a realization of the same set in a Euclidean space having a lower dimension. In most situations, it is not possible to preserve all available interpoint distances in the new space, so that the best possible realization, which gives the minimal error on the distances, needs to be searched. This problem is known in the scientific literature as the Multidimensional Scaling (MDS). We propose a new methodology to discretize the search space of MDS instances, with the aim of performing an efficient enumeration of their solution sets. Some preliminary computational experiments on a set of artificially generated instances are presented. We conclude our paper with some future research directions.

References

  1. J. Alencar, C. Lavor, T. O. Bonates, A Combinatorial Approach to Multidimensional Scaling, IEEE conference proceedings, 2014 IEEE International Congress on Big Data, 562–569, 2014.
  2. P. Biswas, T. Lian, T. Wang, Y. Ye, Semidefinite Programming based Algorithms for Sensor Network Localization, ACM Transactions in Sensor Networks 2, 188–220, 2006.
  3. I. Borg, P.J.F. Groenen, Modern Multidimensional Scaling: Theory and Applications, Springer Series in Statistics, Second Edition, 355 pages, 2005.
  4. A. Cassioli, O. Günlük, C. Lavor, L. Liberti, Discretization Vertex Orders in Distance Geometry, Discrete Applied Mathematics 197, 27–41, 2015.
  5. Y. Ding, N. Krislock, J. Qian, H. Wolkowicz, Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization, Optimization and Engineering 11(1), 45–66, 2010.
  6. M. J. Duan, M.H. Li, L. Han, S.H. Huo, Euclidean Sections of Protein Conformation Space and their Implications in Dimensionality Reduction, Proteins 82, 2585–2596, 2014.
  7. A. E. Garcia, Large-Amplitude Nonlinear Motions in Proteins, Physical Review Letters 68, 2696–2699, 1992.
  8. D. S. Gonçalves, A. Mucherino, Discretization Orders and Efficient Computation of Cartesian Coordinates for Distance Geometry, Optimization Letters 8(7), 2111–2125, 2014.
  9. D. S. Gonçalves, A. Mucherino, Optimal Partial Discretization Orders for Discretizable Distance Geometry, International Transactions in Operational Research 23(5), 947–967, 2016.
  10. W. Gramacho, D.S. Gonçalves, A. Mucherino, N. Maculan, A new Algorithm to Finding Discretizable Orderings for Distance Geometry, Proceedings of Distance Geometry and Applications (DGA13), Manaus, Amazonas, Brazil, 149–152, 2013.
  11. M. C. Hout, M. H. Papesh, S. D. Goldinger, Multidimensional Scaling, Wiley Interdisciplinary Reviews: Cognitive Science 4(1), 93–103, 2013.
  12. A. Kitao, F. Hirata, N. Go, The Effects of Solvent on the Conformation and the Collective Motions of Protein − Normal Mode Analysis and Molecular-Dynamics Simulations of Melittin in Water and in Vacuum, Journal of Chemical Physics 158, 447–472, 1991.
  13. C. Lavor, J. Lee, A. Lee-St.John, L. Liberti, A. Mucherino, M. Sviridenko, Discretization Orders for Distance Geometry Problems, Optimization Letters 6(4), 783–796, 2012.
  14. C. Lavor, L. Liberti, N. Maculan, A. Mucherino, The Discretizable Molecular Distance Geometry Problem, Computational Optimization and Applications 52, 115–146, 2012.
  15. C. Lavor, L. Liberti, A. Mucherino, The interval Branch-and-Prune Algorithm for the Discretizable Molecular Distance Geometry Problem with Inexact Distances, Journal of Global Optimization 56(3), 855–871, 2013.
  16. L. Liberti, C. Lavor, N. Maculan, A. Mucherino, Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3–69, 2014.
  17. L. Liberti, C. Lavor, A. Mucherino, N. Maculan, Molecular Distance Geometry Methods: from Continuous to Discrete, International Transactions in Operational Research 18(1), 33–51, 2011.
  18. L. Liberti, B. Masson, J. Lee, C. Lavor, A. Mucherino, On the Number of Realizations of Certain Henneberg Graphs arising in Protein Conformation, Discrete Applied Mathematics 165, 213–232, 2014.
  19. T.E. Malliavin, A. Mucherino, M. Nilges, Distance Geometry in Structural Biology: New Perspectives. In: “Distance Geometry: Theory, Methods and Applications”, A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.), Springer, 329–350, 2013.
  20. A. Mucherino, On the Identification of Discretization Orders for Distance Geometry with Intervals, Lecture Notes in Computer Science 8085, F. Nielsen and F. Barbaresco (Eds.), Proceedings of Geometric Science of Information (GSI13), Paris, France, 231–238, 2013.
  21. A. Mucherino, A Pseudo de Bruijn Graph Representation for Discretization Orders for Distance Geometry, Lecture Notes in Computer Science 9043, Lecture Notes in Bioinformatics series, F. Ortuño and I. Rojas (Eds.), Proceedings of the 3rd International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO15), Granada, Spain, 514–523, 2015.
  22. A. Mucherino, Optimal Discretization Orders for Distance Geometry: a Theoretical Standpoint, Lecture Notes in Computer Science 9374, Proceedings of the 10 th International Conference on Large-Scale Scientific Computations (LSSC15), Sozopol, Bulgaria, 234–242, 2015.
  23. J. Moré, Z. Wu, Distance Geometry Optimization for Protein Structures, Journal on Global Optimization 15, 219–234, 1999.
  24. A. Mucherino, C. Lavor, L. Liberti, The Discretizable Distance Geometry Problem, Optimization Letters 6(8), 1671–1686, 2012.
  25. A. Mucherino, L. Liberti, C. Lavor, MD-jeep: an Implementation of a Branch & Prune Algorithm for Distance Geometry Problems, Lectures Notes in Computer Science 6327, K. Fukuda et al. (Eds.), Proceedings of the Third International Congress on Mathematical Software (ICMS10), Kobe, Japan, 186–197, 2010.
  26. K. Pearson, On Lines and Planes of Closest Fit to Systems of Points in Space, Philosophical Magazine 2, 559–572, 1901.
  27. J. Saxe, Embeddability of Weighted Graphs in k-Space is Strongly NP-hard, Proceedings of 17th Allerton Conference in Communications, Control and Computing, 480–489, 1979.
  28. J. B. Tenenbaum, V. de Silva, J. C. Langford, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290, 290(5500), 2319-23, 2000.
  29. W. S. Torgerson, Multidimensional Scaling: I. Theory and Method, Psychometrika 17(4), 401–419, 1952.