Triangulation of molecular surfaces

Given a molecule, which consists of a set of atoms, a molecular surface is defined for a spherical probe approximating a solvent molecule. Molecular surface is used for both the visualization of the molecule and the computation of various molecular properties such as the area and volume of a protein, which are important for studying problems such as protein docking and folding. In this paper, we present an O(n) time algorithm, in the worst case, for triangulating molecular surface based on the combinatorial information provided by the beta-shape of the molecule with n atoms. The proposed algorithm takes advantage of the concise representation of topology among atoms stored in the beta-shape. A molecular surface consists of two parts: a blending surface consisting of blending patches and a (solvent) contact surface consisting of (solvent) contact patches. For each blending patch, the algorithm uses compact masks for the construction of a triangular mesh in O(c') time in the worst case, where c is the number of point evaluations on the blending patch. For each contact patch, the algorithm uses a template, for each atom type, for the triangulation of the boundary of the atom. Then, the triangular mesh is trimmed off by hyperplanes where each hyperplane corresponds to an arc of the boundary of the contact patch. The triangulation of a contact patch takes O(c '') time in the worst case, where c '' is the number of point evaluations on the boundary of an atom. Since there are at most O(n) patches, the worst case time complexity is O(n). The proposed algorithm also handles internal voids and guarantees the watertightness of the produced triangular mesh of a molecular surface. In addition, the level-of-detail is easily achieved as a by-product of the proposed scheme. The proposed algorithm is fully implemented and statistics from experiments are also collected. (C) 2009 Elsevier Ltd. All rights reserved.This research was supported by the Korea Science and Engineering Foundation (KOSEF) through the National Research Lab. Program funded by the Ministry of Science and Technology, Korea (No. R0A-2007-000-20048-0). Deok-Soo Kim was in part supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2007-314-D00311) and BK21. Youngsong Cho was supported by BK21. We thank reviewers for their constructive comments