[논문]구 집합에 대한 컨벡스헐 근사

김병주; 김구진; 김영준

doi:10.3745/ktccs.2014.3.1.1

초록
AI-Helper

현재까지 컨벡스헐 (convex hull) 의 계산 알고리즘들은 주로 점 집합 (point set) 에 대해 연구가 수행되어 왔다. 본 논문에서는 이산 공간에서 다양한 반경을 갖는 구 집합에 대한 컨벡스헐을 근사하는 방법을 제시한다. 구 집합에 대한 컨벡스헐 계산은, 특히 단백질 분자의 구조적인 특성을 연구하는 여러 응용분야에서 계산 효율성을 증대시키기 위한 기반 기술이라 할 수 있다. 분자에 대응하는 구의 집합에 대해 복셀 맵 (voxel map) 자료구조를 적용하고 이를 이용하여 컨벡스헐을 계산하는 알고리즘을 제시한다. 제안된 방법은 GPU를 활용한 병렬처리를 수행하여 평균적으로 6,400개 이하의 구가 포함된 집합에 대해 40ms 이내에 컨벡스헐을 계산하는 성능을 보인다.

Abstract ▼ AI-Helper

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 applica...

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.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서 제시하는 컨벡스헐 알고리즘은 복셀 맵으로 표현된 이산 공간에서 효율적으로 구의 집합에 대한 컨벡스헐의 내부 및 외부 복셀을 판별하는 것을 목표로 한다.
본 논문에서는 단백질 분자에 대해 복셀 맵을 이용하여 컨벡스헐을 계산하는 알고리즘을 제안하였다. 분자를 구성하는 원자들이 각각 구로 표현될 때, 각 복셀과 교차하는 원자들의 집합을 구하여 복셀 맵을 구성한다.
본 논문에서는 이산 공간에서 구의 집합에 대한 컨벡스헐을 매우 빠른 속도로 계산하여 구의 집합에 대해 내부와 외부 영역을 구분하는 알고리즘을 제시한다. 기존의 Cudahull과 같은 알고리즘을 분자의 컨벡스헐 계산에 적용할 경우에는 각 원자 표면에서 표본 점들을 추출하여 사용하여야 하며, 결과로 구해지는 컨벡스헐은 다각형 메쉬 (polygonal mesh) 형태이므로 본 논문에서 고려하는 이산 공간에서 컨벡스헐을 계산하기에는 비효율적이다.

가설 설정

분자를 표현하는 집합 M을 포함하는 3차원 공간이 경계 상자의 형태로 주어졌다고 가정한다. 본 논문에서는 단백질 분자를 다양한 반경을 가진 구의 집합 M으로 표현하고, M의 컨벡스헐을 근사화한다.
2A)에서는 구의 집합으로 표현된 단백질 분자에 대해 실 컨벡스헐을 구한 예를 2차원으로 간략화하여 제시한다. 컨벡스헐은 무한대의 반경을 갖는 구 (즉, 지역적인 표면이 평면과 같아 보이는 구) 를 M의 외부에서 M과 접하도록 굴린다고 가정할 때, 구의 envelope 곡면을 추출한 것이라고 가정할 수 있다 (Fig. 2B). 만약 외부에서 굴리는 구의 반경이 무한대보다 작아지면, 이러한 구의 envelope 곡면은 형태가 컨벡스헐과 유사하지만 concave한 부분이 있는 곡면이 구해질 것이다.

제안 방법

