fasthashを使用した読み取りマッピングを加速します

次世代シーケンス（NGS）テクノロジーの導入により、ゲノムシーケンスデータの量の指数関数的な増加に直面しています。次世代シーケンスのすべての医学的および遺伝的応用の成功は、膨大な量のシーケンスデータを迅速かつ正確に処理および分析できる計算技術の存在に大きく依存します。残念ながら、現在の読み取りマッピングアルゴリズムは、NGSによって生成された膨大な量のデータに対処するのが困難です。私たちは、新しいアルゴリズムであるFasthashを提案します。Fasthashは、すべてのシードおよび拡張クラスの読み取りマッピングアルゴリズムと互換性のある一般的なアルゴリズムです。2つの主要な手法、すなわち隣接フィルタリングと安価なk-mer選択を導入します。Fasthashを実装し、人気のある読み取りマッピングプログラムMraffastのコードベースに統合しました。編集距離のカットオフに応じて、100％の感度と高い包括性を維持しながら、最大19倍のスピードアップを観察しました。

With the introduction of next-generation sequencing (NGS) technologies, we are facing an exponential increase in the amount of genomic sequence data. The success of all medical and genetic applications of next-generation sequencing critically depends on the existence of computational techniques that can process and analyze the enormous amount of sequence data quickly and accurately. Unfortunately, the current read mapping algorithms have difficulties in coping with the massive amounts of data generated by NGS.We propose a new algorithm, FastHASH, which drastically improves the performance of the seed-and-extend type hash table based read mapping algorithms, while maintaining the high sensitivity and comprehensiveness of such methods. FastHASH is a generic algorithm compatible with all seed-and-extend class read mapping algorithms. It introduces two main techniques, namely Adjacency Filtering, and Cheap K-mer Selection.We implemented FastHASH and merged it into the codebase of the popular read mapping program, mrFAST. Depending on the edit distance cutoffs, we observed up to 19-fold speedup while still maintaining 100% sensitivity and high comprehensiveness.