본문 바로가기

bwt5

BWT의 복원성 본 내용은 http://www.homolog.us/Tutorials/index.php?p=2.8&s=6을 번역한 것이다. BWT의 복원성 우리는 BWT가 복원 가능함을 언급했었다. 우리는 어떻게 다음 서열로 부터 'homolg.us$'를 복원할 것인가? 우리는 위의 서열이 BWT를 생성하기 위해서 행렬의 마지막 열에서부터 생성된 서열임을 알아야 한다. 그러나 우리는 또한 다른 열인 첫번째 열을 안다. 첫번째 열은 사전순으로 정렬된 마지막 열에 있는 모든 문자들을 가지고 있다. 이 밖에 우리는 어떤 것을 알고 있나? 우리는, 원래 서열에서, 첫번째 열에 있던 문자들이 마지막 열의 다음에 나오는 문자들임을 알고 있다. 그러므로, 우리는 원래의 서열에서 '$'는 's' 다음에 나오고, '.'은 'g' 다음에 .. 2014. 9. 16.
BWT(Burrows Wheeler transform)의 후-전 특성 버로우즈 휠러 변형의 LF 특성은 이전에 언급한 BCR 알고리즘을 이해하기 위해서 매우 중요하다. 본인도 이를 알지 못한 상태에서 코드와 논문을 이해하다 보니 뭔가 빠진 듯한 느낌이 들었는데.. 이제야 알게 되어서 이를 정리해둔다. 이 내용은 http://www.homolog.us/Tutorials/index.php?p=2.7&s=6에서 가져왔다. 후-전(LF) 특성왜 BWT가 유용한가?만약 매우 긴 서열을 변환한다면, BWT는 유사한 문자들을 모이게 하고, 더 압축을 할 수 있도록 해준다. 예를 들어, 변형된 서열에서, 두개의 'o'가 가 같이 오고, 세번째 o도 가까이에 있게 된다.BWT의 두번째 특성은 염기 검색 수행에 유용하다. 이것은 후-전 사상(LF mapping)이라고 불린다. 그것을 설명하.. 2014. 9. 16.
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.
상수 공간 비교 기반 버로우즈 휠러 변환 원 논문의 제목은 A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform이다. 원문 내용의 2절의 일부는 다음과 같다. 다음 내용은 0-index 기반이다. 즉, 문자열에서 첫 문자는 index 0을 가진다. 가령, T='temp'에서 T[0] == 't'이고, T[3] == 'p'이다. Given the input text T = T [0 ..n−1] where T [n−1] = $, moving a single character inside T can change the content of many suffixes. The idea to circumvent this difficulty without .. 2014. 8. 6.