Tabix: 엄청 빠르게 탭으로 구분된 1차원 좌표계 검색하기

시퀀싱 데이터를 대량으로 뽑아놓고 후속 통계 처리를 하자면,
각 태그가 각각 어느 영역에 들어가는지 분류하는 과정을 거쳐야 합니다.
요즘 cufflinks 같이 자동으로 요약해주는 녀석들이 많이 나와서 그냥 단순히 RNA-seq이나 ChIP-seq에서 보통 많이 하는 분석만 하는 것은 간단해졌지만, CLIP-seq처럼 어디로 분석이 튈지 모르는 다른 대부분의 경우엔 매핑된 곳이 뭔지 대량으로 정확히 분류하는 것이 중요합니다.

예를 들어 생쥐 유전체 mm9 버전에서는 Igf2가 chr7의 149,836,673부터 149,845,394까지 있습니다. 사이에 인트론이 3개있고요. 여기서 만약에 14984050 근처에 어떤 태그 하나가 매핑되었다고 치면, 이게 어느 유전자인가 물어봐서 “Igf2의 2번째 인트론입니다”하는 대답하는 것을 수천만번 매우 빠르게 할 수 있어야 하는데요. 여기서 좀 더 복잡해지는 것은 Igf2 인트론에 mmu-mir-483이 껴 있듯이, 여러 주석이 겹쳐서 시작과 끝이 순서가 달라질 수 있어서, 단순히 정렬된 리스트의 이진 탐색이나 B+ tree같은 것으로는 인덱싱이 불가능합니다.

이 문제를 해결하려면 가장 간단하게는 SQLdb에 모두 집어넣어놓고 SELECT절에 BETWEEN을 써서 검색하는 것이겠는데, UCSC Genome Browser도 이 방법으로 MySQL에 넣고 쓰고, RNA-seq 초창기 분석 도구로 유명했던 ERANGE도 sqlite에 넣고 계속 SQL 질의를 보내서 해결합니다. 간단하긴 한데 써 보면 엄청나게 느려서 분석을 구경하는 사람들에게 NGS란 이렇게 오래걸릴 정도로 대단한거구나 하는 환상을 심어주기 쉬울 정도가 되죠.

그렇지만 물론 BETWEEN을 수천만번 하는 것 보다 훨씬 빠른 인덱스를 만드는 방법이 많이 있겠죠. 대표적으로 R+tree나 kd-tree 같은 2차원 공간 탐색이 가능한 인덱스를 쓰는 것도 있겠고요. 겹치는 녀석들끼리 링크드 리스트로 묶어서 서로 안 겹치는 클러스터로 만든 다음, 클러스터를 이진 탐색하는 방법도 있습니다. 알고리즘은 전자가 훨씬 멋있지만, 실제로 벤치마크해보면 후자가 압도적으로 빠릅니다.;; 이 방법을 구현한 파이썬 라이브러리로 Pygr의 NLMSA가 널리 쓰입니다. 그런데 이 쪽 구현은 내부적으로 깔끔하게 구현하느라 그랬는지, 메모리 소모나 인덱싱 속도, 검색 속도 모두 생각보다 훨씬 많이 먹고 느리고 그렇습니다. 특히 인덱스 들고 있는 데에 파이썬 객체를 너무 많이 만들어내서… 물론 SQL쓰는 것보단 훨씬 빠르지만 말이죠.

그러다 괜찮은 것을 발견했습니다. +_+ 어느날 samtools 새 버전이 나왔으면 받으려고 갔는데, tabix라고 처음 보는 게 올라가 있길래 궁금해서 보니까 바로 이 기능을 하는 것이더군요! 이건 좀 더 범용으로 만들어서 탭으로 구분된 모든 텍스트파일을 인덱싱 가능하도록 만들었고, 게다가 원본 그대로 gzip한 다음에 원본에서 찾아주는 것이라 여러 도구에 쉽게 녹아들어갈 수 있게 만들었네요. (압축파일 안에서 랜덤액세스가 가능하도록 하는 도구도 물론 들어있습니다.)

써보니 속도도 상당히 빠릅니다. 매우 만족! 그래서 파이썬에서 쓰려면 어떻게 해야하나 보니까, 이미 펄, 파이썬, 자바 바인딩이 들어있더군용. 그러나 파이썬 바인딩이 ctypes를 쓰게 돼 있어서, 설치나 관리가 여러모로 번거롭고 속도도 (아주 약간) 느려지고.. 흐흐 예전부터 들어왔던 Cython을 배워볼 절호의 기회다! 하고 Cython으로 한참 다시 바인딩하는 작업을 해 봤는데, 아무리 찾아봐도 이터레이터 객체를 구현할 때 __next__에서 NULL을 리턴할 방법이 없어서 깔끔하게 만들어 줄 수가 없네요.. 결국은 그냥 포기하고 C 모듈로 만들었습니다. (tabix 0.2.3용 패치) 패치는 tabix 원저자에게 보냈습니다. 파이썬 2/3 겸용이죠. 호호호;

이렇게 쓸 수 있습니다~ 일단 인덱스 만들고 확인하기.

파이썬에서도 똑같이 접근하기.

원래 pygr.NLMSA쓰고 있던 곳을 요걸로 바꾸니까 거의 10배 이상 빨라졌네요. ^__^