차세대 염기서열 정렬 도구 소개
Introduction to next generation sequencing alignment tools

질병관리본부 유전체센터 바이오과학정보과            
최종필           
  

Ⅰ. 들어가는 말
     유전체(genome)는 생물체에 있는 유전자(gene)를 포함하는 모든 DNA(deoxyribonucleic acid)를 의미하고 생물체를 만들고 생명을 유지하기 위해 필요한 모든 생물학적 정보를 갖고 있다. 한 생명체의 유전체 정보를 파악한다는 것은 그 생명체의 생명현상을 이해하고 유전자형과 표현형(유전자와 환경의 영향에 의해 형성된 생물의 형질) 사이의 관계를 이해하는데 중요한 역할을 한다. 예를 들어 혈류에 있는 과잉 콜레스테롤을 제거하도록 간세포에게 지시하는 어떤 유전자가 있다면 이 유전자는 간세포에게 특정 단백질을 만들도록 지시하고 만들어진 단백질이 과잉 콜레스테롤을 제거하는 일을 수행하게 된다. 그런데 만약 이 유전자가 돌연변이(mutation) 또는 변형(change)될 경우 생성된 단백질이 올바르게 작동하지 않거나 전혀 만들어지지 않을 수 있어 과도한 콜레스테롤을 제거하지 못하게 된다[1]. 이러한 가족성 고(高)콜레스테롤 혈증과 연관 있는 유전자의 위치를 발견하고 변형을 발견하기 위해 유전체의 염기서열을 알아내는 것이 중요하다.
  대부분의 유전체 프로젝트의 목적은 유전체(genome)의 DNA 염기서열(sequence)을 알아내어 유전체의 유전자와 다양한 구조적 특징에 대한 특성을 찾는 것이다. 미국 에너지부(Department of Energy; DOE)와 국립보건연구원(National Institutes of Health; NIH)에서 30억 달러 정도의 예산을 가지고 1990년에 시작되어 2003년에 완료된 인간게놈프로젝트(Human Genome Project; HGP)[2]는 처음으로 많은 수의 기증자로부터 얻어진 염기서열을 조립하여 인간의 유전체 염기서열을 구축하였다. 이 염기서열은 많은 수의 기증자로부터 얻어진 염기서열이기 때문에 어느 개인의 유전적 코드를 대표하지는 못 하지만 참조 유전체(reference genome)로 HGP보다 매우 빠르고 저렴하게 새로운 유전체를 만드는 것을 가능하게 한다.
  차세대 시퀀싱 기술(next-generation sequencing; NGS)의 출현과 DNA 시퀀싱(sequencing; 염기서열 해독)의 비용이 저렴해지면서 의학 유전학(medical genetics)과 집단 유전학(population genetics) 연구를 위해 대규모로 인간 유전체 염기서열의 생산이 가능하게 되었다. 1000게놈프로젝트(1KG; 1000 Genome Project)[3]와 암게놈아틀라스(The Cancer Genome Atlas; TCGA)[4] 같은 프로젝트의 경우 대규모로 DNA 시퀀싱을 수행하여 많은 수의 개인 유전체 염기서열을 얻고 이를 기반으로 인간의 유전적 다양성의 완전한 스펙트럼을 알아내고자 진행되고 있다. 이러한 프로젝트에 사용된 NGS 시퀀서는 길이는 매우 짧지만 수십억 개의 단편서열(short read)을 생산할 수 있다. 각 개인의 유전체 서열은 생산된 단편서열을 참조 유전체의 어느 곳에 위치하는지 결정하는 얼라이닝(aligning) 또는 맵핑(mapping) 작업을 통하여 만들어진다. BLAST(Basic Local Alignment Search Tool)[5]와 같은 기존 도구를 이용하여 맵핑 작업을 수행할 경우 너무 많은 시간이 걸리기 때문에 이 문제를 해결하고자 많은 연구자들이 다양한 방법을 제안하였다. 이 글에서는 NGS의 다양한 응용 분야에서 기본이 되는 차세대 염기서열 정렬 도구를 소개하고자 한다.

Ⅱ. 몸 말
    대부분의 고속의 정렬 알고리즘은 맵핑 속도를 높이기 위해 ‘인덱싱’이라는 보조 자료구조를 생성한다. 책의 끝에 있는 색인처럼 커다란 DNA 염기서열의 색인은 짧은 염기서열(short reads)이 DNA 염기서열 안에 위치한 곳을 빠르게 찾는 것을 가능하게 한다. 색인의 종류에 따라 정렬 알고리즘을 분류하면 크게 해쉬 테이블(hash tables) 1) 기반의 알고리즘과 서픽스 트리(suffix trees) 2) 기반의 알고리즘으로 나눌 수 있다.