분자를 구성하는 원자들이 각각 구로 표현될 때, 각 복셀과 교차하는 원자들의 집합을 구하여 복셀 맵을 구성한다. 경계 복셀에서 복셀 맵과의 최소 거리 계산을 수행하여 컨벡스헐을 계산한다. 제안된 방법은 GPU를 활용한 병렬처리를 수행하여 6,400개 이하의 구의 집합에 대해 평균적으로 40ms 이내에 컨벡스헐을 계산하는 성능을 보여준다.
본 논문에서 제안하는 알고리즘은 구의 집합을 포함하는 경계 상자 (bounding box) 를 계산하고, 경계 상자에 대한 복셀 맵 (voxel map)을 구성한다. 경계 상자의 최외곽에 있는 복셀들로부터 단백질 분자까지의 최소 거리 계산을 통해 컨벡스헐을 계산하고, GPU를 기반으로 병렬 처리를 수행함으로써 효율적으로 컨벡스헐을 추출한다.
org) 와 분자를 복셀 맵으로 구성하는 데 걸린 수행 시간 및 컨벡스헐을 계산하는 데 걸린 시간을 제시한다. 또한, 본 논문에서 제안한 알고리즘을 단일 CPU(single-core CPU) 를 이용하여 계산한 결과 및 GPU 기반의 CUDA 프로그램을 이용하여 계산한 결과를 제시하였다. 자료구조를 구성하는 데 걸린 수행 시간과 컨벡스헐을 계산하는 데 걸린 시간은 100번 반복 수행한 평균값이다.
기존의 Cudahull과 같은 알고리즘을 분자의 컨벡스헐 계산에 적용할 경우에는 각 원자 표면에서 표본 점들을 추출하여 사용하여야 하며, 결과로 구해지는 컨벡스헐은 다각형 메쉬 (polygonal mesh) 형태이므로 본 논문에서 고려하는 이산 공간에서 컨벡스헐을 계산하기에는 비효율적이다. 본 논문에서 제안하는 알고리즘은 구의 집합을 포함하는 경계 상자 (bounding box) 를 계산하고, 경계 상자에 대한 복셀 맵 (voxel map)을 구성한다. 경계 상자의 최외곽에 있는 복셀들로부터 단백질 분자까지의 최소 거리 계산을 통해 컨벡스헐을 계산하고, GPU를 기반으로 병렬 처리를 수행함으로써 효율적으로 컨벡스헐을 추출한다.
분자를 표현하는 집합 M을 포함하는 3차원 공간이 경계 상자의 형태로 주어졌다고 가정한다. 본 논문에서는 단백질 분자를 다양한 반경을 가진 구의 집합 M으로 표현하고, M의 컨벡스헐을 근사화한다. 이산 공간에서 컨벡스헐을 근사화하기 위해 M에 포함된 모든 구를 포함하는 최소영역인 경계 박스를 정의하고, 경계 박스를 복셀(voxel)들의 집합으로 분할한다.
본 논문에서는 단백질 분자에 대해 복셀 맵을 이용하여 컨벡스헐을 계산하는 알고리즘을 제안하였다. 분자를 구성하는 원자들이 각각 구로 표현될 때, 각 복셀과 교차하는 원자들의 집합을 구하여 복셀 맵을 구성한다. 경계 복셀에서 복셀 맵과의 최소 거리 계산을 수행하여 컨벡스헐을 계산한다.

대상 데이터

사용한 pdb 파일은 1,001개의 원자를 포함하는 2LYZ부터 11,183개의 원자로 구성된 1Q0D까지 총 6개의 단백질 분자를 대상으로 하였으며, 평균적으로 6,354개의 원자에 대해 37.94ms의 수행시간이 소요되었다. GPU 기반의 프로그램은 CPU로 구현한 프로그램에 비해 평균적으로 약 45.
실험은 Intel core(TM) i5 CPU (2.8GHz)와 4.0GB의 DRAM 및 nVidia GTX590 GPU가 장착된 컴퓨터에서 실행하였다. Window 환경에서 Visual C++, CUDA를 이용하여 실험 결과를 얻었고, OpenGL을 이용하여 시각화하였다.

데이터처리

