본 내용은 http://www.homolog.us/Tutorials/index.php?p=2.8&s=6을 번역한 것이다.
BWT의 복원성
우리는 BWT가 복원 가능함을 언급했었다. 우리는 어떻게 다음 서열로 부터 'homolg.us$'를 복원할 것인가?
우리는 위의 서열이 BWT를 생성하기 위해서 행렬의 마지막 열에서부터 생성된 서열임을 알아야 한다. 그러나 우리는 또한 다른 열인 첫번째 열을 안다. 첫번째 열은 사전순으로 정렬된 마지막 열에 있는 모든 문자들을 가지고 있다.
이 밖에 우리는 어떤 것을 알고 있나? 우리는, 원래 서열에서, 첫번째 열에 있던 문자들이 마지막 열의 다음에 나오는 문자들임을 알고 있다. 그러므로, 우리는 원래의 서열에서 '$'는 's' 다음에 나오고, '.'은 'g' 다음에 나오고, 'g'는 'o' 다음에 다오고, 'h'는 '$' 다음에 나오고, 'l'는 'o' 다음에.. 이런 식으로 계속 나옴을 안다.
'$' 다음에 나오는 문자가 원래 서열에서 첫째 문자이다. 그것은 'h'이다. 왼쪽(First) 열에서 'h' 다음에는 'o'가 온다. 'o' 다음에는 무엇이 오는가? 우리는 'g', 'l', 그리고, 'm'의 선택이 있다. 이 때 우리는 후-전(LF) 사상 특성을 적용할 필요가 있다. 우리는 'h' 다음의 'o'가 왼쪽(F) 열에서 가장 마지막에 나타나는 'o'임을 후전 사상 특성에 의해서 알 수 있다. BWT 열에서 마지막 'o' 다음에는 'm'이 따라 나온다. 'm' 다음에 나오는 두번째 'o'를 따라가면,'l', 'l'을 따라가면, 첫번째 'o'가 나오며, 첫번째 'o'를 따라가면 'g', 'g'를 따라가면 '.', '.'을 따라가면 'u', 'u'를 따라가면 's', 's'를 따라가면 최종적으로 '$'가 나와서 원래 서열의 복원이 완료된다.
댓글