[NGS Alignment] BWT 알고리즘

BWT 알고리즘 Start.

BioinformaticsAndMe

Alignment라는 과정은 Human 분석에서 특히 빡세다..

시퀀싱을 통해서 얻은 길지 않은 리드로 30억 염기서열과 매칭하는 일은 쉽지 않아보인다.

(음. Pacbio나, 요즘핫해보이는? Nanopore는 리드 길이가 길다)

NGS sequence를 alignment하는 tool로  bowtie 와 BWA 가 널리 알려져 있다. 이 tool들이 주력으로 사용하는 알고리즘은 Burrows-Wheeler Transform이다. 30억 염기서열 중에 ACGTACGTACGT를 align하기 위해서 모든 sequence를 처음부터 검색하면 시간이 매우 오래 걸린다. 이를 해결하기 위해서 사용한 알고리즘이 BWT이다.

BWT(Burrows-Wheeler Transform)

마이클 버로우즈와 데이비드 휠러가 1994년에 발표한 블록 정렬 알고리즘으로 변환 결과에 Index 정보가 포함되어 있어, 다른 정보가 없더라도 변환된 문자열의 경우 유사한 문자열들끼리 뭉쳐진 형태로 나타나는 경우가 많아 압축을 위한 전처리 알고리즘으로 사용된다.

#BWT 과정을 이해해보자.

1. 변환하고자 하는 문자열 ( BANANA )의 맨 마지막에 단어의 끝을 알리는 토큰을 넣는다 ( ex. BANANA$ ).

2. 토큰을 넣은 문자열을 왼쪽으로 한 칸씩 Cyclic Shift를 수행하며 행렬을 생성한다.

3. 생성된 행렬의 각 행을 사전 순으로 Sorting 한다 ($ 토큰은 맨 마지막 순서). 이때 정렬된 형태의 행렬을 BW행렬이라고 한다.

4. 정렬된 행렬의 맨 마지막 열의 문자들로 생성된 문자열이 변화된 결과이다.

#그래서 BWT 특징이 뭐야

Ⅰ. 같은 single nucleotide끼리 붙어있는 경우의 수 증가

transform 전과 후의 문자열 길이는 사실 변함은 없다. 따라서 직접적으로 압축을 수행하는 알고리즘이 아니다. 하지만 input 안에서 중복되는 문자열이 많을수록 single character가 반복되는 경우가 생기기 때문에 압축하기가 매우 용이해진다.

특히 DNA, RNA sequence는 문자열이 A, C, G, T, U 정도밖에 없기 때문에 BWT로 transform 할 경우, 반복되는 문자가 굉장히 많아진다.

예를 들어, 다음의 문자열의 경우 단 하나도 연속되는 single nucleotide가 없는 input이다.

ACGTGCAGTCGATGCGATCGATGCTGACTGATGCAGCTGACTG

하지만 위의 sequence를 Burrow-Wheller Transform으로 변환하면 다음과 같다.

GGGCCGGGGGGGTTAAGGATTTCTCCTTTATACGACCCCAGAA

Ⅱ. 문자의 순서가 유지

#BWT를 이용한 문자열 매칭

-원래 문자열은 $를 제외한 row의 수와 일치하므로 6개의 글자로 이루어진 단어임을 알 수 있음.

-문자의 순서 유지.

-First column은 last column의 뒤에 있었던 문자.

-$는 원래 문자의 맨 마지막에 붙어 있었음. 따라서 A가 맨 마지막 글자임을 알 수 있음.

-알아낸 문자열 : A$

-Last column과 First column의 문자의 순서는 동일함.

-A0의 앞에는 N0임을 알 수 있음.

-알아낸 문자열 : NA$

-L은 F앞의 문자임.

-$는 원본이 아니기 때문에 역변환 종료.

-알아낸 문자열 : BANANA$

#Bowtie (FM-Index)

Bowtie 알고리즘인 FM-Index는 BWT 행렬의 Last First mapping 법칙을 이용하여 문자열 Index를 만든 방법으로 문자열에 대해 BWT를 수행함으로써 얻어짐.

-참고 : Bowtie의 불일치 정합은 그리디(greedy) 알고리즘 형태의 백트래킹(backtracking)을 통해 수행되는데, 이 때 허용되는 에러는 치환 (substitution) 뿐이다. (내가 보고싶은게 InDel variant인데 bowtie를 쓴다면? 써도되겠지만 나는 안쓸란다)

#BWA (BWT + Suffix array)

BWA는 BWT와 접미사 배열(Suffix array)을 이용하여 정렬을 수행하는 알고리즘.

-참고 : BWA MEM 이 성능이 좋다고 평가되어 Alignment 과정에서 가장 빈번하게 사용된다 (빠르고, 정확). 옵션 중에 지금 기억이 안나는데, 특정 파라미터를 조절하면 (불일치스코어 매기는거였나) InDel 찾는 성능이 좋아진다. (읽었던 파라미터 비교 관련 논문을 본 것같은데 확인하고 내용 보완해야겠다ㅜ)

마무리..

BWT 알고리즘 말고도, HASH 기반에 MAQ, STAMPY 같은 알고리즘이 있다는 것을 참고하고 공부해보자 (나중에..)

해시기반이 상대적으로 정확하다고는 하나, 우리가 주로 분석하는 30억 reference를 생각해보면,

또 몇개 샘플 단위가 아니라 몇십, 몇백 샘플을 분석한다면,

정확도가 조금 떨어지지만, 엄청 빠른 매핑할 수 있는 BWT 알고리즘이 있다는 것을 기억해두자.

BWT 알고리즘 End.

BioinformaticsAndMe