Voronota: A Fast and Reliable Tool for Computing the Vertices of the Voronoi Diagram of Atomic Balls

摘要

The Voronoi diagram of balls, corresponding to atoms of van der Waals radii, is particularly well-suited for the analysis of three-dimensional structures of biological macromolecules. However, due to the shortage of practical algorithms and the corresponding software, simpler approaches are often used instead. Here, we present a simple and robust algorithm for computing the vertices of the Voronoi diagram of balls. The vertices of Voronoi cells correspond to the centers of the empty tangent spheres defined by quadruples of balls. The algorithm is implemented as an open-source software tool, Voronota. Large-scale tests show that Voronota is a fast and reliable tool for processing both experimentally determined and computationally modeled macromolecular structures. Voronota can be easily deployed and may be used for the development of various other structure analysis tools that utilize the Voronoi diagram of balls. Voronota is available at: http://www.ibt.lt/bioinformatics/voronota.