Stabbing balls and simplifying proteins.
We address the problem of stabbing a sequence of indexed balls B = {B1,B2, . . . , Bn} in R(3), where Bi (1 <or= i <or= n) has centre pi and radius epsiloni; a solution is an increasing integer sequence i1, . . . , im such that i1 = 1, im = n and for ij <or= k <or= 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.
Daescu
Ovidiu
O
Department of Computer Science, University of Texas at Dallas, MS-EC 31, Richardson, TX 75080, USA. daescu@utdallas.edu
Luo
Jun
J
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D020407:Internet; D011506:Proteins / Q000737:chemistry*; D012984:Software; D014584:User-Computer Interface
D011506:Proteins