Bowtie

Burrows-Wheeler indexing

BWT 는 주어진 string 의 reversible permutation이기 때문에, 처음에는 데이터 압축을 위해 개발 되었지만,  BWT-based 인덱싱은 방대한 텍스트를 작은 양의 memory fottprint 만으로 찾아낼 수 있게 해준다. 이러한 특성 때문에 bioinformatics 에 적용된다. 

텍스트 T의 Burrows-Wheeler transformation BWT(T) 는 아래 처럼 만들어진다. 

 

위와 같이 되는 matrix 을 LF mapping 이라고 하는데 마지막 컬럼에서 문자 x의 i 번째 occurence 가 첫 번 째 컬럼에서도 i 번 째 x의 occurence 가 되기 때문이다. 

LF mapping 은 exact matching 에 활용된다. matrix 가 사전순으로 정렬되어 있기 때문에 주어진 sequence로 시작하는 row 는 연속적으로 나타나게 된다. 

EXACTMATCH는 short read 정렬에 적합하지 않다. 왜냐하면 alignment가 mismatch를 가지기 때문이다. 

따라서, sequencing error 를 야기한다. 따라서 backtracking search 를 이용해서 특정 alignment policy 를 만족하는 alignment 를 찾는 알고리즘을 소개한다.

read의 각 각의 character 는 numeric quality value를 가지고 있고, value가 낮을수록 sequencing error 가 발생했을 확률이 높음을 의미한다.

EXACTMATCH 와 비슷한 방법으로 진행한다. 점점 긴 suffix 를 대상으로 계산을 하게 된다. 만약에 range 가 

empty 가 된다면(suffix 가 text의 어떤 occurence 하고도 맞지 않다면) 알고리즘은 이미 매치된 쿼리 positiond을 선택하고, 다른 염기를 치환한다. 치환 후 부터 EXACTMATCH 가 계속 된다. 알고리즘은 alignment policy 와 일관되는 치환만을 선택하고, text 에서 반드시 한 번은 나타나게 되는  modified suffix 를 만들어내게 된다. 만약에 치환할 수 있는 position의 후보가 여러 개가 있으면 알고리즘은 quality value가 가장 낮은 position을 선택한다. 

Backtracking 시나리오는 새로운 substituion이 발생했을 때 신장하는 stack structure의 context 안에서 진행된다. 

또한 aligner 가 현재stack 에 있는 substitution을 위한 candidate alignment 를 모두 reject 했을 때 stack 이 shrink 한다.

정리하자면, Bowtie 는 가능한 alignment space에 대해서  quality-aware greedy, randomized, depth-first search 를 진행한다. 만약에 유혀한 alignment 가 존재하면, Bowtie는 이것을 찾아낸다. search 가 greedy 이기 때문에 

bowtie는 quality 혹은 mismatch 개수에 대해서 best 를 찾아내지는 않는다.

 

Excesssive Backtracking 

aligner 는 excessive backtracking 을 야기하는 sequence 를 encounter 하게 된다. 이러한 상황은 aligner 가 무의미한 노력을 하도록 만든다. Bowtie 는 double indexing 이라는 테크닉을 이용해서 이 과정을 조금 더 쉽게 만들었다. 

genome에서 2개의 index 가 선정되고, 하나는 genome 의 BWT를 포함하고 forward 라고 부른다. 두 번 쨰 것은 

character sequence 가 역전된 BWT 를 포함한다. 그리고 이것을 mirror index라고 부른다. 이것이 어떻게 알고리즘을 효율적으로 동작할 수 있는지 보면, alignment 에서 하나의 mismatch를 허용하는 policy를 가정해보자.  

하나의 mismatch 에 대한 valid 한 alignment 는 2가지의 경우로 나뉘는데, read 의 반 쪽이 mismatch를 포함하는지 안 하는지이다. 

Bowtie 는 두 가지 경우에 대응하는 2가지의 phase를 진행한다.

Phase 1.  forward index를 메모리에 올리고, query 의 오른쪽 반의 포지션에 대해서 치환을 하지 않는 aligner 를 호출한다. 

Phase 2. Mirror index를 사용해서 오른쪽 반의 포지션에 대해서 치환을 하지 않는 reversed query에 대한 aligner를 호출한다.

애석하게도, alignment 가 2개 이상의 mismatch를 가지는 경우에는 excessive backtracking을 피할 수 가 없다.

excessive backtracking 은 read가 low quality position 을 많이 가지고, reference에 잘 매치되지 않는 경우에 significant 함을 관찰했었다.