드 노보 시퀀스 어셈블러의 병렬화 방법의 비교

Abstract

DNA 시퀀스 어셈블리(Sequence Assembly) 과정은 생체 정보를 포함 하고 있는 DNA 염기 서열을 해독하기 위하여 필수적이며 기본적인 과 정이다. 현재의 기술로는 한 번에 게놈(Genome)을 시퀀싱할 수 없기 때문에, 게놈을 조각내어 시퀀싱하고 이를 다시 재조립하는 어셈블리 과정이 필수적이다. 그동안 이러한 기능을 하는 소프트웨어인 시퀀스 어셈블러(Sequence Assembler)가 많이 개발되었는데, 대부분의 어셈블러는 싱글 스레드(Thread)기반으로 싱글 프로세서에서 실행되도록 개발되었다.2000년대 후반부터 전통적인 Sanger Sequencing 방법의 금전적, 시간적인 한계를 보완한 NGS(Next Generation Sequencing) 기술이 주목받기 시작했다. NGS(Next Generation Sequencing) 기술의 등장으로 처리해야 할 데이터의 양은 기하급수적으로 증가했지만, 기존의 시퀀스 어셈블러들은 이를 감당하지 못하여 어셈블리 과정이 염기 서열 분석 과정의 병목 지점(Bottleneck)이 되었다. 최근에 와서 시퀀스 어셈블러 소프트웨어의 병렬화를 통하여 이러한 병목 현상을 해결하고자 하는 연구가 진행되고 있다. 본 논문에서는 드 노보 시퀀스 어셈블러(De Novo Sequence Assembler)의 실행 시간 중 가장 큰 비중을 차지하는 해쉬맵(Hashmap)생성 부분에 집중하여 연구를 진행하였다. Locking 방법과 Buffered 방법의 두 가지 병렬화 방법을 비교하여, 성능에 영향을 미치는 의미있는 요인을 파악하고 더 나은 병렬화 방안을 제안하고자 한다.

Sequence assembly is one of the essential and basic tasks for genome sequence analysis. The whole genome sequencing at once is impractical with limit current of sequencing technology. So, sequence assembly is a important process that merge individual sequence read to form long continuous sequences. There are many software tools available for genome assembly. But, most of these sequence assemblers are single-threaded applications designed to run on a single processor. In recent years, the next generation sequencing technologies receive attention for replacing Sanger sequencing method with shorter time cost and low cost. The advent of next generation sequencing technologies is accompanied with high DNA sequencing throughput. But, analysis of short read sequences has been limited due to the lack of high performance assembly tools able to handle the vast amount of data. These days, several previous work has been done to develop parallel sequence assembly tools to overcome the limitations. In this paper, we present our work on comparison of parallelization techniques to understand meaningful factors and to suggest a better parallelization method.