버로우즈 휠러 변형의 LF 특성은 이전에 언급한 BCR 알고리즘을 이해하기 위해서 매우 중요하다. 본인도 이를 알지 못한 상태에서 코드와 논문을 이해하다 보니 뭔가 빠진 듯한 느낌이 들었는데.. 이제야 알게 되어서 이를 정리해둔다. 이 내용은 http://www.homolog.us/Tutorials/index.php?p=2.7&s=6에서 가져왔다.
후-전(LF) 특성
왜 BWT가 유용한가?
만약 매우 긴 서열을 변환한다면, BWT는 유사한 문자들을 모이게 하고, 더 압축을 할 수 있도록 해준다. 예를 들어, 변형된 서열에서, 두개의 'o'가 가 같이 오고, 세번째 o도 가까이에 있게 된다.
BWT의 두번째 특성은 염기 검색 수행에 유용하다. 이것은 후-전 사상(LF mapping)이라고 불린다. 그것을 설명하기 위해서, 우리는 이전에 언급한 것과 동일한 변형을 수행하며, 이와 더불어 세 개의 'o'에 대해서 다른 색상으로 표기한다.
여기에 원래의 서열 목록이 있다.
여기에 정렬된 서열 목록이 있다.
후전 사상 특성은 첫번째(First) 열의 염기 순서가 마지막(Last) 열의 염기 순서와 같다는 것이며, 이것은 또한 염기의 색상까지도 일치하는 것이다. 우리는 첫째 열의 세 'o'가 파랑, 초록, 그리고 빨강색으로 정렬된 것을 볼 수 있다. 마지막 열은 원래 서열의 BWT 변형으로 파랑색 'o'가 먼저 나오고, 두번 째로 초록색 'o'가 나오고, 세번째로 빨강색 'o'가 나온다.
후전 사상에 대해 멸로 특별한 것은 없으며, 우리는 단순히 정렬 작업으로 생각하면 된다. 마지막 열의 세 'o"는 각각 첫째 열의 'g', 'l', 'm'이 따라온다. 이 'o'들은 다음으로 따라오는 문자가 'g', 'l', 그리고 'm'에 의해 따라오기 때문에, 이에 의해서 정렬된 것이다. 무슨 말이냐면, 'o'는 전부 같으므로 정렬 순서를 정하기 위해서 그 다음 문자를 비교한 것이다. 사전 순서대로 하면, 'g', 'l', 'm'의 순서이다.
후전 사상 특성이 가지는 의미는 매우 중요하다. 우리는 Bowtie 검색 알고리즘에 대한 설명을 다음에 보도록 하자.
다른 예제인 - TATATATATA$를 보자. 이전과 마찬가지로, 우리는 단어들을 한 문자씩 왼쪽으로 옮기고, 가장 앞에 있던 문자는 맨 뒤에 붙이는 것을 모든 문자에 대해 처리될때까지 수행한다.
다음의 표는 위에 보이는 표를 사전순으로 정렬하여 얻어진다.
마지막 열은 원래 서열의 BWT이다. 다시금, 우리는 변형된 서열에서 a 한개를 빼고는 모든 T와 A가 유사한 위치에 모여 있는 것을 볼 수 있다.
위 표에서 원래 서열의 모든 A와 T는 서로 다른 색상을 가지고 있기 때문에, 우리는 최종 서열이 어떤 식으로 생성되었는지 찾아갈 수 있다. 우리는 여기에서 마지막 열의 A의 색상 순서가 첫째 열의 A의 색상 순서가 같음을 알 수 있다. T 역시 후전 사상 특성으로 알려진 유사한 특성을 보인다.
댓글