De novo assembly is a vital process in modern genomics that recovers the genomes from short DNA fragments. For the recovery, it first constructs the assembly graph that represents the overlap between different fragments and then concatenates the overlapped fragments by traversing the assembly graph. However, the input genomic datasets for de novo assembly often include a large genome or thousands of small genomes, making the corresponding assembly graph at a massive scale. To this end, this dissertation proposes OC-assembler, a de novo assembly framework that stores the assembly graph in storage and processes the graph in an out-of-core fashion. OC-assembler introduces a new graph data structure that reduces the memory footprint by considering the double-stranded structure of an input genome, thereby significantly reducing the storage I/O. Further, OC-assembler efficiently handles the iterative graph update of the de novo assembly by storing a small update log instead of overwriting the entire graph in storage when the amount of updates is small. Our evaluation on diverse genome datasets shows that OC-assembler reduces the storage I/O by 2.9×, thereby shortening the execution time by 2.1× compared to existing out-of-core graph processing methods.
디 노보 어셈블리는 유전자 추출 기기에서 읽은 유전자 단편을 원본 유전자로 복구하는 유전체학의 핵심 작업이다. 디 노보 어셈블리는 단편으로부터 유전자를 복구하기 위해 서로 다른 단편 간의 중첩을 어셈블리 그래프에 표현하고 그래프를 탐색하여 중첩된 단편을 연결한다. 한편, 디 노보 어셈블리가 다루는 유전자 데이터셋은 큰 단일 유전자나 수 천 개의 유전자를 포함하여 이로부터 생성되는 어셈블리 그래프의 크기가 매우 크다. 본 학위 논문은 대규모 유전자 데이터셋을 처리하기 위해 스토리지에 어셈블리 그래프를 저장하고 처리하는 디 노보 어셈블리 프레임워크인 아웃-오브-코어 어셈블러(OC-assembler)를 제안한다. 제안하는 프레임워크는 입력 유전자의 이중 나선 구조를 고려하여 그래프의 용량을 줄이는 새로운 자료구조를 통해 스토리지 입출력을 줄인다. 또한, 제안하는 프레임워크는 디 노보 어셈블리의 반복적인 그래프 변경을 효율적으로 처리하기 위해, 변경이 적은 경우 전체 그래프를 스토리지에 갱신하는 대신 변경 내역만을 로그 형태로 저장하여 입출력 양을 줄인다. 다양한 유전자 데이터셋에 대해 진행한 평가에서 제안하는 프레임워크는 기존 아웃-오브-코어 그래프 프레임워크 대비 스토리지 입출력을 2.9배 줄여 2.1배 짧은 실행 시간을 보였다.