가. 해쉬 테이블 기반의 정렬 도구
  해쉬 테이블 색인을 구축하는 방법은 알고리즘마다 조금씩 다를 수 있지만 일반적으로 색인 대상의 염기서열의 각 위치를 동일 길이의 k-tuple(또는 k-mer) 3)으로 잘라 위치 정보와 함께 해쉬 테이블에 저장하여 색인을 구축한다. DNA의 각 염기는 A, C, G, T이기 때문에 k-tuple의 수는 최대 4**k가 되고 위치 정보의 수는 염기서열의 길이에 가깝게 된다. 그리고 알고리즘에 따라 참조 유전체의 색인을 구축하거나 질의 염기서열(query sequence)의 색인을 만든다. 해쉬 테이블 기반의 정렬은 질의 염기서열과 참조 유전체의 염기서열 사이의 정확히 일치하는 부분(seed)을 해쉬 테이블을 이용하여 찾고 그 곳을 기준으로 정렬을 수행한다. 이러한 방법을 “seed-and-extend” 라 한다.
  Bin Ma[7]는 k개의 비연속적인 문자를 seed로 사용하는 것을 제안하고 k개 문자의 상대적 위치를 모델(model)으로 k를 모델의 가중치라고 정의하였다. 예를 들어 가중치 6의 모델 1110111의 경우 “actgact”와 “actgact” 뿐만 아니라 “actgact”와 “acttact”도 seed 일치한다. 이렇게 정의된 spaced seed는 연속적으로 일치하는 고전적인 seed와 비교하여 민감도의 향상을 보인다고 보고되었다.

1) Eland (Efficient Local Alignment of Nucleotide Data)
  Eland는 일루미나(Illumina)사의 GA(Genomics Analysis) 파이프라인 소프트웨어의 일부로 개발된 정렬 도구로 seed 템플릿을 6개 사용하여 최대 2개의 비 일치(mismatch)를 허용하지만 갭(gap)은 허용하지는 않는다[URL: http://bioinfo. cgrb.oregonstate.edu/docs/solexa/].

2) Soap (Short Oligonucleotide Alignment Program)
  Soap은 Eland와 비슷하지만 short read를 대신에 유전체를 색인한다. 그리고 적은 수(1-3)의 gap과 mismatch만을 허용한다. [URL: http://soap.genomics.org.cn/]

3) Maq (Mapping and Assembly with Quality)
  Maq는 k-mismatches(k개의 비 일치)를 허용하지만 2kCk개의 템플릿이 필요하여 k가 커지면 템플릿의 수가 지수적으로 증가하는 문제가 있다. 속도 향상을 위해 각 read의 첫 번째 28bp 안에서 2-mismatch를 찾는 것만 보장한다[URL: http://sourceforge.net/projects/maq/].

4) RMAP
  염기서열의 길이가 20-64 bp인 Illumina의 단편 서열을 참조 유전체에 정렬하는 도구로 k-mismatches를 허용하는데 k+1개의 seed 템플릿이 필요하다. 하지만 k가 클 경우 각 템플릿의 가중치가 작아져 해쉬 테이블 색인의 장점을 충분히 살릴 수 없다[URL: http://rulai.cshl.edu/rmap/].

5) BFAST (Blat-like Fast Accurate Search Tool)
  BFAST는 다중 색인을 이용하고 gap을 허용하는 spaced seed 기반의 정렬 도구이다. [URL: http://bfast. sourceforge.net]

6) SHRiMP (SHort Read Mapping Package)
  SHRiMP는 spaced seed 기반으로 BLAST와 다르게 여러 seed를 이용하여 적합한 일치하는 영역을 찾고 벡터화된 Smith-Waterman 4)정렬 알고리즘을 이용하여 필터링 작업을 수행하고 최종적으로 Smith-Waterman 성적이 상위에 있는 위치에서 정렬을 수행한다. 이 도구의 특징은 AB SOLiD사에서 제공하는 color-space 데이터도 지원하는 것이다[URL: http://compbio.cs.toronto.edu/shrimp/].

7) SSAHA2 (Sequence Search and Alignment by Hashing Algorithm)
  DNA 데이터베이스에서 거의 정확하게 일치하는 것을 빠르게 찾아주는 SSAHA를 기반으로 NGS 염기서열의 정렬를 수행하는 도구이다. SSAHA2는 길이가 긴 read에 대하여 정렬를 수행하는데 좋은 도구이다[URL: http://www.sanger.ac.uk /resources/software/ssaha2/].

나. 서픽스 트리(suffix trees) 기반의 정렬 도구
  서픽스 트리는 문자열의 모든 서픽스를 포함 하는 트리로 문자열 관련 연산을 매우 빠르게 수행할 수 있는 데이터 구조이다. 하지만 서픽스 트리는 원본 문자열을 서픽스 트리로 구축할 경우 완성된 서픽스 트리의 크기가 매우 커지는 문제점을 갖고 있다. 이러한 문제점을 극복하기 위한 많은 노력이 있었고 그 중 서픽스 어레이(suffix array)는 사전상으로 정렬된 서픽스의 시작 위치를 저장하는 자료 구조로 서픽스 트리와 비교하여 적은 공간이 소요된다. BWT(Burrows-Wheeler Transform) 5)는 본래 데이터 압축을 위해 개발된 것이나 필요한 메모리 공간이 매우 적어 현재 많은 차세대 염기서열 정렬 도구에 적용되고 있다. 서픽스 트리, 서픽스 어레이, BWT 기반 색인은 모두 문자열의 서픽스를 저장하는 데이터 구조로 부분 문자열이 원래 문자열에 여러 곳에 나타나더라도 한번에 찾을 수 있는 장점을 갖는다.

