BLAST는 생명정보학 분야에서 가장 많이 사용하는 도구이다. 이 도구는 입력서열을 기존 서열 데이터베이스와 신속히 비교하고 그 기능을 예측한다. 생물학자는 BLAST를 이용하여 실험의 범위, 시간과 비용을 줄일 수 있다. 하지만, 서열 데이터 양이 급격히 증가함에 따라 그 처리 시간도 같이 증가하여 성능개선 방안이 필요하다. 본 논문에서는 대용량 BLAST처리 성능 향상을 위한 PC 기반의 클러스터 인프라 (E-Cluster)를 제시하고 이 기반에서 데이터베이스 분할기법 (Logical Partitioning)과 질의 라우팅 기법(Intra-Query)을 제안한다. 제안된 시스템을 평가하기 위해 다양한 길이의 서열들과 NR 데이터베이스와 비교하여 응답시간(Response Time), 성능 향상(Speedup), 효율(Efficiency) 관점에서 평가한다. 본 실험을 통해 기존 SMP, Cluster, 그리드 기반의 BLAST 시스템보다 성능, 효율이 뛰어남을 확인하였고, 특히 제안한 시스템의 최대 효율은 600%로 매우 높았다.
BLAST는 생명정보학 분야에서 가장 많이 사용하는 도구이다. 이 도구는 입력서열을 기존 서열 데이터베이스와 신속히 비교하고 그 기능을 예측한다. 생물학자는 BLAST를 이용하여 실험의 범위, 시간과 비용을 줄일 수 있다. 하지만, 서열 데이터 양이 급격히 증가함에 따라 그 처리 시간도 같이 증가하여 성능개선 방안이 필요하다. 본 논문에서는 대용량 BLAST처리 성능 향상을 위한 PC 기반의 클러스터 인프라 (E-Cluster)를 제시하고 이 기반에서 데이터베이스 분할기법 (Logical Partitioning)과 질의 라우팅 기법(Intra-Query)을 제안한다. 제안된 시스템을 평가하기 위해 다양한 길이의 서열들과 NR 데이터베이스와 비교하여 응답시간(Response Time), 성능 향상(Speedup), 효율(Efficiency) 관점에서 평가한다. 본 실험을 통해 기존 SMP, Cluster, 그리드 기반의 BLAST 시스템보다 성능, 효율이 뛰어남을 확인하였고, 특히 제안한 시스템의 최대 효율은 600%로 매우 높았다.
BLAST (Basic Local Alignment Search Tool) is a best well-known tool in a bioinformatics area. BLAST quickly compares input sequences with annotated huge sequence databases and predicts their functions. It helps biologists to make it easy to annotate newly found sequences with reduced experimental ti...
BLAST (Basic Local Alignment Search Tool) is a best well-known tool in a bioinformatics area. BLAST quickly compares input sequences with annotated huge sequence databases and predicts their functions. It helps biologists to make it easy to annotate newly found sequences with reduced experimental time, scope, and cost. However, as the amount of sequences is increasing remarkably with the advance of sequencing machines, performance of BLAST has been a critical issue and tried to solve it with several alternatives. In this paper, we propose a new PC-Based Cluster system (E-Cluster), a new physical data design methodology (logical partitioning technique) and a query routing technique (intra-query routing). To verify our system, we measure response time, speedup, and efficiency for various sizes of sequences in NR (Non-Redundancy) database. Experimental result shows that proposed system has better speedup and efficiency (maximum 600%) than those o( conventional approaches such as SMF machines, clusters, and grids.
BLAST (Basic Local Alignment Search Tool) is a best well-known tool in a bioinformatics area. BLAST quickly compares input sequences with annotated huge sequence databases and predicts their functions. It helps biologists to make it easy to annotate newly found sequences with reduced experimental time, scope, and cost. However, as the amount of sequences is increasing remarkably with the advance of sequencing machines, performance of BLAST has been a critical issue and tried to solve it with several alternatives. In this paper, we propose a new PC-Based Cluster system (E-Cluster), a new physical data design methodology (logical partitioning technique) and a query routing technique (intra-query routing). To verify our system, we measure response time, speedup, and efficiency for various sizes of sequences in NR (Non-Redundancy) database. Experimental result shows that proposed system has better speedup and efficiency (maximum 600%) than those o( conventional approaches such as SMF machines, clusters, and grids.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 PC 기반 클러스터인 E-Cluster를 이용한 BLAST 시스템을 설계하고 구현하였다. E-Cluster 시스템은 대학 내의 PC를 유휴기간 동안 인터넷으로 연결하여, 본연구에서는 BLAST 성능향상을 위해 사용하였다.
본 논문에서는 클러스터와 그리드 컴퓨팅의 기법의 장점을 결합한 PC 기반의 클러스터를 제시하고, 이 기반에서 BLAST 성능향상을 위해 데이터베이스 분할 기법과 질의 라우팅 기법을 제안한다.
저녁이나 주말 등의 유휴 시간에 Wake-up 기능을 통해 참여 PC를 부팅시키고 BLAST 클러스터로 활용한다. 본 방식은 인터넷상에 다수의 노드를 활용하는 그리드 빙식과 노드를 적극적으로 활용할 수 있는 클러스터 방식의 장점을 결합한 것이다. 또한, 기존의 자원을 적극적으로 활용하여 비용을 줄이고, 관리 효율을 높인다.
제안 방법
시스템을 설계하고 구현하였다. E-Cluster 시스템은 대학 내의 PC를 유휴기간 동안 인터넷으로 연결하여, 본연구에서는 BLAST 성능향상을 위해 사용하였다. 본 시스템은 Logical Partitioning 기법과 Intra-Query를 이용하여 성능과 효율을 개선하였다.
이용하였다. N개의 노드에서 성능 향상6%)을 평가하기 위해 단일 시스템의 처리 시간伝)을 다수 노드에서 처리한 시간(G으로 나눈다. N개의 노드에서의 효율(EGe 성능 향상을 노드 수로 나누어 계산한다.
N개의 노드에서 성능 향상6%)을 평가하기 위해 단일 시스템의 처리 시간伝)을 다수 노드에서 처리한 시간(G으로 나눈다. N개의 노드에서의 효율(EGe 성능 향상을 노드 수로 나누어 계산한다.
넷째, 본 논문에서 제안한 방식으로 Intra-Query와 논리적 분할(Logical Partitioning)을 결합하는 것이다. 분할된 데이터베이스를 각 노드에 완전히 캐쉬하여 BLAST 성능과 효율을 높이고 단일 데이터베이스를 유지하므로 관리가 쉽다.
둘째, 캐쉬를 적극적으로 활용하는 Logical DB Partitioning 기법을 제안하여 클러스터 성능과 자원 효율을 극대화한다. 하나의 물리적인 DB를 여러 개로 세그먼트로 나누고 참여 PC가 NFS로 접근하여 메모리에 캐쉬한 다음 각각 독립적으로 BLAST 연산을 수행한다.
본 방식은 인터넷상에 다수의 노드를 활용하는 그리드 빙식과 노드를 적극적으로 활용할 수 있는 클러스터 방식의 장점을 결합한 것이다. 또한, 기존의 자원을 적극적으로 활용하여 비용을 줄이고, 관리 효율을 높인다. 또한, 별도의 공간이 필요 없고 전력 활용 측면에서 우수하다.
E-Cluster 시스템은 대학 내의 PC를 유휴기간 동안 인터넷으로 연결하여, 본연구에서는 BLAST 성능향상을 위해 사용하였다. 본 시스템은 Logical Partitioning 기법과 Intra-Query를 이용하여 성능과 효율을 개선하였다. Logical Partitioning 기법은 데이터베이스 여러 노드가 공유하므로 관리 비용이 저렴하고 최신 데이터 업데이트가 쉽다.
본 실험의 데이터분할을 위해 formatdb 유틸리티를 이용하여 NR 데이터베이스를 50개로 분할하였으며, 질의 서열은 100 Base Pair에서 10000 Base Pair까지 다양 크기의 서열을 이용한다. 성능은〔표 2〕와 같이 응답시간(Response Time), 성능향상(Speedup), 효율(Efficiency)로 평가한다.
또한, 부팅 이후 운영체제와 처리할 데이터를 메모리에 캐쉬하고, 메모리 일부를 램 디스크(RAMDISK) 로 활용하므로 부트 서버와의 통신을 최소화한다. 본 연구에서는 BLAST 프로그램과 분할된 데이터베이스를 메모리에 캐쉬하여 성능을 극대화하였다.
또한, 내부 시스템 구성관점에서는 동적인 노드 환경에서 Logical Partitioning 기반의 Intra-Query를 통해 응답시간을 최소화하고 자원의 효율을 극대화한다. 응답속도, 성능향상, 효율을 통해 본 시스템의 우수성을 검증한다. 본 연구의 공헌은 다음과 같다.
제안한 클러스터 시스템은 대학 내의 PC 자원을 원격 부팅 시켜 BLAST 연산에 활용하는 방법으로, 구축 및 관리 비용은 최소화하고 성능과 확장을 극대화한다. 또한, 내부 시스템 구성관점에서는 동적인 노드 환경에서 Logical Partitioning 기반의 Intra-Query를 통해 응답시간을 최소화하고 자원의 효율을 극대화한다.
첫째, 대학 내 기존 PC 자원에 오픈 소스 기반의 네트워크 부팅 기술〔10〕을 적용하여 BLAST 클러스터를 구축하였다. 저녁이나 주말 등의 유휴 시간에 Wake-up 기능을 통해 참여 PC를 부팅시키고 BLAST 클러스터로 활용한다.
하나의 물리적인 DB를 여러 개로 세그먼트로 나누고 참여 PC가 NFS로 접근하여 메모리에 캐쉬한 다음 각각 독립적으로 BLAST 연산을 수행한다. 특정 노드 개수 이후부터는 I/O가 발생하지 않아서 성능과 효율이 급격히 증가한다.
대상 데이터
본 실험은 2개의 PC 실습실의 50대의 PC를 대상으로 수행하였다. 〔표 1)은 본 실험에서 사용한 각 PC의 사양과, 네트워크, 운영체제, BLAST 프로그램의 버전, 데이터베이스 구성을 제시한다.
클러스터이다. 본 연구에서의 컴퓨팅 노드는 주로 대학 내에서 사용 중인 실습용 PC이다. 평소에는 교육용으로 사용하고 저녁 또는 주말 시간을 이용해 BLAST 전용 클러스터 노드로 활용한다.
성능/효과
컴퓨터를 이용하는 기법과 ii) 다수의 컴퓨팅 노드를 LAN 내에서 묶은 클러스터를 이용하는 방식, 그리고 ⅲ) 인터넷상의 자원을 이용한 그리드 기반의 기법이 소개되었다. 각 접근 방식은 비용, 성능, 확장성, 관리, 안정성 측면에서 장단점이 있다.
〔14〕의 실험에 의하면 SMP 컴퓨터와 클러스터에서의 Sne 각각 L8~19 L9의 성능을 보여준다. 결과적으로 본 연구의 시스템 성능이 기존 시스템보다 1.5~7배 정도 우수함을 확인할 수 있다.
NCBI는 매주 새로운 서열을 제공하고 있으며 제안한 방식은 잦은 갱신주기에 가장 적합한 시스템이다. 둘째, 노드 수에 비례하여 데이터베이스가 분할되어 각 노드에 완전히 캐쉬하여 I/O를 최소화할 수 있다. 데이터베이스가 완전히 캐쉬되는 특정 개수 노드 이상에서 성능이 급격히 향상된다.
데이터베이스가 완전히 캐쉬되는 특정 개수 노드 이상에서 성능이 급격히 향상된다. 물리적 복제와 논리적 복제 방식은 데이터베이스 크기가 노드의 메모리보다 크면 스래싱과 네트워크 트래픽으로 성능이 급격히 저흐]된다셋째, Intra-Query 기반으로 질의 응답시간을 최소화할 수 있다. 데이터베이스 일부만을 검색하고 병합하는 방식으로 빠른 응답시간이 필요한 경우에 적합하다.
제안된 시스템은 기존 시스템에 비해 저렴한 비용과 우수한 확장성을 지원한다. 실험을 통해 기존 SMP, 클러스터, 그리드 보다 성능과 자원 활용 효율 측면에서도 우수함을 검증하였다. 향후 연구로는 노드 수에 따른 응답시간을 예측할 수 있는 함수 모델을 만들 예정이다.
예상한 바와 같이 노드 수가 증가함에 따라 응답시간이 급격히 좋아짐을 확인할 수 있다. 특히, 알고리즘의 특성상 입력 서열의 길이가 짧을수록 처리 시간이 빠르고, 성능 향상 정도가 높음을 확인할 수 있다.
Intra-Query는 데이터베이스의 일부를 접근하여 완선 캐쉬한 뒤 BLAST 연산을 수행하여 성능을 극대화하였다. 제안된 시스템은 기존 시스템에 비해 저렴한 비용과 우수한 확장성을 지원한다. 실험을 통해 기존 SMP, 클러스터, 그리드 보다 성능과 자원 활용 효율 측면에서도 우수함을 검증하였다.
7의 효율을 보여준다. 제안된 시스템의 성능평가를 수행한 결과성능향상, 효율 측면에서 모두 뛰어남을 확인할 수 있다.
본 방식의 장점은 다음과 같다. 첫째, 각 노드가 직접 데이터를 관리하지 않으므로 전체 데이터베이스 업데이트 비용이 줄어든다. NCBI는 매주 새로운 서열을 제공하고 있으며 제안한 방식은 잦은 갱신주기에 가장 적합한 시스템이다.
사용하고 있다〔3〕. 특히 새로 발견된 유전자 서열을 기존 서열과 비교하여 그 기능을 예측하여 생물학자에게 실험의 범위를 줄일 뿐만 아니라 시간과 비용을 절감할 수 있다.
노드의 수에 비례하여 성능이 급격히 증가함을 확인할 수 있다. 특히, 데이터베이스가 메모리에 모두 캐쉬 되는 2개의 노드에서 가장 급격한 성능향상을 보여준다. 이 지점은 각 노드의 메모리 크기에 따라 달라질 수 있다.
예상한 바와 같이 노드 수가 증가함에 따라 응답시간이 급격히 좋아짐을 확인할 수 있다. 특히, 알고리즘의 특성상 입력 서열의 길이가 짧을수록 처리 시간이 빠르고, 성능 향상 정도가 높음을 확인할 수 있다.
후속연구
향후 연구로는 노드 수에 따른 응답시간을 예측할 수 있는 함수 모델을 만들 예정이다. 또한 노드 성능이 다를 경우에 각 노드에서 균등한 응답시간을 얻을 수 있는 방안을 제시할 예정이다.
실험을 통해 기존 SMP, 클러스터, 그리드 보다 성능과 자원 활용 효율 측면에서도 우수함을 검증하였다. 향후 연구로는 노드 수에 따른 응답시간을 예측할 수 있는 함수 모델을 만들 예정이다. 또한 노드 성능이 다를 경우에 각 노드에서 균등한 응답시간을 얻을 수 있는 방안을 제시할 예정이다.
참고문헌 (18)
B. DA, et. al., "GenBank," Nucleic Acids Res. this issue. 2009.
GOLD database, http://www.genomesonline.org/.
남성혁, 김태경, 김경란, 조완섭, "서비스 지향 구조 기반의 EST 서열 주해 시스템," 한국컴퓨터정보학회논문지, 제 13권, 제 3호, 35-44쪽, 2008년 5월.
J. Ye, et al., "BLAST: improvements for better sequence alignment," Nucleic Acids Research, Vol. 34, pp. 6-9, 2006.
S. F. Altschul et al., "Gapped BLAST and PSI-BLAST: A new generation of protein database search programs," Nucleic Acids Research, Vol.25, pp. 3389-3402, 1997.
S. B. Needleman, C.D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of Molecular Biology, Vol.48, No.3, pp.443-53, 1970.
M. K. Gardner: Wu-chun Feng, H.J. Archuleta, "Parallel Genomic Sequence-Searching on an Ad-Hoc Grid: Experiences. Lessons Learned, and Implications," The International Conference on High-Performance Computing, Networking, and Storage, 2006.
G. Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities," AFIPS Conference Proceedings, Vol.30, pp. 483-485, 1967.
Etherboot Project, http://www.etherboot.org.
I. Foster, "The Grid: A New Infrastructure for 21st Century Science," Physics Today, Vol.55, No.2, pp. 42-47, 2002.
A. Krishnan, "GridBLAST: a Globus-based high-throughput implementation of BLAST in a Grid computing framework: Research Articles," Concurrency and Computation: Practice & Experience, Vol. 17, No. 13 pp. 1607-1623. 2005.
H. S. Kim, H. J. Kim and D. S. Han, "Hyper-BLAST: A Parallelized BLAST on Cluster System," Lecture Note in Computer Science, Vol.265, pp.213-222, 2003.
A. Darling, L. Carey, and W. Feng, "The Design, Implementation, and Evaluation of mpiBLAST," International Conference on Linux Clusters, 2003.
홍창범, 차정호, 이성훈, 신승우, 박근준, 박근용, "클러스터 환경에서의 MPI 기반 병렬 서열 유사성 검색에 관한 연구," 한국컴퓨터정보학회논문지, 제 112권, 제 6호, 69-78쪽, 2006년 12월.
R. Bjornson, A. Sherman, S. Weston, N. Willard, and J. Wing, "TuroboBLAST(r): A parallel implementation of BLAST built on the TuroboHub," International Parallel and Distributed Processing Symposium, 2002.
R. de Carvalho Costa and S. Lifschitz. "Database allocation strategies for parallel BLAST evaluation on clusters," Distributed and Parallel Databases, Vol. 13, No.1, 2003.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.