Title: Stabbing balls and simplifying proteins

Authors: Ovidiu Daescu, Jun Luo

Addresses: Department of Computer Science, University of Texas at Dallas, MS-EC 31, 2601 N. Floyd Rd., Richardson, TX 75080, USA. ' Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shekou, Shenzhen, Zip 518067, China

Abstract: We address the problem of stabbing a sequence of indexed balls B = {B₁,B₂, . . . , B_n} in R³, where B_i (1 ≤ i ≤ n) has centre p_i and radius ε_i; a solution is an increasing integer sequence i₁, . . . , i_m such that i₁ = 1, i_m = n and for i_j ≤ k ≤ i_j+1 the line segment Pi_j Pi_j+1 stabs the ball B_k; 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.

Keywords: algorithm; ball stabbing; computational geometry; protein simplification; bioinformatics; molecule chains; visualisation; matching; searching efficiency; molecule databases; protein databases; protein chains.

DOI: 10.1504/IJBRA.2009.022464

International Journal of Bioinformatics Research and Applications, 2009 Vol.5 No.1, pp.64 - 80

Published online: 07 Jan 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article