Stabbing balls and simplifying proteins
Ovidiu Daescu, Jun Luo · International Journal of Bioinformatics Research and Applications · 2009
We address the problem of stabbing a sequence of indexed balls B = {B1,B2, . . . , Bn} in R³, where Bi (1 ≤ i ≤ n) has centre pi and radius εi; a solution is an increasing integer sequence i1, . . . , im such that i1 = 1, im = n and for ij ≤ k ≤ ij+1 the line segment Pij Pij+1 stabs the ball Bk; the goal is to minimise m. The problem finds applications in simplification of molecule chains for visualisation, matching and efficient searching in molecule and protein databases. We implemented the algorithm and created a web server where one can input a pdb file and get the simplified protein chains. We did experiments on thousands of proteins from the PDB Bank to estimate the simplification ratio achieved.