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_1, ... ,a_n} and B = {b_1,6_2, ? ? ? 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_1 and T(b_1) is at most d for every bi in B_(opt). A meaningful prediction requires that the size of B_(opt) is at least an for some constant α [8]. We use UWPS(A,B,d,α) to denote the largest well predicted subset problem with meaningful prediction. An (1 + <5i,l — ^-approximation for LWPS(A,B,d,a) is to find a transformation T to bring a subset B' C B of size at least (1 — 62) I B_(opt) I such that for each bi G B', the Euclidean distance between the two points distance(a,, T(bi)) < (1 + 5i)d. We develop a constant time (1 + δ_1,l — ^-approximation algorithm for VNPS(A,B,d,a) for arbitrary positive constants δ_1 and fo.