suffix tree (1)

whole genome alignment, Silva에서의 alignment 과정 그리고 금선생 추천 책 등등에서 많이 만나온 용어 suffix tree. 정리해야 겠다. 일단. 참고 문헌은 http://www.cs.ucf.edu/~shzhang/Combio10/lec3.pdf 과 algorithms on Strings, Trees, and Sequence의 5장부터로 한다. 과연 볼수 있을려나..


네이버링으로 대략적으로 알아본 결과 reference가 m길이의 T 문자열일때 query가 n 길이의 S 문자열이면 KMP나 보이어-무어의 방법(이 두가지 방법 다 뇌를 자극하는 알고리즘에 나온다. 기억이 가물하지만)이 O(m)의 시간이 걸리는데 비해 suffix tree는 reference를 한번 preprocessing (O(m)) 하면 O(n)의 시간만에 T에서 S를 찾아낸다(hashing 인건가). 또한 i번째 leaf 노드에서 루트까지 node의 값을 연결하면 T[i:m]의 문자열이 나온다. 그리고 suffix tree를 구하는 방식은 여러가지인데 특정 문자열에 대한 suffix tree는 unique하다. 또한 문자열 안에 substring이 몇번 나오나 혹은 어디에 있나 하는 정보를 root에서 부터 원하는 substring까지의 노드를 찾고 거기서 부터 연결된 leaf 갯수를 새면 그 정보가 나온다. 요정도..


<from UFC >
: ucf 자료를 보면 순서가 suffix의 대한 intro, definition, exact string matching problem, building suffix tree 순으로 되어 있다.  그림은 위 링크의 pdf를 참조하길. 


-hash table 보다 suffix tree가 났냐? hash가 더 이해하기 쉽고 뭐.. 시간도 비슷하지만 문젠 hash table은 query의 문자열의 길이가 고정이라는거. 그리고 다른 string match trick이 안먹힌다는데.. 이건 계속 봐야 알겠음.


-suffix tree의 정의 : 
1. rooted directed tree로 문자열 길이만큼의 leaves를 갖는다.
2. root 노드를 제외한 internal 노드는 최소한 2개의 자식 노드를 갖으며 각 edge(연결선)은 문자열의 substring으로 labeling되어 있다.
3. 한 노드에서 나가는 edge들의 시작 character는 동일할 수 없다.
4. suffix tree의 key feature는 i 번째 leaf에서 edge의 label들을 연결하면 문자열의 i번째에서 시작하는 substring이 된다.
5. 문자열의 마지막 character는 unique charater여야 한다.


-exact string matching problem
reference 문자열 ST를 O(m) 시간 만큼 걸려서 suffix tree를 만들고 query 문자열 P를 ST에서의 unique path로 찾는다. root 에서부터 query의 문자열이 되는 path를 찾는다. path의 마지막 노드 아래의 leaf가 query를 포함하고 있는 suffix가 되겠다.


-building the suffix tree
1.Naive method : O(m**2)의 시간이 걸린단다. 이해는 잘된다. root에서 부터 제일 긴 suffix 부터 node를 붙인다. 예를 들어 papua 라는 문자열을 suffix tree로 만들려면 우선은 papua에서 제일 긴 suffix 인 papua를 root 노드에서 부터 연결한다. 그 다음의 젤 긴 suffix인 apua를 또 root에서 새로운 노드로 붙인다. 그다음 suffix는 pua인데 suffix tree의 정의에 따라 자식 노드들의 첫 character는 같으면 안되기때문에 아까의 papua와 pua가 첫 글자가 겹치기 때문에 이를 root에서 공통으로 edge를 만들고  apua와 ua로 노드를 분리 시킨다. 이런식으로 마무리.
2. 원래 suffix tree의 reference의 preprocessing 시간이 O(m)이라고 했는데 이는 1973년 Weiner에 의해 소개됐고 이후 space efficient 한 방법을 McCreight가 1976년 소개, 그 뒤 1995년 더 단순한 on-line algorithm이 Ukkonen에 의해 소개
3. Ukkonen's algorithm : 1에서부터 m 까지의 prefix를 하나씩 따서 그것의 suffix들을 tree에 extension하는 방식(이 말이 이해는 안갈건데 pdf 그림보면 안다). 이때 extension은 3가지 rule( 1.s[j:i+1] 을 extend 할때 s[j:i]까지의 label이 있는 edge를 찾으면 그 edge에 i+1번째 character를 extend한다. 2. 만약 root에서 시작되는 edge중 s[j:i]까지 매치되는 edge가 없으면 맞는데까지에서 새로운 edge와 노드를 만든다. 3.이미 s[j:i+1]까지의 문자열이 정확히 매치되면 nothing to do)에 따른다. 여기까지는 기본 방법이고, 여기다가 speed up 방법이 있는데 요건 이해가 안됨.


여전히 알고리즘 시간에 대한 계산이 이해가 잘 안된다. 음.. 그리고 예전 알고리즘 책 볼때도 느낀건데 어떻게 진행하는지는 이해는 하는데 왜는 깊게 이해 안되는 느낌이랄까.. 명화를 감상하는데 아 저기에 뭐가 있고 저기에 뭐가 그려져 있구나. 근데 이게 무슨 느낌으로 그린거지?하고 이해하지 못하는 느낌. 내가 볼때 반복만이 이 느낌을 채울수 있다고 본다.