Conference paper
The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins
The calculation of the overlap volume of half-spheres 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 predicates 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 predicates by using geometric invariants and Gro¿bner bases. The main application of these certified computations is to predict the 3D structure of proteins.
Language: | English |
---|---|
Publisher: | IEEE Computer Society Press |
Year: | 2009 |
Pages: | 263-264 |
Proceedings: | 6th International Symposium on Voronoi Diagrams in Science and Engineering |
ISBN: | 0769537812 , 1424447690 , 1509070192 , 9780769537818 , 9781424447695 , 9781509070190 , 9764304974 and 9789764304978 |
Types: | Conference paper |
DOI: | 10.1109/ISVD.2009.40 |
ORCIDs: | Anton, François |
3D structure Bioinformatics Biological system modeling Biology computing Delaunay graph Ellipsoids Genomics Gro¿bner bases Molecular biophysics Polymers Proteins Solvents Spine Voronoi diagram action matrices bioinformatics biological macromolecules computational geometry ellipsoids generalized Voronoi vertex genomic scale geometric invariants graph theory half balls half spheres matrix algebra multiplication map proteins