The voronoi diagram of half-balls and its application to the pbkp_rediction of the 3D structure of proteins

Abstract:

The calculation of the overlap volume of halfspheres or ellipsoids is of direct interest in structural bioinformatics, which is concerned with the computational study of biological macromolecules on a genomic scale. We present an algorithm for computing the Delaunay graph and the overlap volume of a set of half-balls using exact pbkp_redicates that detect the disjointness or non-disjointness of two half-balls and the validity of the generalized Voronoi vertex of four half-balls using geometric invariants and action (multiplication map) matrices. We prove the correctness of the algorithm and the optimality of the degree of the pbkp_redicates by using geometric invariants and Gröbner bases. The main application of these certified computations is to pbkp_redict the 3D structure of proteins. © 2009 IEEE.

Año de publicación:

2009

Keywords:

Fuente:

scopus