License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.5
URN: urn:nbn:de:0030-drops-76079
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7607/
Go to the corresponding LIPIcs Volume Portal

Liberti, Leo ; D'Ambrosio, Claudia

The Isomap Algorithm in Distance Geometry

pdf-format:
LIPIcs-SEA-2017-5.pdf (1 MB)

Abstract

The fundamental problem of distance geometry consists in finding a realization of a given weighted graph in a Euclidean space of given dimension, in such a way that vertices are realized as points and edges as straight segments having the same lengths as their given weights. This problem arises in structural proteomics, wireless sensor networks, and clock synchronization protocols to name a few applications. The well-known Isomap method is a dimensionality reduction heuristic which projects finite but high dimensional metric spaces into the "most significant" lower dimensional ones, where significance is measured by the magnitude of the corresponding eigenvalues. We start from a simple observation, namely that Isomap can also be used to provide approximate realizations of weighted graphs very efficiently, and then derive and benchmark six new heuristics.

BibTeX - Entry

@InProceedings{liberti_et_al:LIPIcs:2017:7607,
  author =	{Leo Liberti and Claudia D'Ambrosio},
  title =	{{The Isomap Algorithm in Distance Geometry}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7607},
  URN =		{urn:nbn:de:0030-drops-76079},
  doi =		{10.4230/LIPIcs.SEA.2017.5},
  annote =	{Keywords: distance geometry problem, protein conformation, heuristics}
}

Keywords: distance geometry problem, protein conformation, heuristics
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI