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

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 ₁ and f ₂ are equivalent if and only if f ₁ = f ₂ · 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 ₁,g ₂,..., g _k, so as to minimize the sum of the distances between each of f ₁, f ₂,..., fn to its nearest structural fragment in g ₁,..., 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.