유전체 데이터에 대한 배치 접미사 배열의 실험적 분석

Abstract

두 인간의 유전체는 서로 99.9% 이상 유사하며, 이러한 유사성을 이용해 효율적으로 인덱싱 하는 연구가 활발히 진행되고 있다. 배치 접미사 배열은 문자열들의 공통 부분과 비공통 부분을 구별하여 일반화 접미사 배열보다 적은 개수의 인덱스를 저장함으로써 공간을 절약한다. 본 논문에서는 1000 유전체 프로젝트의 실제 유전체 데이터가 가진 특성을 조사하고, 배치 접미사 배열을 구현하여 유전체 데이터를 이용해 실험한 결과를 분석한다. 그 결과, 실험에 사용된 200개의 20번 염색체 데이터는 1.08% 위치에서만 차이를 보인다. 30개 염색체의 배치 접미사 배열은 일반화 접미사 배열 크기의 9.46%만을 사용해 90.54%를 절약하며, 200개 염색체의 배치 접미사 배열은 17.51%를 사용해 82.49%를 절약한다. 200개 염색체의 배치 접미사 배열을 저장하는 파일은 일반화 접미사 배열 파일보다 38.85GB를 절약한 8.24GB만을 사용한다. 염색체의 개수가 증가할수록 배치 접미사 배열이 일반화 접미사 배열에 비해 차지하는 크기 비율은 서서히 상승하는 추세지만 그 상승폭은 매우 완만하여 배치 접미사 배열이 일반화 접미사 배열에 비해 절약할 수 있는 공간은 꾸준히 증가한다. 따라서 더 많은 개수의 유전체를 인덱싱 할수록 배치 접미사 배열이 일반화 접미사 배열에 비해 상당한 공간을 절약할 수 있을 것으로 기대한다.