Burrow-wheeler transform 쉽게 이해하기

Burrow-wheeler Transform (BWT)

 

 

mississippi라는 문자열을 Burrow-wheeler Transform으로 변형시키는 과정은 다음과 같다.

 

1. 문자열 끝에 #을 추가시킨 후, n by n 테이블을 만든다. (n은 #을 포함한 문자열 길이)

2. 1칸씩 rotate 시킨다. rotate 시키는 방향은 우측이든 좌측이든 관계 없다. 모든 경우의수가 나오도록만 하면 된다.

    이 matrix를 Conceptual matrix 𝑀𝑇 라고 한다.

3. roate 시킨 문자열들을 정렬한다. (정렬하는 과정에서 같아지기 때문에 rotate 방향은 상관이 없다.)

   정렬된 각 서열의 우측에있는 문자들이 BWT의 결과 sequence이다.

 

따라서 mississippi#라는 문자열의 B-W transform 결과는 ipssm#pissii 가 된다.

(mississippi -> ipssmpissii)

 

 

transform 전과 후의 문자열 길이는 사실 변함은 없다. 따라서 직접적으로 압축을 수행하는 알고리즘이 아니다.

하지만 input 안에서 중복되는 문자열이 많을수록 single character가 반복되는 경우가 생기기 때문에 압축하기가 매우 용이해진다.

특히 DNA, RNA sequence는 문자열이 A, C, G, T, U 정도밖에 없기 때문에 BWT로 transform 할 경우, 반복되는 문자가 굉장히 많아진다. 그리고 알고리즘도 매우 간단하며 가역반응이기 때문에 압축손실이 전혀 없는 알고리즘이다.

 

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

ACGTGCAGTCGATGCGATCGATGCTGACTGATGCAGCTGACTG

 

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

GGGCCGGGGGGGTTAAGGATTTCTCCTTTATACGACCCCAGAA

 

같은 single nucleotide끼리 붙어있는 경우의 수가 확실히 많이 늘었다.

이로서

 

 

 

http://ko.wikipedia.org/wiki/버로우즈-휠러_변환

 

Wikipedia의 버러우즈-휠러 변환 예제로 쓰인 abraca를 예로 R로 프로그래밍 해봤다.

source code R

 

str = "abraca"
strlen <- nchar(str)

for(i in 2:strlen){
    str[i] <- str[1]
    str[i] <- paste(c(str[i], substr(str[i], 1, i-1)), collapse="")
    str[i] <- substr( str[i], i, 99)
} # Conceptual matrix 만들기

for(i in 1:length(str)) print(str[i]) # Conceptual matrix 출력

 

str_sort <- sort(str) # 정렬하기
for(i in 1:length(str_sort)) print(str_sort[i]) # 정렬 matrix 출력

 

bwt <- paste((substr(str_sort[1:strlen],strlen,strlen)), collapse="") #BWT 결과 sequence 가져오기

 

 

 

decoding algorithm은 귀찮아서 나중에 구현하기로 함..

wikipedia 페이지에 알고리즘이 잘 나와있으니 그걸 보면 쉽게 이해할 수 있을 것이다.