빅데이터분석

Colummar Storage in Genomics

hongiiv 2014. 7. 22. 14:55
반응형
요즘 화두는 Big Data 기술을 어떻게 genomics에 접목하는 것이냐에 대한 것이다. 구글의 Google Genomics, UC Berkeley의 ADAM 등이 Genomics에 Big Data 기술을 적용하고 있다.

다양한 Big Data 기술들이 genomics에 적용될 수 있겠지만, 오늘은 colummar storage 기술을 이용하여 BAM 파일등의 genomics 데이터를 다루는 방법에 대한 이야기를 하고자 한다.

왠 colummar storage? colummar storage 기술을 사용하면 대용량의 데이터에 대한 액세스를 빠르게 수행할 수 있기 때문이다. genomics 데이터를 다루기 힘든 이유와 왜 빠른 액세스가 필요한지 등등의 구구절절한 why에 대한 대답은 굳이 하지 않겠다. 뭐 간단히 지난 그들에서 google의 bigquery를 사용하는 방법에 대해서 언급한 적이 있는데 바로 bigquery도 colummar storage 기술을 이용하고 있다. 그 정도로 해두겠다.

python을 통해 파일을 처리한다고 해보자. 우선 파일의 내용을 읽어들야 한다. 이때 readline()을 이용하여 line 단위로 처리할 것이다. 흔히 MySQL과 같은 데이터베이스도 레코드 단위로 데이터를 저장하고 읽어들이게 된다. 지금까지 우리가 알고 있는 데이터는 record-oriented하게 저장되어 있다. 근데 요놈을 90도 돌려서 column-oriented하게 저장하는 것이 바로 columnar storage이다. 이렇게 되면 아래 그림에서 보는 것과 같이 컬럼 별로 데이터를 각기 다른 storage volume에 저장이 가능하게 된다. columnar storage를 사용하게 됨으로서 다음과 같은 잇점을 얻게 된다.

Traffic minimization 쿼리에 사용된 컬럼의 값만 스캔하여 쿼리를 실행하고 데이터를 이동시키면 된다는 것이다. 예를 들어 "SELECT top(title) FROM foo"의 경우 전체 데이터에 대해서 뒤지는게 아니라 단지 title 컬럼이 저장된 곳만 뒤지면 되기 때문에 트랙픽을 최소화할 수 있게 된다. BigQuery에서는 쿼리를 날린 데이터의 양에 대해서 과금이 책정되는 이유가 바로 이것이며, 1000 genomes의 variants가 3.5 TB에 달하지만 매번 쿼리에 따라 3.5 TB의 모든 데이터를 사용하지는 않게 되며 따라서 빠르게 scan이 가능하다.

Higher compression ratio 한 연구에 따르면 row-based storage가 일반적으로 1:3인것에 비해  columnar storage의 경우 압축률이 1:10으로 훨씬 효율적인데 이는 컬럼내에 유사한 값들이 존재하고 이는 컬럼내의 값들의 variation이 적은 경우 특히 낮다. 따라서 BAM 포맷의 파일의 경우 5~25% 정도의 압축률을 보인다고 한다.

그러나 단점도 존재하는 법! 바로 기존의 데이터에 대한 update가 있는 경우 효율적으로 작동하지 않는다는 것인데, 이는 genomics 데이터의 특성상 update가 거의 발생하지 않는다는 점에서 genomics 데이터를 column storage 기술을 사용하는데에 있어서 최적이라고 할 수 있다.

바로 이러한 column storage의 기술을 구현한 것이 Dremel로 구글 내부에서 사용하다가 google bigquery라는 이름의 서비스로 내놓았다. open source 진영에서도 Parquet가 존재한다.