0GB의 DRAM 및 nVidia GTX590 GPU가 장착된 컴퓨터에서 실행하였다. Window 환경에서 Visual C++, CUDA를 이용하여 실험 결과를 얻었고, OpenGL을 이용하여 시각화하였다. 표 1에서는 실험에서 입력으로 사용한 단백질 분자의 pdb id(http://www.

이론/모형

단백질 분자의 채널을 계산하는 기존 연구들은 분자의 컨벡스헐을 계산하기 위해 주로 Quickhull 알고리즘 [12] 을 사용하였으며, 이 알고리즘은 점 집합 (point set) 에 대해서 매우 빠른 속도로 컨벡스헐을 계산한다. Quickhull 알고리즘은 점 집합에 대해 극단점들 (extreme point) 을 찾고, 극단점들에 의해 정의된 영역 내부에 속하는 점들을 제거하는 과정을 재귀적으로 수행하면서 컨벡스헐을 계산한다.
본 논문에서 제안하는 알고리즘은 구의 집합에 대한 컨벡스헐 계산을 위하여 Kim 등 [15] 이 제시한 방법을 적용하여 복셀 맵 구조 상에서 한 점으로부터 구의 집합에 대해 최소 거리를 계산한다.

성능/효과

94ms의 수행시간이 소요되었다. GPU 기반의 프로그램은 CPU로 구현한 프로그램에 비해 평균적으로 약 45.28배 계산 속도가 향상되었다.
본 논문에서는 이산 공간에서 구의 집합에 대한 컨벡스헐을 매우 빠른 속도로 계산하여 구의 집합에 대해 내부와 외부 영역을 구분하는 알고리즘을 제시한다. 기존의 Cudahull과 같은 알고리즘을 분자의 컨벡스헐 계산에 적용할 경우에는 각 원자 표면에서 표본 점들을 추출하여 사용하여야 하며, 결과로 구해지는 컨벡스헐은 다각형 메쉬 (polygonal mesh) 형태이므로 본 논문에서 고려하는 이산 공간에서 컨벡스헐을 계산하기에는 비효율적이다. 본 논문에서 제안하는 알고리즘은 구의 집합을 포함하는 경계 상자 (bounding box) 를 계산하고, 경계 상자에 대한 복셀 맵 (voxel map)을 구성한다.
경계 복셀에서 복셀 맵과의 최소 거리 계산을 수행하여 컨벡스헐을 계산한다. 제안된 방법은 GPU를 활용한 병렬처리를 수행하여 6,400개 이하의 구의 집합에 대해 평균적으로 40ms 이내에 컨벡스헐을 계산하는 성능을 보여준다. 향후, 제시된 알고리즘들을 좀 더 병렬화하여 성능을 개선할 계획이다.

후속연구

제안된 방법은 GPU를 활용한 병렬처리를 수행하여 6,400개 이하의 구의 집합에 대해 평균적으로 40ms 이내에 컨벡스헐을 계산하는 성능을 보여준다. 향후, 제시된 알고리즘들을 좀 더 병렬화하여 성능을 개선할 계획이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	본 논문에서 제안한, 단백질 분자에 대해 복셀 맵을 이용하여 컨벡스헐을 계산하는 알고리즘의 성능은 어떠한가?	경계 복셀에서 복셀 맵과의 최소 거리 계산을 수행하여 컨벡스헐을 계산한다. 제안된 방법은 GPU를 활용한 병렬처리를 수행하여 6,400개 이하의 구의 집합에 대해 평균적으로 40ms 이내에 컨벡스헐을 계산하는 성능을 보여준다. 향후, 제시된 알고리즘들을 좀 더 병렬화하여 성능을 개선할 계획이다.
	Quickhull 알고리즘은 어떠한 과정을 수행하나요?	단백질 분자의 채널을 계산하는 기존 연구들은 분자의 컨벡스헐을 계산하기 위해 주로 Quickhull 알고리즘 [12] 을 사용하였으며, 이 알고리즘은 점 집합 (point set) 에 대해서 매우 빠른 속도로 컨벡스헐을 계산한다. Quickhull 알고리즘은 점 집합에 대해 극단점들 (extreme point) 을 찾고, 극단점들에 의해 정의된 영역 내부에 속하는 점들을 제거하는 과정을 재귀적으로 수행하면서 컨벡스헐을 계산한다. 최근 에는 Quickhull 알고리즘을 바탕으로 GPU 병렬 처리 가속을 CUDA 라이브러리로 구현한 Cudahull 알고리즘 [13] 이 발표되었다.
	컨벡스헐 계산 알고리즘의 사용목적은 무엇인가요?	리간드 (ligand) 가 분자와 결합할 수 있는 활성 부위 (active site) 를 발견하고, 외부로부터 활성 부위까지 도달할 수 있는 채널 (channel) 및 터널 (tunnel) 을 탐색하기 위해 단백질 분자의 내부 영역과 외부 영역이 구분되어야 하며, 이를 위해 컨벡스헐 계산 알고리즘이 사용되어 왔다 [1-11].

참고문헌 (16)

T.J.A. Ewing, S. Makino, A.G. Skillman, and I.D. Kuntz, "DOCK4.0: Search Strategies for Automated Molecular Docking of Flexible Molecule Databases," Journal of Computer-Aided Molecular Design, Vol.15, No.5, pp.411-428, 2001.

상세보기
S.K. Lai-Yuen and Y.S. Lee, "Interactive Computer-Aided Design for Molecular Docking and Assembly," Computer-Aided Design and Applications, Vol.3 No.6, pp.701-709, 2006.

상세보기
D. Levine, M. Facello, P. Hallstrom, G. Reeder, B. Walenz, and F. Stevens, "Stalk: an Interactive System for Virtual Molecular Docking," IEEE Computational Science and Engineering, Vol.4, No.2, pp.55-65, 1997.

상세보기
H. Nagata, H. Mizushima, and H. Tanaka, "Concept and Prototype of Protein-Ligand Docking Simulator with Force Feedback Technology," Bioinformatics, Vol.18, No.1, pp.140-146, 2002.

상세보기
R.D. Taylor, P.J. Jewsbury, and J.W. Essex, "A Review of Protein-Small Molecule Docking Methods," Journal of Computer-Aided Molecular Design, 16(3), 151-166(2002).

상세보기
O. Trott and A.J. Olson, "AutoDock Vina: Improving the Speed and Accuracy of Docking with a New Scoring Function, Efficient Optimization, and Multithreading," Journal of Computational Chemistry, Vol.31, No.2, pp.455-461, 2010.

상세보기
C.M. Venkatachalam, X. Jiang, T. Oldfield, and M. Waldman, "LigandFit : a Novel Method for the Shape-Directed Rapid Docking of Ligands to Protein Active Sites," Journal of Molecular Graphics and Modelling, Vol.21, No.4, pp.289-307, 2003.

상세보기
Y. Zhao and M.F. Sanner, "Protein-Ligand Docking with Multiple Flexible Side Chains," Journal of Computer Aided Molecular Design, Vol.22 No.9, pp.673-679, 2008.

상세보기
M. Petrek, M. Otyepka, P. Banas, P. Kosinova, J. Koca, and J. Damborsky, "CAVER: a new tool to explore routes from protein clefts, pockets and cavities," BMC Bioinformatics, Vol.7, pp.316-324, 2006.

상세보기
M.Petrek, P. Kosinova, J. Koca, and M. Otyepka, "MOLE: a Voronoi diagram based explorer of molecular channels, pores, and tunnels," Structure 2007, Vol.15, No.11, pp.1357-1363, 2007.
R. G. Coleman, and K. A. Sharp, "Finding and Characterizing Tunnels in Macromolecules with Application to Ion Channels and Pores," Biophysical Journal, Vol.96, No.2, pp.632-645, 2009.

상세보기
C. B.Barber, D. P. Dobkin, and H. Huhdanpaa, "The quickhull algorithm for convex hulls," ACM Transactions on Mathematical Software, Vol.22, No.4, pp.469-483, 1996.

상세보기
A. Stein, E. Geva, and J. El-Sana, "CudaHull: Fast parallel 3D convex hull on the GPU," Computers & Graphics, Vol.36, No.4, pp.265-271, 2012.

상세보기
J.-D. Boissonnat, A. Cerezo, O. Devillers, J. Duquesne, M. Yvinec, "An algorithm for constructing the convex hull of a set of spheres in dimension d. Computational Geometry, Vol.6, No.2, pp.123-130, 1996.

상세보기
B. Kim, J. E. Lee, Y. J. Kim, K.-J. Kim, "Comparison of voxel map and sphere tree structures for proximity computation of protein molecules," Journal of Korea Multimedia Society, Vol.15, No.6, pp.794-804, 2012.

원문보기 상세보기
B. Kim, and K.-J. Kim, "Computing the convex hull for a set of spheres on a GPU," Procd. of VRCAI 2012 (poster abstract), Dec.2-4, Singapore, pp.345, 2012.

이 논문을 인용한 문헌

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

구 집합에 대한 컨벡스헐 근사
Approximating the Convex Hull for a Set of Spheres 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (16)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

구 집합에 대한 컨벡스헐 근사 Approximating the Convex Hull for a Set of Spheres 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (16)

이 논문을 인용한 문헌

저자의 다른 논문 :

김병주 (16) 김구진 (22) 김영준 (7)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

구 집합에 대한 컨벡스헐 근사
Approximating the Convex Hull for a Set of Spheres 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper