title: Stabbing balls and simplifying proteins.
abstract: 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.
authors.affiliation: Department of Computer Science, University of Texas at Dallas, MS-EC 31, Richardson, TX 75080, USA. daescu@utdallas.edu
authors.forename: Ovidiu
authors.initials: O
authors.lastname: Daescu
authors.forename: Jun
authors.initials: J
authors.lastname: Luo
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D020407:Internet; D011506:Proteins / Q000737:chemistry*; D012984:Software; D014584:User-Computer Interface
chemical_list: D011506:Proteins