コンパクトなhashテーブルを用いた高速なマッピングツール FEM

　DNA配列決定は、生物学および医学の多くの分野において強力な技術となっている。過去10年間のハイスループットシーケンシングプラットフォームにおける技術革新により、ゲノミクスの分野で革命が起こった。 1回のシーケンスで、数十億回のショートリードを迅速かつ安価に生成することができ、これによってゲノムデータ解析の計算負荷は増大する。大部分の関連パイプラインの第1ステップは、生成されたリードをリファレンスゲノムにマッピングすることである。

　リードのマッパーは、2つのクラスのいずれかに分類される。 FastHASH [論文より　ref.1]、mrsFAST [ref.2]、RazerS3 [ref.3]、BitMapper [ref.4]、およびHobbes [ref.5]を含む1つのクラスは、all-mappersと呼ばれる。All-mappersは、各リードのすべてのマッピング位置を検索しようとする。もう１つのBowtie2 [ref.6]、BWA [ref.7]、GEM [ref.8]などは、best-mappersと呼ばれる。Best-mappersは、各リードごとに1つまたはいくつかのトップ・マッピング・ロケーションを識別するためのヒューリスティックな手法を使う。これらのヒューリスティックな戦略は、スピードの大幅な改善につながる。しかし、CHIP-seq実験[ref.9]、コピー数変動、RNA-seq転写産物量定量[ref.10]などの特定のアプリケーションでは、すべてのマッピングのすべてのマッピング位置を特定するためにオールマッパーを使用することが望ましい場合がある。この研究では、効率的でスケーラブルなオール・マッパー・アルゴリズムの設計に重点を置いた。

　数十億の文字を含むリファレンス全体を簡単に検索するために、すべてのマッパーはしばしばシードと拡張の戦略を使用する。この戦略を使用して、全マッパーは、最初にリファレンスゲノムの固定長シードまたはk-mer（長さkの部分文字列）をハッシュテーブルまたは同様のデータ構造にインデックスする。第2に、リファレンスゲノムにおけるリードの正しいマッピングはシードでもマッピングされるという観察に基づき、各クエリのリードはシードに分割され、ハッシュテーブルインデックスに候補マッピング位置を問い合わせる。最後に、Needleman-Wunsch [ref.11]やSmith-Waterman [ref.12]のような動的プログラミングアルゴリズムを使用して、候補位置の各リードを拡張し、エラーの閾値がe以下で正確性を検証する。

　リードマッピング問題には、多くのindexing技術が適用されている。これらは、サフィックスツリー[ref.13]、接尾辞配列[ref.14]、FM index付きバウンス - ウィーラー変換（BWT）[ref.15]、およびq-グラム[ref.16-18]を含む。indexの選択はパフォーマンスにとって重要である。最先端のAll-mappersは、主にヒトリファレンスゲノムのために約12GBのメモリを占めるq-gramインデックスに依存している。このインデックスは、通常、マッピングプロセス中にメインメモリに保持されなければならないため、はるかに小さいメモリフットプリントでアプローチすることが非常に望ましい。これは、高帯域幅メモリ（HBM）などの限られたサイズの高速メモリを特徴とする最新のコンピュータアーキテクチャにとって特に重要である。

　この論文の著者らは、ヒトゲノムのindexに3.5~5.3GBの小さなメモリフットプリントを有するリードマッピングのための新規なデータ構造を提示する。簡潔なハッシュインデックスには、FEM (Fast(F) and Efficient(E) read Mapper(M)）を設計するために実装した2つの新規シード選択アルゴリズム（グループシードおよび可変長シード）と効率的な並列構築アルゴリズムがある。 FEMは、指定された編集距離内のすべてのリードのマッピングを返すことができる。著者らの実験結果は、FEMがスケーラブルであり、スピードとメモリフットプリントの両方に関して、他の最先端のオールマッパーよりも優れていることを示している。Masaiと比較すると、FEMは1つのスレッドを使用時に1桁高速で、複数のスレッド使用時は2桁高速である。さらに、BitMapperと比較して最大2.8倍のスピードアップと、BitMapper2とHobbes3に比べて1桁のスピードアップを達成している。

インストール

cent OSに導入した。

Github

https://github.com/haowenz/FEM

git clone https://github.com/haowenz/FEM.git
cd FEM/
make

> ./FEM

$ ./FEM

Program: FEM (Fast and Efficient short read Mapper)

Version: 1.1

Contact: Haowen Zhang <hwzhang@gatech.edu>

Usage: FEM <command> [options]

Command: index index sequences in the FASTA format

align FEM algorithm

Note: To use FEM, you need to first index the genome with `FEM index'.

ラン

１、indexを作成する。順にwindowサイズとstepサイズを指定する必要がある。

FEM index 12 2 reference.fa

２、マッピング

FEM align -ref reference.fa --read inout.fq -o output.sam

-e error threshold
-t number of threads
-f seeding algorithm: "g" for group seeding and "vl" for variable-length seeding
-a select one additional q-gram (only for test)
--ref Input reference file
--read Input read file
-o Output SAM file