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

Abstract

In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of ℓ points in a 3D space, where ℓ is a fixed natural number. Two structural fragments f 1 and f 2 are equivalent iff under some rotation and translation . We consider the distance between two structural fragments to be the sum of the Euclidean squared 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, ..., f n to its nearest structural fragment in g 1, ..., g k . In this paper we show a PTAS for the problem through a simple sampling strategy. © 2008 Springer-Verlag Berlin Heidelberg.