文章基本信息

标题：The Isomap Algorithm in Distance Geometry
本地全文：下载
作者：Leo Liberti ; Claudia D'Ambrosio
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：75
页码：5:1-5:13
DOI：10.4230/LIPIcs.SEA.2017.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：distance geometry problem; protein conformation; heuristics