그래프 기반 분산처리 시스템 트리니티를 이용한 서열 정렬 알고리즘 = SAG: Sequence Alignment Algorithm based on Graph with distributed system Trinity

다국어 초록 (Multilingual Abstract)

Sequence alignment is one of the widely used tools in genomics. Recently, after NGS(NextGeneration Sequencing) technology was developed, the production of sequence read data increaseddramatically. A number of sequence alignment algorithms have been developed for processing theseNGS data. However, these algorithms are suffered from a trade-off between throughput andalignment quality, because there is a large computation cost for handling the repeat reads andpolymorphism. On the contrary, alignment algorithms with distributed system such as Hadoop andTrinity can obtain better throughput without compromising alignment quality than existingalgorithms on single machine. In this paper, we suggest SAG, sequence alignment algorithm basedon graph with in-memory distributed system, Trinity proposed by Microsoft. We transformedreference sequence into a graph form, and added new edge between adjacent node havingconnection possibility on graph. And we performed combination of sequence fragments in order tocandidates allowing polymorphism. Finally, we performed glocal alignment to find final results forthe obtained candidates. Our experimental results show that SAG better throughput with samequality or better quality than existing algorithms with Hadoop. We have also proved scalability thatwe obtained better throughput by simply adding machines.

국문 초록 (Abstract)

유전체학(Genomics)에서 서열정렬은 가장 널리 사용된다. 차세대 시퀀싱(Next Generation Sequencing) 기술이 발전하면서, 최근 서열 리드 데이터의 양이 급격하게 증가했다. 급증한 차세대 시퀀싱 데이터를 처리하기 위한 서열정렬 알고리즘이 많이 개발되었다. 하지만 서열정렬 알고리즘들은 반복서열(repeat), 변이(polymorphism)를 처리하기 위해 많은 계산량을 요구한다. 그렇기 때문에 기존 서열정렬 알고리즘은 처리량(throughput)과 정렬품질(quality)사이에 트레이드오프(trade-off)가 존재한다. 하지만 분산처리 시스템Hadoop, Trinity에서 동작하는 정렬 알고리즘은 기존 싱글에서 동작하는 알고리즘에 비해 정렬 품질을 덜 희생하고, 더 높은 처리량을 얻을 수 있다. 본 논문에서는 Microsoft에서 제안한 그래프 기반 인-메모리(in-memory)분산시스템 트리니티(Trinity)에서 동작하는 서열정렬 알고리즘 SAG(Sequence Alignment Algorithm basedon Graph with Trinity)를 제안한다. 우리는 기존 참조 서열을 그래프 형태의 데이터로 변형 한 뒤, 그래프에서연결 가능한 인접한 노드에 새로운 간선을 추가했다. 그리고 변이(polymorphism)를 허용하는 정렬을 수행하기위해 서열조각들 사이의 조합을 통해 후보를 얻었다. 마지막으로 후보를 대상으로 glocal alignment를 수행해최종적인 결과를 찾았다. 실험을 통해 SAG는 기존 Hadoop에서 동작하는 알고리즘과 비교했을 때 비슷하거나더 좋은 정렬 품질조건과 동시에 상당히 높은 처리량을 얻었다. 또한 머신을 추가함으로써 더 좋은 처리량을 얻는확장성을 입증하였다.

참고문헌 (Reference)

• 1 N. G., "de Bruijn. A combinatorial problem" 49 : 758-764, 1946
• 2 Andrew D Smith, "Using quality scores and longer reads improves accuracy of Solexa read mapping" 9 : 128-, 2008
• 3 Andrew D. Smith, "Updates to the RMAP short-read mapping software" 25 (25): 2841-2842, 2009
• 4 B. Langmead, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome" 10 (10): 2009
• 5 B Shao, "Trinity: A distributed graph engine on a memory cloud" 505-516, 2013
• 6 "Trinity Manual"
• 7 H. Li, "The Sequence alignment/map(SAM)format and SAM tools" 25 (25): 2078-2079, 2009
• 8 R. Li, "SOAP2 : an improved ultrafast tool for short read alignment" 25 (25): 1966-1967, 2009
• 9 Dean J, "MapReduce:simplified data processing on large clusters" 51 : 107-113, 2008
• 10 T. F. Smith, "Identification of Common Molecular Subsequences" 147 : 195-197, 1981
• 11 H. Li, "Fast and accurate short read alignment with Burrows-Wheeler transform" 25 (25): 1754-1760, 2009
• 12 Schatz M, "CloudBurst: highly sensitive read mapping with MapReduce" 25 (25): 1363-, 2009
• 13 Tung Nguyen, "CloudAligner : A fast and full-featured MapReduce based tool for sequence mapping" 4 : 171-, 2011
• 14 Needleman, S. B., "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins" 48 : 443-453, 1970