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 language | English |
|---|---|
| Pages (from-to) | 43-51 |
| Journal | Algorithms |
| Volume | 1 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - Dec 2008 |
| Externally published | Yes |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver