interval tree

SnpEff (https://www.landesbioscience.com/journals/fly/2011FLY0072R1.pdf) 
:  SNPs, MNPs (multiple nucleotide polymorphism), InDels 등을 annotation 할때 쓰는 프로그램

위 논문의 내용은 말그대로 variant를 찾고 나서 그 뒤에 variant에 대한 annotation을 해주는 프로그램인 SnpEff를 사용하여 Drosophila의 strain의 SNP, MNPs, InDels 등을 annotation 한 논문.

프로그램 차원에서 보면 중요한 keyword는 
""interval forest, which is a hash of interval trees indexed by chromosome"".


Interval Trees
http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22intervals/

interval 은 정수 쌍을 의미([a,b] such that a<b)
elementary interval은 interval의 end point (integer)  에 의해 생기는 partition을 의미.
예를 들어 interval x=[10,20],y=[15,25],z=[18,22] 가 있을때 아래 그림과 같이 7개의 elementary interval이 생긴다.

이 interval들을 저장하기 위한 자료 구조로 BST(binary search tree)를 이용한다. 
일단 elementary interval을 저장할 수 있는 자료 구조로 아래와 같은 tree 생성.

각 leaf node는 elementary interval을 나타나게 된다. 여기서 interval의 정보를 넣는 방법은..
단순하게 생각하면 아래와 같을 수 있다.

 문제는 too much memory !
그래서 아래와 같은 두가지 조건으로 internal node 까지 사용한다.
1.node의 범위가 interval 에 완전히 포함되고 2.그 node의 parent node 범위는 interval을 벗어나면 그 node에 interval 을 저장. 그러면 아래와 같이 interval을 저장하게 된다.

좀더 복잡한 예제를 보자면 아래와 같은 작곡가의 일생을 interval로 tree 를 만들면 

아래와 보는 바와 같다.

여기서 문제. 1910년 경에 살았던 작곡가는 누구인가라는 문제에 대한 해답은 어떻게 찾는가?
1910을 span 하고 있는 leaf에 담긴 interval이 그 해답. 곧 A,B.  그런데 만약 문제가 1880년 경이라면? 1880을 span 하고 있는 leaf는 아무 interval도 포함하고 있지 않다. 
그래서 정확하게 해당 interval을 찾는 과정은 해당 년도를 포함하고 있는 leaf에서부터 root 까지의 interval을 다 찾는 것. 다르게 이야기 하면 root 에서 해당 년도를  span 하고 있는 leaf를 찾아가면서 각 internal node의 interval을 다 찾으면 되는 것. 곧 root-to-leaf path finding문제가 된다.


Interval Tree Code for Python
http://blog.nextgenetics.net/?e=45


Return to Paper
Each interval tree is composed of nodes. Each node has five elements (i) a center point, (ii) a pointer to a node having all intervals to the left of the center, (iii) a pointer to a node having all intervals to the right of the center, (iv) all intervals overlapping the center point sorted by start position, and (v) all intervals overlapping the center point, sorted by end position