Skip to main navigation Skip to search Skip to main content

A PTAS for the k-consensus structures problem under squared Euclidean distance

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

21 Downloads (CityUHK Scholars)

Abstract

In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of l points in a 3D space, where l is a fixed natural number. Two structural fragments f 1 and f 2 are equivalent if and only if f 1 = f 2 · R + under some rotation R and translation τ. We consider the distance between two structural fragments to be the sum of the squared Euclidean distance between all corresponding points of the structural fragments. Given a set of n structural fragments, we consider the problem of finding k (or fewer) structural fragments g 1,g 2,..., g k, so as to minimize the sum of the distances between each of f 1, f 2,..., fn to its nearest structural fragment in g 1,..., g k. In this paper we show a polynomial-time approximation scheme (PTAS) for the problem through a simple sampling strategy. © 2008 by the authors.
Original languageEnglish
Pages (from-to)43-51
JournalAlgorithms
Volume1
Issue number2
DOIs
Publication statusPublished - Dec 2008
Externally publishedYes

Research Keywords

  • Algorithm
  • Clustering 3D point sequences
  • Polynomial-time approximation scheme
  • Squared Euclidean distance

Publisher's Copyright Statement

  • This full text is made available under CC-BY 3.0. https://creativecommons.org/licenses/by/3.0/

Fingerprint

Dive into the research topics of 'A PTAS for the k-consensus structures problem under squared Euclidean distance'. Together they form a unique fingerprint.

Cite this