버로우즈-휠러1 Lightweight BWT Construction for Very Large String Collection 핵심 부분 이 알고리즘은 대량의 서열 정보로 부터 BWT된 FM-index를 생성할 수 있도록 해주는 알고리즘을 제안한다. 그중 세 저자의 이름을 따서 하나는 BCR (Markus J. Bauer-Anthony J. Cox-Giovanna Rosone), 그것의 확장된 버전은 BCRext라고 부른다. 처음에는 해당 논문의 번역 내용을 올릴려고 했으나, 완전히 이해하고 쉽게 풀어서 설명하는 것이 더 나은 듯 하여 여기에 정리해 둔다. 구현은 BEETL이라는 라이브러리에서 최초 등장했다. BCR 알고리즘 먼저 입력된 서열에 대해 행을 열로 바꾸는(transpose) 연산을 수행한다. 그리고 가장 뒤에 있는 염기에서 부터 한 염기씩 진행해가면서 처리하는데, 이를 횟수라고 하자. 알고리즘은 입력 서열 중 가장 긴 길이의 .. 2014. 8. 15. 이전 1 다음