이 알고리즘은 대량의 서열 정보로 부터 BWT된 FM-index를 생성할 수 있도록 해주는 알고리즘을 제안한다. 그중 세 저자의 이름을 따서 하나는 BCR (Markus J. Bauer-Anthony J. Cox-Giovanna Rosone), 그것의 확장된 버전은 BCRext라고 부른다. 처음에는 해당 논문의 번역 내용을 올릴려고 했으나, 완전히 이해하고 쉽게 풀어서 설명하는 것이 더 나은 듯 하여 여기에 정리해 둔다. 구현은 BEETL이라는 라이브러리에서 최초 등장했다.
BCR 알고리즘
먼저 입력된 서열에 대해 행을 열로 바꾸는(transpose) 연산을 수행한다. 그리고 가장 뒤에 있는 염기에서 부터 한 염기씩 진행해가면서 처리하는데, 이를 횟수라고 하자. 알고리즘은 입력 서열 중 가장 긴 길이의 서열의 횟수(cycle) 만큼 진행되게 된다. 물론 해당 논문의 구현은 동일한 길이의 서열을 가정하고 구현되어 있다. 한 염기를 처리할 때는 다음과 같은 배열의 정보를 유지한다.
- Q: 부분 BWT 가 저장되는 배열이다. 이는 BWT의 가장 맨 앞의 염기의 사전식 순서에 따라 배열 색인 번호가 결정된다. 또한, 사용되는 알파뱃의 개수만큼 존재한다. 이 중 BWT0 부분 배열은 단 한 문자만을 포함한 접미사를 담고 있기 때문에, 전체 리드의 가장 마지막 문자들로 이뤄져 있다. 구현된 코드에는 pileN이라는 식으로 명명되어 있다.
- P: 새로운 염기값을 부분 BWT에 붙여갈 때, 가장 먼저 부분 BWT가 Q에 의해서 결정되고, 그 다음에는 그 부분 BWT의 몇 번째에 들어가는지의 값이 저장되는 곳이다. 쉽게 보자면 해당 접미사 배열을 정렬한 후에 접미사 배열 상의 번호이다. 구현된 코드에는 posN이라는 식으로 명명되어 있다.
- N: 개별 서열이 출력되는 순서를 담는 배열이다. Q와 P를 찾은 후에 P와 Q에 대해 정렬을 수행하게 되면 원래 N의 순서도 그 정렬 순서에 따라 바뀌게 되는데, 그 때 이 배열 값의 순서도 따라서 바뀌므로 어떤 순서로 값을 써야 하는 지 알 수 있게 된다. 구현에서는 seqN이라는 식으로 명명되어 있다.
이 알고리즘은 이전의 염기의 값들로 위 세 배열의 값들을 계산한 후에, 새로운 염기들을 이전 염기 값들에서 계산된 Q, P, N에 따라 부분 BWT를 수정하게 된다. 이것이 가능한 이유는 서열의 순열을 취한 후에 가장 마지막 열을 취하는 것이 BWT이고, 이 값은 현재 접미사의 맨 앞에 있는 염기의 바로 이전 염기가 순열을 취했을 때 가장 마지막 염기임을 이용하는 것이다.
BCRext 알고리즘
이 알고리즘은 아직 읽어 보지 않았다.
댓글