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. Given two ordered point sets A = {a₁,⋯, a_n} and B = {b₁, b₂, ⋯b_n} containing n points, and a threshold d, the largest well predicted subset problem is to find the rigid transformation T for a largest subset B_opt of B such that the distance between a_i 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 α [8]. We use LWPS(A, B, d, α) to denote the largest well predicted subset problem with meaningful prediction. An (1+δ₁, 1-δ₂)-approximation for LWPS(A, B, d, α) is to find a transformation T to bring a subset B′ ⊆ B of size at least (1-δ₂)|B_opt| such that for each b_i ε B′ the Euclidean distance between the two points distance(a_i , T(b_i )) ≤ (1+δ₁)d. We develop a constant time (1+δ₁, 1-δ₂)-approximation algorithm for LWPS(A, B, d, α) for arbitrary positive constants δ₁ and δ₂.