Kim Deok-Soo, Ryu Joonghyun, Shin Hayong, Cho Youngsong
Department of Industrial Engineering, Hanyang University, 17 Haengdang-dong, Seongdong-gu, Seoul 133-791, South Korea.
J Comput Chem. 2012 May 15;33(13):1252-73. doi: 10.1002/jcc.22956. Epub 2012 Mar 7.
Given a set of spherical balls, called atoms, in three-dimensional space, its mass properties such as the volume and the boundary area of the union of the atoms are important for many disciplines, particularly for computational chemistry/biology and structural molecular biology. Despite many previous studies, this seemingly easy problem of computing mass properties has not been well-solved. If the mass properties of the union of the offset of the atoms are to be computed as well, the problem gets even harder. In this article, we propose algorithms that compute the mass properties of both the union of atoms and their offsets both correctly and efficiently. The proposed algorithms employ an approach, called the Beta-decomposition, based on the recent theory of the beta-complex. Given the beta-complex of an atom set, these algorithms decompose the target mass property into a set of primitives using the simplexes of the beta-complex. Then, the molecular mass property is computed by appropriately summing up the mass property corresponding to each simplex. The time complexity of the proposed algorithm is O(m) in the worst case where m is the number of simplexes in the beta-complex that can be efficiently computed from the Voronoi diagram of the atoms. It is known in ℝ(3) that m = O(n) on average for biomolecules and m = O(n(2)) in the worst case for general spheres where n is the number of atoms. The theory is first introduced in ℝ(2) and extended to ℝ(3). The proposed algorithms were implemented into the software BetaMass and thoroughly tested using molecular structures available in the Protein Data Bank. BetaMass is freely available at the Voronoi Diagram Research Center web site.
给定三维空间中的一组球形球，称为原子，其质量属性，如原子集合的并集的体积和边界面积，对许多学科都很重要，特别是对于计算化学/生物学和结构分子生物学。尽管之前有许多研究，但这个看似简单的计算质量属性的问题尚未得到很好的解决。如果还要计算原子偏移并集的质量属性，问题就变得更加困难。在本文中，我们提出了能够正确且高效地计算原子并集及其偏移的质量属性的算法。所提出的算法采用了一种基于最近的β - 复形理论的方法，称为β - 分解。给定原子集的β - 复形，这些算法使用β - 复形的单纯形将目标质量属性分解为一组基元。然后，通过适当地汇总与每个单纯形对应的质量属性来计算分子质量属性。在所提出算法的最坏情况下，时间复杂度为O(m)，其中m是β - 复形中单纯形的数量，它可以从原子的Voronoi图高效计算得出。在ℝ(3)中已知，对于生物分子，平均m = O(n)，对于一般球体，最坏情况下m = O(n(2))，其中n是原子的数量。该理论首先在ℝ(2)中引入并扩展到ℝ(3)。所提出的算法已被实现到软件BetaMass中，并使用蛋白质数据库中可用的分子结构进行了全面测试。BetaMass可在Voronoi图研究中心网站免费获取。
