BWT란? #

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

Burrows-Wheeler Transform #

Transform #

"BANANA" 문자열을 예로 들어 버로우즈 휠러 변환하는 과정은 기본적으로 아래와 같다.

1. 변환하고자 하는 문자열(BANANA)의 맨 마지막에 단어의 끝을 알리는 토큰을 넣는다( ex> BANANA$ )
2. 토큰을 넣은 문자열을 왼쪽으로 한칸씩 Cyclic Shift를 수행하며 행렬을 생성한다.
3. 생성된 행렬의 각 행을 사전순으로 Sorting 한다($ 토큰은 맨 마지막 순서). 이때 정렬된 형태의 행렬을 BW행렬이라고 한다.
4. 정렬된 행렬의 맨 마지막 열의 문자들로 생성된 문자열이 변화된 결과이다.[그림]

위 변환과정을 수행하기 위해서는 문자열의 길이가 n일 때, O(n) * O(nlogn)(문자열 비교시간 * 정렬횟수) = O(n^2logn) 의 시간이 걸리지만, 현재는 Linear Time 에 변환 가능한 여러 알고리즘이 발표되었다.

Inversion #

변환된 BWT로부터 복호화하는 과정은 변환 과정에 비해 다소 복잡하다. 앞서 "BANANA"를 변환한 "BNN$AAA"로부터 역변환 하는 과정은 다음과 같다.

1. 각 열에 변환된 문자열 "BNN$AAA"를 추가한다. 2. 각 행에 생성된 문자열을 사전순으로 정렬한다.
2. 1, 2번 과정을 반복수행한다.
3. 맨 마지막 열에 단어의 끝을 알리는 토큰('$')이 있는 행이 역변환된 행렬이다.

Bioinformatics in BWT #

BWT는 변환과정에서 생성되는 버로우즈-휠러 행렬(Burrows-Wheeler Matrix; BW Matrix)의 몇가지 특징을 이용하여 문자열 패턴 검색 시 매우 빠른 시간 안에 검색이 가능하다. 이러한 검색 기능은 문자열 매칭에 많이 사용되며 특히 Bioinformatics 분야에서 BWT를 이용하여 RNA Sequence 를 Mapping 하기 위한 방법으로 많이 사용된다. BWT를 이용한 대표적인 도구로는 Bowtie, BWA, SOAP2 등이 있으며 속도 최적화등의 이유로 BWT 기반 알고리즘인 FM-Index를 이용하여 Sequence를 매칭한다.

Incoming Links #

Related Bioinformaticses (Bioinformatics 0) #

• FM-Index