KIPS Trans. Comp. and Comm. Sys. Vol.8, No.10 pp.231~238 pissn: 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 231

Size: px

Start display at page:

Download "KIPS Trans. Comp. and Comm. Sys. Vol.8, No.10 pp.231~238 pissn: 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 231"

희애 온
4 years ago
Views:

1 KIPS Trans. Comp. and Comm. Sys. Vol.8, No.10 pp.231~238 pissn: 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 Parallelization of Genome Sequence Data Pre-Processing on Big Data and HPC Framework Eun-Kyu Byun Jae-Hyuck Kwak Jihyeob Mun ABSTRACT Analyzing next-generation genome sequencing data in a conventional way using single server may take several tens of hours depending on the data size. However, in order to cope with emergency situations where the results need to be known within a few hours, it is required to improve the performance of a single genome analysis. In this paper, we propose a parallelized method for pre-processing genome sequence data which can reduce the analysis time by utilizing the big data technology and the highperformance computing cluster which is connected to the high-speed network and shares the parallel file system. For the reliability of analytical data, we have chosen a strategy to parallelize the existing analytical tools and algorithms to the new environment. Parallelized processing, data distribution, and parallel merging techniques have been developed and performance improvements have been confirmed through experiments. Keywords : Genome Sequence Data Preprocessing, NGS, Big Data, Hadoop, HPC, Parallelization 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 변은규 곽재혁 문지협 요 약 차세대염기서열분석법이생성한유전체원시데이터를기존의방식대로하나의서버에서분석하기위해서는데이터크기에따라수십시간이필요할수있다. 그러나응급환자의진단처럼수시간내에결과를알아야하는상황이존재하기때문에단일유전체분석의성능을향상시킬필요가있다. 본연구에서는빅데이터기술의병렬화기법과고속의네트워크로연결되고병렬파일시스템을공유하는고성능컴퓨팅클러스터를적극적으로활용하여분석시간을크게단축시킬수있는유전체데이터분석의전처리프로세스의병렬화방법을제안한다. 분석데이터의신뢰성을위해기존의검증된분석도구및알고리즘을새로운환경에맞게병렬화하는전략을선택하였다. 프로세스의병렬화, 데이터의분배및병렬병합기법을개발하였고실험을통해성능향상을확인하였다. 키워드 : 유전체데이터전처리, NGS, 빅데이터, Hadoop, 고성능컴퓨팅, 병렬화 1. 서론 1) 차세대염기서열유전체분석법 (NGS, Next Generation 이논문은대한민국정부 ( 과학기술정보통신부 ) 의재원으로정보통신기획평가원의지원 (No , 빅데이터처리고도화핵심기술개발사업총괄및고성능컴퓨팅기술을활용한성능가속화기술개발 ) 과한국과학기술정보연구원주요사업의지원을받아수행된연구임. 이논문은 2018 년도한국정보처리학회추계학술발표대회에서 고성능클러스터와분산병렬파일시스템을이용한유전체데이터전처리작업의효율적인병렬화기법 의제목으로발표된논문을확장한것임. 정회원 : 한국과학기술정보연구원선임연구원 비회원 : 한국과학기술정보연구원선임연구원 Manuscript Received : December 10, 2018 First Revision : August 22, 2019 Accepted : September 9, 2019 * Corresponding Author : Eun-Kyu Byun(ekbyun@kisti.re.kr) Sequencing) 의발전으로인해유전체정보를보다저렴한가격과적은시간을들여읽어낼수있게되었다 [1]. 이렇게얻은유전체데이터를분석하여질병의진단, 예방등에활용할수있다. 이러한분석과정은유전체정보를기계를통해읽어내는작업뿐아니라수백기가바이트에달하는데이터를분석하는과정이필요한데, 이러한분석기존의단일서버를사용하는방식으로수행하면수십시간이소요되는경우도일반적이다. 대규모의컴퓨팅클러스터를소유한경우, 이러한분석을동시에여러개를수행하는방식으로효율을높여왔다. 이러한접근방법은일상적인검사나연구의경우에는크게문제가되지않지만응급환자에게적합한처치를해야하는상황처럼빠른분석이필요한경우에는치명적일수있 This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License ( licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

2 232 정보처리학회논문지 / 컴퓨터및통신시스템제 8 권제 10 호 ( ) 다. 따라서더많은전산자원을활용하더라도단일분석의시간을단축할수있는기술이필요하다. 본논문에서는많은유전체데이터분석에서공통적으로쓰이는데이터전처리프로세스를병렬화하는방법을제안한다. 병렬화된분석프로세스는고속의네트워크로연결되고병렬파일시스템을공유하는복수의서버들위에서동작하여실행시간을크게단축시킬수있다. NGS기법을통한유전자분석과정은여러단계의데이터처리프로세스로구성된파이프라인으로이루어진다. 먼저세포로부터염기서열을읽어야한다. 각염색체혹은 RNA염기서열전체를한꺼번에직접읽어내는것이불가능하다. 따라서시퀀서 (Sequencer) 라는장비를이용하여유전체를작은다수의리드 (Read) 로조각내고이를증폭하여화학및광학적인방법을사용하여염기쌍 (base pair) 들을순서대로읽어내어원시데이터파일을생성한다. 분석을위해서는조각나기전의원래염기서열정보를리드데이터들로부터재조합해야한다. 이러한과정을데이터전처리과정이라하며대부분의유전정보분석기법에서공통적으로필요로한다. 전처리결과의기술방법또한 SAM, BAM이라는파일형식으로표준화되어있다 [2]. 전처리과정의첫단계로각리드들이실제로유전자중어느위치에해당하는지를알아야한다. 이를위해참고유전체 (reference genome) 의염기서열에리드들의데이터를비교하여높은확률로일치하는위치를찾는과정을거친다. 이과정을지역정렬 (alignment) 이라하며많은계산시간과메모리를필요로하지만전처리중필수적인단계이다. 다음으로중복검출단계가필요할수있다. 시퀀서에서 NGS데이터를생성하는과정중중합효소연쇄반응단계에서같은데이터가여러차례발생할수있다. 이러한데이터가분석에왜곡을가져올수있으므로중복으로판단되는리드를표시해둘필요가있다. 데이터를변경하는것이아니라플래그를추가하는것이므로분석응용의필요에따라활용여부를결정할수있다. 마지막으로분석도구가원하는위치의유전체정보에빠르게접근할수있도록색인화하는작업이필요하다. 이를위해서각리드를참고게놈내에서의위치를나타내는전역좌표를기준으로정렬해야한다. 그이후에문자열형식으로되어있는파일을바이너리형식으로변경하고압축하는과정을마친후색인정보를생성해야한다. 본연구에서는가장널리쓰이는유전체원시데이터인 ILLUMINA사의시퀀서에서생성하는 paired-end 리드데이터를대상으로삼았다 [3]. 이원시데이터를지역정렬, 중복검출, 색인하는전처리과정각각을병렬화하고그에필요한데이터전달기법을개발하였다. 데이터의신뢰도를높이기위해프로세스의병렬화, 데이터의분배및병합기법은추가로개발한반면각단위프로세스에서의데이터처리는 기존의검증된도구들이수행하도록하였다. BWA (Burrow- Wheeler Aligner)[4], samblaster[5], samtools[6] 가각각의단계에서사용되었다. 작업및데이터병렬처리의실제구현에는서버간의소켓통신, 병렬파일시스템인 LustreFS를이용한 MPI-IO 및 Hadoop on Luster 기술등을활용하였다. 본연구의차별화되는가치는데이터전처리과정전체를병렬화하여더많은자원을투입하면단일유전정보세트에대해더빠른수행이가능한방법을제안했다는점이다. 이는멀티쓰레드병렬화를활용하였으나단일노드의한계로인해성능향상에제한이있었던기존의방식과하둡등을이용하여병렬화를하였으나파일전처리의병목문제들로인해충분한성능향상을얻지못한기존의연구들의문제점을해결한것이다. 또한공통으로쓰이는전처리과정에집중하여재사용이가능하게함으로써특정분석에서만적용가능한병렬화를제공했던기존의방법과달리모든유전체기반분석에활용가능하다는차이점이있다. 논문의나머지부분은다음과같이구성된다. 2장에서관련연구를간단히소개하고, 3장에서유전체데이터전처리과정병렬화기법을각단계별로상세히소개한다. 추가로전체병렬프로세스관리와데이터재분배방식과관련하여실제실험에사용한구현방식과대안들의장단점에대한의견을제시한다. 4장에서테스트베드에서수행한성능평가결과를제공한다. 2. 관련연구 2009년 Burrow-Wheeler Aligner (BWA) 가개발된이후유전체서열데이터의지역정렬알고리즘의사실상표준으로사용되고있다. 그러나 BWA는상당히많은연산을필요로하는알고리즘으로멀티코어 CPU에서병렬실행을하더라도전체유전체데이터를정렬하는데는몇시간또는며칠이걸리는경우도발생한다. 유전체분석파이프라인을활용하여진단이나치료를돕기위해서는가능한한빨리분석해야하고따라서분산처리프레임워크에서구현되어야가속화가가능하다. 이러한필요성에의해몇가지병렬알고리즘 [7-9] 이제안되었다. 그중하나는 BWA를 Hadoop 프레임워크에서병렬실행시키기위해개발된 BigBWA이다 [10]. Hadoop을이용하여입력파일을분할하여다수의 Mapper가병렬로데이터를처리한다. JNI를이용하여기존의 BWA응용을수정없이호출하여수행한다. 그러나 Hadoop의스토리지시스템인 HDFS는데이터전송, 데이터변환및병합에추가시간을발생시켜예상보다좋지않은성능을보인다. 이는기존의응용프로그램을 Hadoop 환경으로이식할때일반적으로발생하는문제이다. 또하나의 NGS 데이터분석의병렬화사례로는유전체분석중하나인 variant calling의파이프라인단계전체를병렬

빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 233 화한 Halvade가있다 [11]. GATK Best Practice에서제안한알고리즘세트를빅데이터프로그래밍모델인 MapReduce를이용하여구현하였다. 이러한여러노드를이용한병렬화를통해싱글노드만을활용한 multi-thread 방식을뛰어넘는성능향상도이루었다.

본연구에서는이러한문제들을해결하기위해분석에서공통으로쓰이는 NGS데이터의전처리과정전체를고성능클러스터와병렬파일시스템을활용하여병렬화하였다. Fig. 1. Architecture and Execution Steps of KBigBWA 3. 유전체데이터전처리과정병렬화기법 3.

3 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 233 화한 Halvade가있다 [11]. GATK Best Practice에서제안한알고리즘세트를빅데이터프로그래밍모델인 MapReduce를이용하여구현하였다. 이러한여러노드를이용한병렬화를통해싱글노드만을활용한 multi-thread 방식을뛰어넘는성능향상도이루었다. 그외에도 HDFS 대신 Amazon S3와 Lustre를 HDFS 대신활용하는것도가능하다. 그러나 Halvade는 variant calling이라는특정한유전체분석응용에만사용하기위해설계되어서다른분석에사용하기위해서는전처리과정부터다시수행해야한다는한계점이있다. 본연구에서는이러한문제들을해결하기위해분석에서공통으로쓰이는 NGS데이터의전처리과정전체를고성능클러스터와병렬파일시스템을활용하여병렬화하였다. Fig. 1. Architecture and Execution Steps of KBigBWA 3. 유전체데이터전처리과정병렬화기법 3.1 지역정렬단계병렬화지역정렬단계를효율적으로병렬화하기위해 Hadoop을이용하여 BWA를병렬화한기존의 BigBWA의성능상의문제점을 Hadoop on Lustre와병렬 I/O 기술을도입하여개선한 KBigBWA를개발하였다. BigBWA 의성능저하의큰부분은 HDFS를사용하기때문에발생한다. Hadoop 클러스터에서병렬로정렬을수행하려면유전체원시파일을 HDFS에복사해야한다. 또한 BWA에서생성된파일은분석파이프라인의다음단계에서활용하기위해 POSIX 호환파일시스템으로다시복사해야한다. 본연구에서는 Lustre on Hadoop을도입하여문제를해결하였다 [13]. Hadoop 응용프로그램은 HDFS에서파일을복사하거나복사하지않고 Lustre의파일에자유롭게액세스할수있다. HDFS의특징인데이터지역성 (data-locality) 의장점을포기하지만고성능컴퓨팅자원을활용하여훨씬큰성능상의이득을얻을수있다. 이를확인하기위해먼저 BigBWA를변경하지않고단순히 HDFS를 Lustre로교체한후에성능개선을측정해보았다. 실험을위해 10개의계산노드로이루어진 Hadoop 클러스터와 24개의 HDD로구성된 Lustre 시스템을구축하고이를 Infiniband FDR과연결하였다. 각계산노드에는 Seagate의 Hadoop on Lustre 어댑터와연동한 Hadoop 2.8을설치하였고 HDFS를구성하는로컬디스크로는 SATA SSD를사용하였다. Fig. 2에서가장왼쪽의두개의막대는 HDFS와 Lustre를사용하는 BigBWA를각각사용하여 30GB의유전체원시데이터를지역정렬하는데소요되는시간을보여준다. HDFS로의복사에소요되는시간이없어지기때문에 Lustre에서 Hadoop 을사용하면 HDFS보다 30% 가량빠른것을확인할수있다. Lustre에 Hadoop을적용하는것만으로도실행시간이의미있게줄어들지만 BigBWA의불완전한병렬화로인한 I/O 오버헤드가여전히남아있다. 우리는 BigBWA를다시설계 하여 Lustre 특성을적극적으로활용하여모든 I/O를병렬화하였고그전체수행과정이 Fig. 1에요약되어있다. 기존의 BigBWA에서가장많은시간을소비하는부분은한쌍의 fastq 파일을 Hadoop 호환입력파일로병합하는과정으로단일노드에서수행되는 Python 스크립트로구현되어있다. 한세트의입력만받아들일수있는 Hadoop Mapper들이이병합된입력파일을여러노드에서분할하여읽은후각로컬디스크의임시디렉토리에저장하고 BWA를호출하여입력데이터로전달하여지역정렬을수행한다. KBigBWA에서는이러한시간소모적인데이터변환단계를추가적인 Mapper 단계로대체하였다. 두개의 Mapper 단계는두개의 fastq 파일을각각병렬로분리한다. 분리된데이터를이용하여 BWA를수행하기위해서각 BWA 인스턴스는동일한범위의분할된파일쌍에액세스할수있어야한다. 이를위해서두 Mapper 단계에서사용되는병렬프로세스의개수는동일해야한다. 또한분할된데이터를로컬디스크의 Hadoop temp디렉토리대신모든노드가공유하는 Lustre에서마운트된 shared_tmp 디렉토리에저장하도록하였다. 따라서 BWA 프로세스모두가 shared_tmp에있는필요한범위의데이터조각을읽어서처리할수있다. 또한 BWA의출력파일은 Lustre에직접기록된다. 각각의 BWA가생성한결과파일을분석파이프라인의다음단계에서사용하기위해서는하나의 sam 파일로병합해야한다. BigBWA에서제공하는 Hadoop reduce 또는 FullSam python 스크립트를사용하는두가지방법모두비병렬방식을사용하기때문에시간소모가크다. KBigBWA에서는여러노드가동시에 Lustre에대한병렬쓰기에참여하는 MPIIO를활용한병합도구를개발하였다. Fig. 2는 KBigBWA 의성능을 BigBWA 와비교한결과를보여준다. 입력데이터분할및출력데이터병합의병렬화를통해실행시간이 1/3 이하로단축하였고이는 HDFS 를사용하는 BigBWA 과비교해서는 1/5에불과하다. 또한단일노드에서수행한 BWA과비교해도시간을크게단축시켰음을확인하였다.

234 정보처리학회논문지 / 컴퓨터및통신시스템제 8 권제 10 호 (2019. 10) Fig. 2. Performance Improvement of KBigBWA with Hadoop on Lustre and Parallel I/O Functionality 3.2 중복검출단계병렬화지역정렬단계가완료되면 SAM 형식의파일이생성된다. Fig. 3의예제와같이 SAM파일에는참조유전체의염색체이름과길이정보가헤더에나타나고각리드의정렬 (alignment) 정보가매줄마다기록된다.

Paired-end read의경우데이터는각유전자조각을양쪽에서일정한크기만큼읽어내어생성한데이터이므로동일한 QNAME에서리드정렬정보가최소한 2개존재한다. 또한참조유전체에정렬되는위치가하나이상인경우도있을수있다. 이경우가장확률이높은정렬위치의쌍을 Primary line이라고한다.

Samblaster 알고리즘은 Read Group의 primary line의전역좌표값을비교하여중복을판단한다. 따라서중복검출의누락을방지하기위해이조건을고려하여병렬화를위해데이터를재분배기법을설계하였다. 각각의노드에서병렬로실행된 BWA는 SAM형식으로결과를출력하는데 Read Group이연속되어기록된다.

4 234 정보처리학회논문지 / 컴퓨터및통신시스템제 8 권제 10 호 ( ) Fig. 2. Performance Improvement of KBigBWA with Hadoop on Lustre and Parallel I/O Functionality 3.2 중복검출단계병렬화지역정렬단계가완료되면 SAM 형식의파일이생성된다. Fig. 3의예제와같이 SAM파일에는참조유전체의염색체이름과길이정보가헤더에나타나고각리드의정렬 (alignment) 정보가매줄마다기록된다. 이중 RNAME 값과 POS값을이용하면해당리드가참조유전체중어느염색체의어느위치에정렬되어있는지알수있다. 헤더에적힌참조염색체의순서와길이값을누적하면각참조염색체의오프셋을계산할수있고이값과 POS값을더해서정렬된위치의전역좌표를결정할수있다. 중복검출과색인단계에는이전역좌표값을사용한다. Fig. 3에서 QNAME 값은시퀀서에서읽은각조각의ID를나타낸다. Paired-end read의경우데이터는각유전자조각을양쪽에서일정한크기만큼읽어내어생성한데이터이므로동일한 QNAME에서리드정렬정보가최소한 2개존재한다. 또한참조유전체에정렬되는위치가하나이상인경우도있을수있다. 이경우가장확률이높은정렬위치의쌍을 Primary line이라고한다. 이렇게같은 QNAME을가지는여러개의리드정렬정보의집합 ( 이후 Read Group으로표현 Fig. 3. An Example of SAM File 함 ) 은동일한염기서열조각에서생성된데이터들로중복검출시함께처리되어야한다. Samblaster는 SAM파일을입력으로받는데이때같은 Read Group에속한리드들은반드시연속된라인으로함께입력되어야한다. Samblaster 알고리즘은 Read Group의 primary line의전역좌표값을비교하여중복을판단한다. 따라서중복검출의누락을방지하기위해이조건을고려하여병렬화를위해데이터를재분배기법을설계하였다. 각각의노드에서병렬로실행된 BWA는 SAM형식으로결과를출력하는데 Read Group이연속되어기록된다. 이결과물을읽어서 Read Group별로구분하고 primary line의전역좌표 2개중작은값을 Key값으로 read group의정렬정보전체를 value값으로결정한다. 그 Key값을기준으로데이터를분배 (partitioning) 하여 samblaster를수행하는노드들에전송한다. 이과정을통해각각의 samblaster 프로세스에는특정한범위에정렬된유전자조각들이모이게된다. 입력된 SAM형식의데이터에서중복으로판단된리드의 FLAG값만을수정한내용이결과로출력된다. Primary line의광역좌표를기준으로파티션을결정하였기때문에, non-primary 리드들의좌표가파티션의범위에해당하지않는경우가발생할수있다. Samblaster 수행후이러한리드들에대해다시한번광역좌표를기준으로맞는위치의파티션에전송하고, 현재파티션과일치하는리드들은로컬노드내에서다음단계의입력으로직접전달될수있다. 몇가지데이터셋을통해측정해본결과이렇게재분배되는비율은 1% 전후로적은양이어서소요시간이매우짧았다. 설령대부분이데이터가재분배되는경우에도 samblaster 병렬화를위해수행했던재분배프로세스에서소요되는시간과동일한시간복잡도를가지므로전체수행시간에큰영향을주지않을것으로예상된다. 3.3 정렬, 압축및병합단계병렬화다음으로모든리드정보를전역좌표를기준으로오름차순정렬 (sort) 을해야한다. 수억개의리드정보를한꺼번에정렬하는것은엄청난시간을필요로한다. 그러나이미 samblaster 병렬화단계에서전역좌표를기준으로데이터가분배되어있다. 이렇게분배되어있는데이터집합들각각을병렬로정렬 (sort) 하고난후, 각각의데이터집합들을순서에맞게연결시키기만하면전체정렬 (sort) 이완성된다. Samtools의 sort 기능을활용하면 sort, encoding, compress가한꺼번에수행되고결과물로 BAM 파일이생성된다. BAM 파일형식은 ASCII 텍스트형식인 SAM파일의용량을줄이는목적으로정의되었다. binary encoding을수행한후 gzip알고리즘의호환인 BGZF 포맷으로압축을진행한다. 이때데이터전체를한번에압축하지않고 64KB보다작은크기의블록으로데이터를나눈후각각을압축하고메타데이터에블록의크기, 전역위치정보들을포함하여향후인덱싱

빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 235 에활용한다. gzip의특성상독립적으로압축된파일인각각의블록을단순히연결해도 gzip파일이되고압축해제시연결한순서대로복원되는점을이용하였다. SAM파일의헤더내용을담은헤더블록과 EOF 블록이앞뒤에추가된다.

이렇게손질된파일의연결은 MPI-IO를이용하여 N-to-1병렬쓰기작업을통해병합을진행한. 따라서최종파일의크기가크더라도여러노드가동시에쓰기를수행하기때문에소요시간이크지않다. 마지막으로합쳐진 BAM파일에대하여 samtools의 index 기능을이용하여색인파일을생성한다.

파란화살표는데이터의전달과정을나타내며, 회색화살표는 MPI-IO를이용한병렬쓰기를나타낸다. 노란박스로표시된부분이병렬화한기존도구들이며, 붉은색으로표시한부분이새롭게개발한기능들이다. 시퀀서에서생성한원시데이터가 fastq 파일의쌍으로주어지면 KBigBWA가 Hadoop on Lustre를이용해지역정렬데이터를각각의노드에생성한다.

이들을병렬병합기능을이용해하나의 BAM파일로합치고 index파일까지생성하면 NGA데이터의전처리과정이완료된다. 결과물로지역정렬데이터 SAM파일하나지역정렬, 중복검출, 정렬및압축이모두완료된 BAM파일하나와그 index 파일하나가생성되고이는향후의유전체분석에활용될수있다. 각각의단계를실제로수행하기위해서는병렬프로세스를생성하고데이터를전달하는관리자가필요하다.

5 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 235 에활용한다. gzip의특성상독립적으로압축된파일인각각의블록을단순히연결해도 gzip파일이되고압축해제시연결한순서대로복원되는점을이용하였다. SAM파일의헤더내용을담은헤더블록과 EOF 블록이앞뒤에추가된다. 이렇게각각의 samtools 프로세스에서생성된 BAM파일을하나의전체 BAM 파일로병렬로연결하는기법을개발하였다. 앞서언급한 gzip 파일의특성에따라각파일내에서광역좌표를기준으로정렬되어저장된 BAM파일들을순서에맞게단순히연결하는것만으로전체정렬된파일을얻을수있다. BAM 파일을정상적으로합치기위해서는연결부위의헤더와 EOF블록을잘라내야한다. 이렇게손질된파일의연결은 MPI-IO를이용하여 N-to-1병렬쓰기작업을통해병합을진행한. 따라서최종파일의크기가크더라도여러노드가동시에쓰기를수행하기때문에소요시간이크지않다. 마지막으로합쳐진 BAM파일에대하여 samtools의 index 기능을이용하여색인파일을생성한다. 이과정은 100GB 데이터의경우수분정도소요되는작업으로전체수행시간대비비중이크지않고 samtools의수정없이 O(1) 병렬화가어렵기때문에본연구에서는따로병렬화하지않았다. 3.4 병렬프로세스관리및데이터재배치방법 Fig. 4에본논문에서제안한 NGS 데이터의전처리병렬화기법의전체수행과정이정리되어있다. 파란화살표는데이터의전달과정을나타내며, 회색화살표는 MPI-IO를이용한병렬쓰기를나타낸다. 노란박스로표시된부분이병렬화한기존도구들이며, 붉은색으로표시한부분이새롭게개발한기능들이다. 시퀀서에서생성한원시데이터가 fastq 파일의쌍으로주어지면 KBigBWA가 Hadoop on Lustre를이용해지역정렬데이터를각각의노드에생성한다. 이데이터는 Read Group별로 primary line의광역좌표를기준으로재분배되고각각의노드에서 samblaster를이용해중복리드를검출한다. 이후각리드의광역좌표를기준으로위치조정을다시수행한후각각의노드에서 samtools sort를이용해정렬압축된 BAM파일을생성한다. 이들을병렬병합기능을이용해하나의 BAM파일로합치고 index파일까지생성하면 NGA데이터의전처리과정이완료된다. 결과물로지역정렬데이터 SAM파일하나지역정렬, 중복검출, 정렬및압축이모두완료된 BAM파일하나와그 index 파일하나가생성되고이는향후의유전체분석에활용될수있다. 각각의단계를실제로수행하기위해서는병렬프로세스를생성하고데이터를전달하는관리자가필요하다. KBigBWA 에서는 Hadoop의병렬자원및프로세스관리기능을사용하였다. Hadoop을사용하면자동으로클러스터에프로세스를생성하고병렬로데이터분석작업을시작할수있다. 단, Java로구현된 Hadoop API와호환되도록기존의분석도구를수정할필요가있다. BigBWA가이러한기능을이미구현해놓은상황이었기때문에어렵지않게적용이가능하였다. Fig. 4. Whole Process of NGS Data Preprocessing Hadoop을사용하지않는방법으로는 Spark을사용하는방법이있다. 이경우에도분석도구의수정이필요하다. Hadoop 과 Spark과같은도구를사용하는방법은병렬작업의관리및장애복구등에장점이있는반면실행파일의수정, 프레임워크와 API 단계로인해발생하는성능오버헤드등의단점이있다. 이러한단점을가장해결하기위해가장가벼운방법으로작업을병렬수행시키는방법은 GNU parallel을사용하는것이다. GNU parallel은 SSH로연결된클러스터에병렬작업을손쉽게실행할수있도록해준다. 간단히 Hadoop, Spark, GNU parallel을사용하여 BWA의병렬수행의시간을비교해본결과 GNU parallel을사용하는것이 5% 이상수행시간이빠르다는것을확인하였다. 따라서본논문의범위에서는 samblaster와 samtools 를이용하는단계에서는 GNU parallel을이용한병렬프로세스수행방식으로구현을하고성능분석을진행하였다. 그러나앞서언급한것처럼빅데이터자원및프로세스관리프레임워크의장점들을활용하는것이전체소프트웨어의안정성에도움이되기때문에전체병렬화된전처리과정을 Spark으로구현하는작업을함께진행중이다. 또다른중요한고려사항은데이터재분배과정의효율적인설계이다. Hadoop 프레임워크에서는이과정을 shuffle이라고하고기본기능으로포함되어있다. 위에서언급한바와같이본논문에서구현한방식에서는 GNU parallel을사용하였기때문에데이터전송및수집을위한가벼운도구를몇가지방식으로개발하였다. 첫번째는 OS에서제공하는파이프와소켓을사용하는방식이다. 지역정렬단계에서중복검출로데이터를전달하는과정의경우 BWA의결과로나오는 SAM포맷의결과물을파이프로전달받는프로세스들이실행되고이들로부터데이터를 TCP소켓통신을통해전달받아파이프를통해각 samblaster 의입력으로전달하는프로세스들이실행되게된다. N개의

6 236 정보처리학회논문지 / 컴퓨터및통신시스템제 8 권제 10 호 ( ) BWA 인스턴스와 M개의 samblaster 인스턴스가실행될때 N+M개의전달프로세스와 N*M개의연결이필요하다. 이러한방식의장점은데이터전달과정이매우간단하고추가적인저장공간을사용하지않으며, 전단계와다음단계가동시에수행되면서파이프라이닝을통해자원사용효율을극대화시킨다는점이다. 그러나대규모클러스터에서아주많은인스턴스를이용하여병렬화를하는경우소켓의크기가관리하기어려울정도로많아져서오히려 OS 및메모리부하로인해성능이떨어질우려가있다. 이를해결하기위한방법으로 ZeroMQ나 Kafka와같은메세징소프트웨어를사용하는방법이있다. 각소프트웨어가제공하는프로토콜에맞도록데이터를가공해야하고메세징프레임워크를설정해야하는단점이있지만보다안정적인데이터전송이가능하다는장점이있다. 또다른해결방식은공유스토리지에중간생성파일을저장하여단계사이의데이터를전달하는방식이다. 이경우본논문에서가정한고성능컴퓨팅환경의병렬파일시스템을적극적으로활용하여확장성이나안정성이확보된다는장점이있으나임시저장공간이필요하고, 전단계의병렬작업끝난이후에다음단계의작업을시작해야하는경우가생길수있어서, 프로세스사이에직접통신을하는방식에비해시간이조금더걸릴수있다. 세가지방식을 8대규모의클러스터에서 100GB 크기의데이터를이용하여테스트해본결과파이프와소켓을사용하는방식이가장시간이적게걸리는것으로나타났다. 다만, 이는클러스터의크기가크지않았기때문에단점이드러나지않았기때문일가능성이있다. 그리고공유스토리지를사용하는방식과시간차이도 10% 이내로크지않았다. Kafka를사용하였을때에는설정값에따라성능과안정성이변동이있었다. 마지막으로고려해볼수있는방식은 Spark을사용하는것이다. 데이터처리프로세스가병렬화되면서 RDD 사이에자동으로데이터재분배가이루어진다. 특히 Spark-stream을사용하면간단계가파이프라이닝되어수행되므로더빠른수행이가능해질수있다. 구성하였다. 각계산노드에는듀얼소켓 10 core Xeon E CPU와 80GB 메모리가설치되어있으며, 각각의스토리지노드에는 40개의하드디스크가 4개의 RAID6 스토리지타겟으로구성되어있다. 아래 Figs. 5, 6은크기가각각 102GB, 208GB인유전체리드원시데이터들의전처리에소요되는시간을보여주고있다. 그래프의맨왼쪽부분은기존의방법으로하나의노드에서 BWA, samblaster, samtools를연속으로실행할때의소요시간을나타낸다. 이때, 멀티스레드옵션을활성화하여 20개의코어를최대한활용하도록하였다. 오른쪽의두결과는본논문에서제시한병렬화기법을이용하여각각 4대, 8대의노드에서병렬로수행하였을때의결과를나타낸다. BWA는 KBigBWA를통해 Hadoop on Lustre를통해병렬로수행되며 samblaster와 samtools는 GNU parallel 을이용하여각각의노드에서작업을나누어처리한다. 각단계사이에서의데이터재배치및전송은 IPoIB 소켓통신을통해이루어지고, 파일을병합하는과정은 MPI-IO를이용해병렬화하였다. 각단계에 Fig. 5. Breakdown of Execution Time of Preprocessing 208GB NGS Data with Parallel Mechanism 4. 성능 본연구의목적은복수의노드로이루어진클러스터를활용하여수행시간을단축시키는방법을제안하는것이다. 따라서실험을통해더많은노드로사용하면수행시간을더많이단축시킬수있음을확인하고자하였다. 3장에서설명한전처리프로세스를실행가능한프로그램으로구현하고이를병렬클러스터위에서실제유전체원시데이터를이용하여전처리를수행하는과정의전체및각단계의시간을측정하였다. 클러스터는 FDR Infiniband로연결된여덟대의계산노드와 2대의스토리지노드로구성된 Lustre파일시스템으로 Fig. 6. Breakdown of Execution Time of Preprocessing 105GB NGS Data with Parallel Mechanism

빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 237 서노드당 5개의작업프로세스가병렬로데이터처리작업을처리한다. 멀티스레딩이가능한 BWA와 samtools는각프로세스마다 4개의스레드를사용하여모든노드의코어를최대한사용하였다. 실험을통해모든전처리단계를병렬화함으로써더많은자원을투입하면전처리속도를유의미하게향상시킬수있음을확인하였다.

분석의종류에따라서실험에서사용한데이터보다수배이상큰데이터를실제로사용하는경우도존재하기때문에병렬자원을투입하여소요시간을단축시키는것의이점이더부각될수있을것이다. 5. 결론본연구를통해 Lustre, MPIIO 등 HPC 기술을적극적으로적용하여병렬자원을활용하여유전체시퀀스데이터의전처리과정을소요시간을크게감소시킬수있는병렬화하는기법을제안하고구현및실험을통해입증하였다.

7 빅데이터및고성능컴퓨팅프레임워크를활용한유전체데이터전처리과정의병렬화 237 서노드당 5개의작업프로세스가병렬로데이터처리작업을처리한다. 멀티스레딩이가능한 BWA와 samtools는각프로세스마다 4개의스레드를사용하여모든노드의코어를최대한사용하였다. 실험을통해모든전처리단계를병렬화함으로써더많은자원을투입하면전처리속도를유의미하게향상시킬수있음을확인하였다. 데이터재배치과정에서추가되는시간은병렬화를통해얻는이득에비해크지않다고판단된다. 또한두방식으로생성된결과물을비교하였을때데이터처리순서의변경으로인해발생하고최종분석에영양을미치지않는오차를제외하고는동일한결과물을생성하는것을확인하였다. 분석의종류에따라서실험에서사용한데이터보다수배이상큰데이터를실제로사용하는경우도존재하기때문에병렬자원을투입하여소요시간을단축시키는것의이점이더부각될수있을것이다. 5. 결론본연구를통해 Lustre, MPIIO 등 HPC 기술을적극적으로적용하여병렬자원을활용하여유전체시퀀스데이터의전처리과정을소요시간을크게감소시킬수있는병렬화하는기법을제안하고구현및실험을통해입증하였다. 이기법을이용하여응급환자의진단등시급성이요구되는상황에서고성능의병렬자원을이용하여유전변이검출프로세스의효율성을크게증가시킬수있다. 유전정보를의료진단및치료에활용하고자하는요구사항및시장의크기는점점더커질것으로예상된다. 본연구에서제안한병렬화를기법을통한유전체분석시간의단축이대형병원등의료업계에서유전체분석정보를활용하는서비스의폭을넓힐수있을것으로기대된다. References [1] S. Goodwin, J. D. McPherson, and W. R. McCombie, Coming of age: ten years of next-generation sequencing technologies, Nature Review Genetics, Vol.17, No.6, pp , May [2] Sequence Alignment/Map Format Specification, The SAM/ BAM Format Specification Working Group [Internet], [3] An introduction to Next-Generation Sequencing Technology, Illumina, Inc., [Internet], products/illumina_sequencing_introduction.pdf [4] H. Li and R. Durbin, Fast and accurate long-read alignment with Burrows-Wheeler transform, Bioinformatics, Vol.26, No.5, pp , [5] Faust, Gregory G., and Ira M. Hall, SAMBLASTER: Fast Duplicate Marking and Structural Variant Read Extraction, Bioinformatics, Vol.30, No.17, pp , [6] H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan, N. Homer, G. Marth, G. Abecasis, R. Durbin, and 1000 Genome Project Data Processing Subgroup, The Sequence Alignment/Map format and SAMtools, Bioinformatics, Vol.25, No.16, pp , [7] L. Pireddu, S. Leo, and G. Zanetti, SEAL: a distributed short read mapping and duplicate removal tool, Bioinformatics, Vol. 27, No.15, pp , Aug [8] T. Nguyen, W. Shi, and D. Ruden, CloudAligner: A fast and full-featured MapReduce based tool for sequence mapping, BMC Res Notes, Vol.4, No.1, pp.171, Jun [9] M. C. Schatz, CloudBurst: highly sensitive read mapping with MapReduce, Bioinformatics, Vol.25, No.11, pp , Jun [10] J. M. Abuín, J. C. Pichel, T. F. Pena, and J. Amigo, BigBWA: approaching the Burrows-Wheeler aligner to Big Data technologies, Bioinformatics, Vol.31, No.24, pp , [11] D. Decap, J. Reumers, C. Herzeel, P. Costanza, and J. Fostier, Halvade: Scalable Sequence Analysis with MapReduce, Bioinformatics, Vol.31, No.15, pp , [12] E.-K. Byun, J. Lee, S. J. Yu, J.-H. Kwak, and S. Hwang, Accelerating Genome Sequence Alignment on Hadoop on Lustre Environment, 2017 IEEE 13th International Conference on E-Science, pp , [13] Lustre Hadoop Plugin, Seagate [Internet], com/seagate/lustrefs 변은규 ekbyun@kisti.re.kr 2003년한국과학기술원전산학과 ( 학사 ) 2011년한국과학기술원전산학과 (Ph.D., 석 박사통합 ) 2011년~2012년 SK텔레콤매니저 2013년~현재한국과학기술정보연구원선임연구원관심분야 : 분산병렬시스템, 빅데이터, HPC, 스토리지시스템 곽재혁 jhkwak@kisti.re.kr 2001년아주대학교정보및컴퓨터공학부 ( 학사 ) 2003년서울대학교전기및컴퓨터공학부 ( 석사 ) 2003년~현재한국과학기술정보연구원선임연구원관심분야 : 분산컴퓨팅, 고성능컴퓨팅, 빅데이터컴퓨팅

238 정보처리학회논문지 / 컴퓨터및통신시스템제 8 권제 10 호 (2019. 10) 문지협 https://orcid.org/0000-0002-5683-6021 e-mail : munji@kisti.re.

8 238 정보처리학회논문지 / 컴퓨터및통신시스템제 8 권제 10 호 ( ) 문지협 munji@kisti.re.kr 2009년동국대학교컴퓨터공학과 ( 학사 ) 2011년동국대학교컴퓨터공학과 ( 석사 ) 2017년과학기술인연합대학원대학교 (UST) 기능유전체학 ( 박사 ) 2017년~현재한국과학기술정보연구원선임연구원관심분야 : 차세대염기서열분석

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1