1) Bowtie
  Bowtie는 참조 유전체를 BWT(Burrows-Wheeler Transform)을 이용하여 색인을 함으로써 인간의 유전체(약 3GB)를 2.2 GB의 메모리에 유지할 수 있다. 그리고 이 도구는 시간당 길이가 35 bp read를 1,200만개 처리할 정도로 빠르게 정렬를 수행할 수 있다[URL: http://bowtie-bio.sourceforge.net/index.shtml].

2) BWA/ BWA-SW (Burrows-Wheeler Aligner)
  길이가 200bp 보다 짧은 read를 정렬하는 BWA와 길이가 200bp - 100kbp 인 read를 정렬하는 BWA-SW이 있다. 이들 도구는 모두 BWT를 이용하여 참조 유전체를 색인하여 인간과 같은 커다란 유전체도 적은 메모리 공간에서 정렬을 수행하는 것이 가능하다. 그리고 gap을 허용한다[URL: http://bio-bwa.sourceforge.net/].

3) MUMmer
  MUMmer는 서픽스트리 데이터 구조에 참조 유전체를 색인하고 seed-and-extend 방법으로 정렬을 수행하는 도구이다. MUMmer는 참조 유전체의 1bp 당 17bytes의 메모리 공간을 필요하기 때문에 인간의 유전체와 같은 커다란 유전체에 대하여 정렬을 수행하는데 어려움이 있다[URL: http://mummer. sourceforge.net/].

4) Vmatch
  Vmatch는 서픽스어레이(suffix array) 데이터 구조를 이용하여 MUMmer와 비교하여 메모리를 절약할 수 있다. 그리고 생성된 색인을 이용하여 다양한 염기서열 맷칭 작업을 수행할 수 있다[URL: http://www.vmatch.de/].

Ⅲ. 맺는 말

    차세대 시퀀싱 기술(NGS)의 발전으로 저비용으로 대규모 시퀀싱이 가능해졌고 이를 활용한 다양한 연구가 진행되고 있다. 하나의 샘플로부터 얻어질 수 있는 단편의 염기서열(short read)의 수는 플랫폼에 따라 수백만에서 수십억 개가 되고 이를 참조 유전체에 맵핑(정렬)하는 도구가 위에서 설명한 것처럼 많이 개발되었다. 하지만 현재 개발된 대부분의 도구는 짧은 read에 특화된 정렬 도구로써 단편의 길이가 길어질 경우 기대한 수준의 성능을 낼 수 없다. 또한 대부분의 도구는 gap의 허용 범위가 제한적으로 참조 유전체와 상당히 다른 유전체를 시퀀싱할 경우 올바르게 맵핑하는 것이 어려운 문제점을 갖고 있다. 그리고 차세대 시퀀싱 기술이 지속적으로 발전하고 있다. 이러한 문제점을 해결하고 기술의 발전에 발맞춰 효율적이며 효과적인 정렬 도구의 개발이 지속적으로 이루어져야 한다.

1) 해쉬 테이블은 키(key)와 값(value)을 저장하는 데이터 구조이다. 해쉬 함수는 주어진 키에 대응하는 값이 저장된(될) 위치(색인)를
   구해주는 함수이다.
2) 서픽스 트리는 문자열 S의 모든 서픽스를 트리에 저장하는 데이터 구조이다.
3) k-tuple은 k개의 문자로 이루어진 문자열이다. 예를 들어 문자열 S = banana 이고 k = 4로 주어질 때 S에 있는
   모든 4-tupledms {bana, anan, nana}이다.
4) Smith-waterman 알고리즘은 두 서열 사이의 유사한 영역을 찾는 알고리즘이다.
5) BWT는 1994년 Michal Burrows and David Wheeler에 의해 개발된 텍스트 변환 알고리즘이다. 이 알고리즘으로 변환된 텍스트는 일반
   적으로 원본 텍스트를 압축하는 것 보다 좋은 효율로 압축되는 특성을 갖는다. 현재 이 알고리즘은 압축뿐만 아니라 검색분야에도 많이
   활용되고 있다.

Ⅳ. 참고문헌

1. MOLECULAR GENETICS: PIECING IT TOGETHER. http://www.ncbi.nlm.nih.gov/About/primer/genetics_molecular.html
2. Human Genome Project. http://www.ornl.gov/sci/techresources/ Human_Genome/home.shtml
3. 1000 Genomes. http://www.1000genomes.org/home
4. The Cancer Genome Atlas (TCGA). http://biospecimens. cancer.gov/relatedinitiatives/overview/tcga.asp
5. Altschul SF, Gish W, Miller W, et al. Basic local alignment search tool. JMol Biol 1990 215:403-10.
6. Li H, Homer N. A survey of sequence alignment algorithms for next generation sequencing. Brief Bioinfor0m 2010 11: 473-483.
7. Ma B, Tromp J, Li M. PatternHunter: faster and more sensitive homology search. Bioinformatics 2002 18:440-5.