BWT와 LF 특성 #

BWT(Burrows-Wheeler Transform) #

BWT에 대한 설명은 https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform 와 BWT에 자세히 설명되어있다.

LF 특성 #

BWT 변환 과정에서 생성되는 행렬은 몇 가지 재미있는 특징을 가진다. 그중에서도 LF(Last-First) 특성은 BWT를 이용하여 문자열 매칭이 가능하게 한 매우 중요한 특징 중 하나이다. LF 특성은 첫 번째 열의 염기 순서가 마지막 열의 염기 순서와 같다는 것이며, 이는 나중에 Backward Searching 시 매우 중요한 단서가 된다.

FM Index #

FM-Index는 BWT 행렬의 First, Last 행의 글자만 따서 문자열의 Index를 만든 방법으로 문자열에 대해 BWT를 수행함으로써 얻어질 수 있다. BWT 과정에서 생성되는 BW 행렬의 마지막 문자열은 BWT 변환 결과이며, 맨 첫 행렬은 Suffix array(접미사행렬)과 같은 성질을 가진다. FM-Index는 기존 BWT 행렬에서 O(1)시간만에 생성 가능하며 문자열 검색에 있어 가장 중요한 특성 중 하나인 LF 특성을 그대로 이용 할 수 있어 일반적으로 O(n^2)의 공간이 필요한 BWT 행렬이 아닌 FM-Index를 이용하여 문자열 질의를 실행한다.

또한 FM-Index는 적절한 변환 과정을 통해 BWT뿐만 아니라 접미사 트리(Suffix trie or Suffix tree), 접미사 행렬(Suffix array)로 빠르게 변환 가능하므로 쉽게 응용 할 수 있다.

Backward Searching #

버로우즈-휠러 변환과정에서 생성되는 FM-index는 찾으려는 문자열의 길이가 m일 때, O(m) 시간 만에 매우 빨리 찾을 수 있어 유전자의 특정 시퀀스를 찾는데 주로 사용된다. 아래 그림은 앞서 생성한 BANANA문자열의 FM-index렬로부터 "NANA" 패턴을 찾는 과정이다.

그림의 위쪽 행렬은 매칭과정을 쉽게 설명하기 위한 BWT 행렬로 실제 Backward 과정에서는 나타나지 않는다. 아래쪽 그림은 실제 FM-Index를 이용해 검색을 수행하는 과정으로 BWT 행렬의 중간 문자들이 생략되었을 뿐 동일한 과정을 거쳐 검색을 수행한다.

Query를 검색하기 위해서는 찾고자 하는 문자열 "NANA"를 거꾸로 뒤집어 "ANAN" 순서로 검색을 수행한다. 검색을 수행하는 과정은 아래와 같다.

1. FM Index의 접미사에서 검색하려는 문자 Q(i=0)를 모두 찾는다.
2. FM Index에서 찾아진 문자 Q(i) 위치에 해당하는 접두사들을 검색한다. 이때 LF 특성을 이용하여 검색을 수행한다. 즉, BWT 마지막 문자열에서 두 번째로 나타난 'A'는[6 ] 접두사에서 두 번째로 나타난 'A'[2]와 동일하다.
3. 검색된 접두사 중에 접미사가 Q(i+1)에 해당하는 문자열을 찾는다.
4. Query의 모든 문자열 검색이 끝날 때 까지 2,3 과정을 반복한다.

즉, 위와 같은 검색 과정을 통해 Query 문자열을 검색할 수 있으며 검색 과정 중에 다음 문자열을 찾을 수 없을 경우 해당 쿼리는 Ref 문자열에 존재하지 않는 것을 의미한다.

Suggested Pages #

• 0.025 Next-generation_sequencing
• More suggestions...