Constant time approximation scheme for largest well predicted subset

摘要

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, ..., a_n}, where each ai is a point in 3D space. Given two ordered point sets A = {a1, ..., a_n} and B = {b_1, b_2, ... b_n} 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 B_(opt) of B such that the distance between ai and T (b_i) is at most d for every b_i in B_(opt). A meaningful prediction requires that the size of B_(opt) 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)|B_(opt) | such that for each b_i ∈ B', the Euclidean distance between the two points distance(a_i,T (b_i)) ≤ (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/δ_1~5) 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 = {a_1, . . ., a_n} and B = {b_1, b_2, ... b_n} containing n points and the problem is to find the smallest d_(opt) such that there exists a rigid transformation T with distance(a_i,T (b_i)) ≤ d_(opt) for every point b_i ∈ B. A (1+δ)-approximation for the bottleneck distance problem is to find a transformation T, such that for each b_i ∈ B, distance(a_i,T (b_i)) ≤ (1+δ)d_(opt), 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).