BAM/SAM 파일을 예를 들어보면, row 기반으로 헤더정보와 read 정보를 컬럼 단위로 포맷을 변환한다. 이렇게 포맷변환을 수행하면 column storage에 저장이 가능한 형태가 되며 여러 장비에 컬럼 단위로 분산되어 저장이 가능하게 된다. 앞선 higher compression ratio의 경우 특히  quality score에서 효율성이 좋아지며 약 0.75x archive의 효율성을 지닌다. traffic minimization 부분은 filter나 read의 quality를 체크하는 것등과 같은 구현에서 좋은 성능을 보인다.

 
BQSR (Base Quality Score Recalibration)
alignment 이후에는 BQSR 과정을 거쳐 data normalization을 수행하는데 이부분이 pipeline에서 많은 시간이 소요되는 부분이다. 이 과정은 후에  variant call의 accuracy에 상당한 영향을 미치기 때문에 bioinformatics pipeline에서 중요한 부분중 하나이다. 

GATK에서 BQSR이 구현되어 있지만 완벽하게 map reduce 프레임웍을 지원하지 않고 있지만 embarrassingly paralleizable (완전하게 독립되어 각각의 프로세서에 나누어 실행될 수 있는 병렬화의 하나) 하기 때문에 
colummar storage를 통해 구현됨으로서 성능향상을 꽤할 수 있다.  BQSR의 알고리즘은 Introduction to Base Quality Score Recalibration (BQSR)을 참고하면 되며, 간단하게 설명하면 다음과 같다. 
 
DNA sequencing 장비로부터 생산된 read의 각 base (A, C, T, G)는 estimate된 quality를 가지고 있다. estimated quality score는 Phred score를 통해 표현되며 이는 에러 확률이다. Phred score가 10이라면 이는 90%의 accuracy를 의미하며, 20은 99%, 30은 99.9%를 의미한다. Phred scores는 quality score 또는 Q scores라고도 한다.

BQSR은 바로 이 Phred quality score를 보정(adjusting)하는 과정으로 이미 알려진 SNPs를 입력으로 받는다. BQSR 알고리즘은 당신의 파일에서 reference와 다른 SNP이 dbSNP에 존재하지 않는 경우라면 이를 error로 간주한다. 통계적으로 개인에서 dbSNP에 존재하지 않는 SNP은 약 1,000개를 넘지 않는다는 가정을 기반으로 한다.

reported phred와 dbSNP의 정보를 가지고 계산된 empirical phread score를 통해 recalibration을 수행한다. 다음과 같이 3개의  read group(RG1, RG2, RG3)가 존재하고 각각은 error갯수/관찰된 SNP갯수로 RG1의 경우 총 3개의 read중 첫번째의 경우 1/105로 empirical phred score는 -10log10(error probability) = -10log10(1/105) = Q20인데, Yate's correction에 의해 -10*log10((errors+1) / (observations+2) = Q17이 된다. Reported quality score는 Q16으로 이 두개의 값을 통해 read의 각각 base에 대해서 recalibration을 수행하면 된다.

뭐 당연한 거지만, BQSR 과정에서는 read의 뒷쪽으로 갈수록 즉 machine cycle이 진행될수록 quality가 낮아지는 SBS(
Sequencing by Synthesis) 방식의 경우 covariates으로 base position을 사용하여 BQSR을 수행한다.


암튼 요렇게 분산처리 가능 quality score 컬럼만 사용하여 계산하면 무지 빨라진다. 뭐 그런거임. 대충 BQSR을 구현하게 되면 아래 수식,,, 자세한건 생략


GATK와 비교하면 accuracy나 performance측면에서 뛰어나고 Picard와 비교만 해서 BQSR의 경우 Performance 그래프는 생략,,, 암튼 GATK와 99% 동일한 결과,,, 이거 내가 한거 아님 아래 참고문헌의 ADAM 만든 사람이 한거임...



정말 끝.

참고문헌

https://github.com/googlegenomics
https://cloud.google.com/files/BigQueryTechnicalWP.pdf
http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-207.html
https://github.com/bigdatagenomics/adam
https://spark.apache.org/
http://www.genomeweb.com/informatics/uc-berkeley-team-develops-new-open-source-schema-apis-tools-fast-scalable-genomi 
http://zenfractal.com/2014/01/25/bqsr/
http://www.open-bio.org/bosc2014/BOSC2014-Genome-01-ADAM-Nothaft.pdf
반응형