구 집합에 대한 컨벡스헐 근사
Approximating the Convex Hull for a Set of Spheres
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
현재까지 컨벡스헐 (convex hull) 의 계산 알고리즘들은 주로 점 집합 (point set) 에 대해 연구가 수행되어 왔다. 본 논문에서는 이산 공간에서 다양한 반경을 갖는 구 집합에 대한 컨벡스헐을 근사하는 방법을 제시한다. 구 집합에 대한 컨벡스헐 계산은, 특히 단백질 분자의 구조적인 특성을 연구하는 여러 응용분야에서 계산 효율성을 증대시키기 위한 기반 기술이라 할 수 있다. 분자에 대응하는 구의 집합에 대해 복셀 맵(voxel map) 자료구조를 적용하고 이를 이용하여 컨벡스헐을 계산하는 알고리즘을 제시한다. 제안된 방법은 GPU를 활용한 병렬처리를 수행하여 평균적으로 6,400개 이하의 구가 포함된 집합에 대해 40ms 이내에 컨벡스헐을 계산하는 성능을 보인다.
Abstract
Most of the previous algorithms focus on computing the convex hull for a set of points. In this paper, we present a method for approximating the convex hull for a set of spheres with various radii in discrete space. Computing the convex hull for a set of spheres is a base technology for many applications that study structural properties of molecules. We present a voxel map data structures, where the molecule is represented as a set of spheres, and corresponding algorithms. Based on CUDA programming for using the parallel architecture of GPU, our algorithm takes less than 40ms for computing the convex hull of 6,400 spheres in average.
참고문헌 (16)
- T. J. A. Ewing, "DOCK4. 0 : Search Strategies for Automated Molecular Docking of Flexible Molecule Databases", Journal of Computer-Aided Molecular Design, 15(5), pp.411~428 (2001)
- S. K. Lai-Yuen, "Interactive Computer-Aided Design for Molecular Docking and Assembly", Computer-Aided Design and Applications, 3(6), pp.701~709 (2006)
- D. Levine, "Stalk : an Interactive System for Virtual Molecular Docking", IEEE Computational Science and Engineering, 4(2), pp.55~65 (1997)
- H. Nagata, "Concept and Prototype of Protein-Ligand Docking Simulator with Force Feedback Technology", Bioinformatics, 18(1), pp.140~146 (2002)
- R. D. Taylor, "A Review of Protein-Small Molecule Docking Methods", Journal of Computer-Aided Molecular Design, 16(3), pp.151~166 (2002)
- O. Trott, "AutoDock Vina : Improving the Speed and Accuracy of Docking with a New Scoring Function, Efficient Optimization, and Multithreading", Journal of Computational Chemistry, 31(2), pp.455~461 (2010)
- C. M. Venkatachalam, "LigandFit : a Novel Method for the Shape-Directed Rapid Docking of Ligands to Protein Active Sites", Journal of Molecular Graphics and Modelling, 21(4), pp.289~307 (2003)
- Y. Zhao, "Protein-Ligand Docking with Multiple Flexible Side Chains", Journal of Computer Aided Molecular Design, 22(9), pp.673~679 (2008)
- M. Petrek, "CAVER : a new tool to explore routes from protein clefts, pockets and cavities", BMC Bioinformatics, 7, pp.316~324 (2006)
- M. Petrek, "MOLE : a Voronoi diagram based explorer of molecular channels, pores, and tunnels", Structure 2007, 15(11), pp.1357~1363 (2007)
- R. G. Coleman, "Finding and Characterizing Tunnels in Macromolecules with Application to Ion Channels and Pores", Biophysical Journal, 96(2), pp.632~645 (2009)
- C. B. Barber, "The quickhull algorithm for convex hulls", ACM Transactions on Mathematical Software, 22(4), pp.469~483 (1996)
- A. Stein, "CudaHull : Fast parallel 3D convex hull on the GPU", Computers & Graphics, 36(4), pp.265~271 (2012)
- J. -D. Boissonnat, "An algorithm for constructing the convex hull of a set of spheres in dimension d", Computational Geometry, 6(2), pp.123~130 (1996)
- 김병주, "단백질 분자에 대한 proximity 연산을 위한 복셀 맵과 스피어 트리 구조 비교", 멀티미디어학회논문지, 15(6), pp.794~804 (2012), 한국멀티미디어학회[DOI]
- B. Kim, "Computing the convex hull for a set of spheres on a GPU", Procd. of VRCAI 2012 (poster abstract), pp.345~ (2012)