Constant time approximation scheme for largest well predicted subset

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)352-367
Journal / PublicationJournal of Combinatorial Optimization
Volume25
Issue number3
Online published8 Dec 2010
Publication statusPublished - Apr 2013

Abstract

The largest well predicted subset problem is formulated for comparison of two predicted 3D protein structures from the same sequence. A 3D protein structure is represented by an ordered point set A={a1,..., an}, where each ai is a point in 3D space. Given two ordered point sets A={a1,..., an} and B={b1, b2,...bn} containing n points, and a threshold d, the largest well predicted subset problem is to find the rigid body transformation T for a largest subset Bopt of B such that the distance between ai and T(bi ) is at most d for every bi in Bopt. A meaningful prediction requires that the size of Bopt is at least αn for some constant α (Li et al. in CPM 2008, 2008). We use LWPS(A, B, d, α) to denote the largest well predicted subset problem with meaningful prediction. An (1+δ1, 1-δ2)-approximation for LWPS(A, B, d, α) is to find a transformation T to bring a subset B'⊂B of size at least (1-δ2)|Bopt| such that for each biB′, the Euclidean distance between the two points distance (ai, T(bi)) ≤ (1+δ1)d. We develop a constant time (1+δ1, 1-δ2)-approximation algorithm for LWPS(A, B, d, α) for arbitrary positive constants δ1 and δ2. To our knowledge, this is the first constant time algorithm in this area. Li et al. (CPM 2008, 2008) showed an O(n(log n)2/δ15) time randomized (1+δ1)-distance approximation algorithm for the largest well predicted subset problem under meaningful prediction. We also study a closely related problem, the bottleneck distance problem, where we are given two ordered point sets A={a1,..., an } and B={b1, b2,...bn} containing n points and the problem is to find the smallest dopt such that there exists a rigid transformation T with distance(ai, T(bi )) ≤ dopt for every point biB. A (1+δ)-approximation for the bottleneck distance problem is to find a transformation T, such that for each biB, distance (ai, T(bi)) ≤ (1+δ) dopt, where δ is a constant. For an arbitrary constant δ, we obtain a linear O(n/δ6) time (1+δ)-algorithm for the bottleneck distance problem. The best known algorithms for both problems require super-linear time (Li et al. in CPM 2008, 2008).

Research Area(s)

  • Approximation scheme, Constant time, Randomization