그래픽 하드웨어를 이용한 분자용 보로노이 다이어그램 계산
Voronoi Diagram Computation for a Molecule Using Graphics Hardware
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 주어진 단백질 분자에 대해 3차원 보로노이 다이어그램을 계산하는 알고리즘을 제안한다. 분자는 반경이 서로 다른 구의 집합으로 표현되며, 각 구의 반경은 원자의 반데르바스 (van der Waals) 반경에 대응한다. 보로노이 다이어그램은 3차원 공간을 복셀 (voxel)의집합으로 분할한 뒤, 보로노이 다이어그램을 포함하는 복셀을 보수적으로 추출함으로써 구성된다. 분자의 계층적 성질을 이용하여BVH(bounding volume hierarchy)를 구성하고, CUDA 프로그래밍을 통하여 그래픽 하드웨어 가속을 활용함으로써 계산 시간 효율성을 높인다. 공간이 최대 224개의 복셀로 분할될 경우, 단일 코어 CPU로 구현하는 알고리즘에 비해 계산 속도가 323배 가량 향상 되었다.
Abstract
We present an algorithm that computes a 3 dimensional Voronoi diagram for a protein molecule in this paper. The molecule is represented as a set of spheres with van der Waals radii. The Voronoi diagram is constructed in the 3D space by finding the voxels containing it. For the feasibility of the computation, we represent the molecule as a BVH (bounding volume hierarchy), and our system is accelerated by modern graphics hardware with CUDA programming support. Compared to single-core CPU implementations, experimental results show 323 times faster performance in the computation time, when the space is partitioned into 224 voxels.
참고문헌 (16)
- Y. -E. A. Ban, "Interface surfaces for protein-protein complexes", Proceedings of the 8th annual international conference on research in computational molecular biology, pp.205~212 (2004)
- J. Bernauer, "A new protein-protein docking scoring function based on interface residue properties", Bioinformatics, 23(5), pp.555~562 (2007)
- A. Bondi, "van der Waals Volumes and Radii", The Journal of Physical Chemistry, 68(3), pp.441~451 (1964)
- I. Fischer, "Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU", Journal of Graphics Tools, 11(4), pp.39~60 (2006)
- M. Gerstein, "Protein Geometry: Distances, Areas, and Volumes, In International Tables for Crystallography", pp.531~539 (2001), Crystallography of biological macromolecules, pp. 531-539
- K. E. Hoff III, "Fast computation of generalized Voronoi diagrams using graphics hardware", SIGGRAPH’99 Proc. of the 26th annual conference on Computer graphics and interactive techniques, pp.277~286 (1999)
- H. –H. Hsieh, "A simple GPU-based approach for 3D Voronoi diagram construction and visualization", Simulation Modelling Practice and Theory, 13, pp.681~692 (2005)
- 이성훈, "Interaction interfaces in proteins via the Voronoi diagram of atoms", CAD Computer Aided Design, 38(11), pp.1192~1204, Pergamon Press Ltd.
- D. –S. Kim, "Euclidean Voronoi diagram of 3D balls and its computation via tracing edges", Computer-Aided Design, 37, pp.1412~1424 (2005)
- D. –S. Kim, "“Euclidean voronoi diagrams of 3D spheres: Their construction and related problems from biochemistry,” Mathematics of Surfaces 2005", LNCS, pp.255~271 (2005)
- K. –J. Kim, "Voronoi diagram computation for protein molecules using graphics hardware (poster)", Proceedings of ACM SIGGRAPH (2010)
- A. Poupon, "Voronoi and Voronoi-related tessellations in studies of protein structure and interaction", Current Opinion in Structural Biology, 14(2), pp.233~241 (2004)
- N. Ray, "Intersurf: dynamic interface between proteins", Journal of Molecular Graphics and Modelling, 23(4), pp.347~354 (2005)
- F. Ric, "The interpretation of protein structures: total volume, group volume distributions and packing density", Journal of Molecular Biology, 82, pp.1~14 (1974)
- G. Rong, "Variants of jump flooding algorithm for computing discrete Voronoi diagrams", Proceedings of the 4thInternational Symposium on Voronoi Diagrams in Science and Engineering, pp.176~181 (2007)
- A. Varshney, "Defining, computing, and visualizing molecular interfaces", Proceedings of the IEEE visualization, pp.36~43 (1995)