Accurate high throughput alignment: Algorithmic solutions for seeding and seed processing

Abstract

최근 몇 년 동안, 게놈 서열 (DNA와 RNA)의 연구는 의학 및 생물학과 같은 다양한 과학 분야의 중심 요소가 되었다. 이 연구는 구조적 변이 검색, 게놈의 어셈블리 또는 유전자 발견 등과 같은 분석을 망라한다. 이러한 모든 작업은 서열을 게놈으로의 매핑을 위한 빠르고 정확한 서열-게놈 얼라인어(aligners)들을 필요로 한다. 최첨단 얼라인어(aligners)들은 초기 작업으로 시딩으로 구성이 된 seed-chain-extend 패러다임을 적용하는 관계로 이러한 매핑을 효율적으로 그리고 정확하게 수행한다. 이 논문에서 우리는 시딩에 초점을 둔 high-throughput sequence-to-genome alignment를 위한 몇 가지 알고리즘들을 제안한다. 이 맥락에서 우리는 chaining을 “Strip of Consideration” 과 “seed harmonization”라고 칭한 두 알고리즘적 처리 방법의 연속 적용으로 대체한다. 이들 처리 방법은 각각 공간적으로 로컬하고 상호 consistent한 시드 집합을 계산한다. 추가적으로 우리는 FMD-index와 같은 suffix array를 기초로 한 bidirectional Burrows–Wheeler transform (BWT)를 이용해 효율적으로 계산 되어 질 수 있는 최대 생성 시드(maximal spanning seeds)라고 명명한 새로운 variable-size seed 집합을 소개한다. BWT는 오랜 계산 시간을 필요로 하는 관계로 single-use indices에 대해 적합하지 않다. 이러한 단점을 피하기 위해 우리는 추가로 해쉬 함수 (hash-map)를 기초로 한 fixed-size seeding 으로부터 MEMs (variable-size seeding)로의 알고리즘적 브리지를 개발한다. MEMs에 대한 두 필터링 방안을 이용해 우리는 이 브리지를 SMEMs과 최대 생성 시드(maximal spanning seeds) 로 확장한다. variable-size 와 fixed-size seed 집합들 사이의 하이라키 (hierarchy)들과 브리지 그리고 correctness rate 개념을 이용하여 우리는 fixed-size 와 variable-size seed 집합들을 종합적으로 분석하고 비교한다. 런타임 및 정확성과 관련해 우리의 해결방안의 강점을 실질적으로 입증하기 위해 우리는 MA – The Modular Aligner –를 구현하고 또한 short 그리고 long reads에 대해 벤치마킹 한다. MA는 MIT license at https://github.com/ITBE-Lab/MA 하의 오픈 소스 응용 프로그램으로 사용할 수 있다.; In recent years, the study of genomic sequences (DNA and RNA) has become a central element of various scientific disciplines as e.g. medicine and biology. This study comprises analyses such as the search for structural variants, the assembly of genomes or the finding of genes among others. All these tasks require fast and accurate sequence-to-genome aligners for mapping sequences to genomes. State-of-the-art aligners perform this mapping efficiently and accurately by applying the seed-chain-extend paradigm, which comprises seeding as an initial operation. Here we propose several algorithms for high-throughput sequence-to-genome alignment with a focus on seeding. In this context, we replace chaining by the consecutive application of two algorithmic approaches that are called “Strip of Consideration” and “seed harmonization”. These approaches compute sets of seeds that are spatially local and mutually consistent, respectively. Additionally, we introduce a novel variable-size seed set, called maximal spanning seeds, which can be efficiently computed using a bidirectional Burrows–Wheeler transform (BWT) based suffix array as e.g. the FMD-index. The BWT is not well suited for single-use indices due to its long build time. For circumventing this disadvantage, we additionally develop an algorithmic bridge from hash-map based fixed-size seeding to MEMs (variable-size seeding). Via two filtering approaches for MEMs, we extend this bridge to SMEMs and maximal spanning seeds. Using the bridge together with hierarchies among variable-size and fixed-size seed sets and a correctness rate notion, we comprehensively analyze and compare fixed-size and variable-size seed sets. For practically proving runtime and accuracy benefits of our approaches, we implement MA – The Modular Aligner – and benchmark it for short and long reads. MA is available as an open source application under the MIT license at https://github.com/ITBE-Lab/MA.