以前の世代と比較して、第3世代シークエンシング（以後 3GS）は5〜120 kbのリードを得ることができる。しかし、現時点で報告されているエラー率はPacBioシークエンシング（論文より Koren et al、2012）で約15％、オックスフォードナノポア配列決定（Laver et al。、2015）で約40％と高い。これは、間違いなく、3GSのリードでゲノムをアセンブルするための最も重要な計算上の課題を提起する。
ゲノムアセンブリは、多数の短くて品質の低いDNA配列から、DNAが由来する元の染色体の高品質の表現を作成するために、コンティグ（contig）として知られる連続した部分にそれらを戻すプロセスである（定義）（Myers et al 、2000; Nagarajan＆Pop、2013; Pevzner、Tang＆Waterman、2001）。 3GSデータでは、de novoゲノムアセンブリアルゴリズムは、重複の発見（Berlin et al、2015; Ye et al、2014）、配列アライメント（Chaisson＆Tesler、2012; Myers、2014）、エラー訂正のポリッシュ、という3つのボトルネックを通過する必要がある。低品質の標的ゲノム領域から標的領域にアライメント可能なクエリー配列を収集するためには高速のアルゴリズムが必要であり、クエリー配列のレイアウト関係を利用するためには正確なアライナーが必要である。最後に、ポリッシュするコンセンサスアルゴリズムはレイアウト情報を取り、“ground truth” sequenceを推論する（図１に流れ）。
コンセンサスアルゴリズムは、複数の理由からゲノムアセンブリにとって重要である。第1に、コンセンサスアルゴリズムは、高品質の出力を生成するためにアセンブラに必要である。第2に、最近のアセンブリの進歩は、入力シーケンスのベースごとの精度を上げるために、個々のリードのポリッシュにも使用できる（Au et al、2012; Hackl et al、2014; Koren et al、2012; Salmela＆Rivals、2014） 。修正されたリードは、正確な入力を必要とする既存のオーバーラップ・レイアウトコンセンサスベースのアセンブラに供給される（Huang et al、2003; Mullikin＆Ning、2003; Myers et al、2000）。最初のシナリオでは、各ドラフトアセンブリcontig（またはbackboneと呼ばれる）がターゲットとして使用され、このバックボーンにアライメントされたすべてのリードは、バックボーンの品質を高めるためのクエリシーケンスとして使用される。第2のシナリオでは、エラーの多いロングリードがターゲットとして使用される。 ハイブリッドアセンブリアプローチと呼ばれる3GSデータとともにショートリードデータを活用する手法は、3GS技術誕生以来広く使われているアセンブリ戦略である。ショートリードはコストを大幅に抑え、精度を高めているため、これらを組み込むことで、アセンブリパイプライン全体のコストと計算負担を削減できる（Ye et al、2014）。それにもかかわらず、効率的なコンセンサスアルゴリズムが欠如しているため、このコンセンサスステップは、標的配列中の領域をショートリードまたはアセンブリに置き換えるなどのより単純なアプローチによって回避されている。残念なことに、ショートリードシーケンスのエラーは、正しい3GSシーケンスを傷つけ、望ましくないコンセンサスエラーを生成する可能性がある。最後に、アセンブリパイプラインのコンセンサスを得るステップがしばしば計算時間の最大部分を占めることも注目に値する（Berlin et al、2015; Chin et al、2013; Lee et al、2014）。したがって、効率的なコンセンサスアルゴリズムがあれば、アセンブリプロセスを顕著に加速できることになる（以下略）。
この研究では、よく知られたde Bruijn / k-mer graph（Hannenhalli et al、1996; Pevzner、Tang＆Waterman、2001; Ronen et al、2012）から知恵を借りて、エラーのあるドラフトアセンブリシーケンスを磨くために、一般的で汎用性の高い 'Sparc'アルゴリズムが開発されている。 Sparcは、シーケンスから直接規則的な非巡回グラフ（i.e., non-multigraph）を構築する。同じ位置に現れるk-merは、グラフを構築するときにメモリ消費量を削減するためにオンザフライでマージされる。このグラフは、誤ったk-mersによって引き起こされる過剰なメモリの使用を避けるために、”sparse”（Yeら、2012）にすることも許可されている。 k-mers間のリンク/エッジは、各リードを供給するときに構築される。エッジ重みは、リンクの信頼性を表す。直感的には、エッジウェイトの合計が最も高いパスがコンセンサスの良好な近似値と考えられる。したがって、この経路は探索され、アルゴリズム出力と見なされる。Sparcは、他のグラフ簡素化手法を利用することなく、低メモリで優れた結果を提供できる。シンプルなため、このアルゴリズムは主要な3GSコンセンサスプログラムPBdagcon（Chin et al。、2013）と比較して5倍高速で、メモリスペースを5倍少なくしている。SparcはNGS（第２世代）と3GSのデータをサポートしている。 30×PacBioデータのみで、Sparcはエラー率<0.5％でコンセンサスを得ることができ、より困難なOxford Nanoporeデータでは、SparcはNGSデータと組み合わせることで同様のエラー率（<0.5％）を達成できるとしている。
インストール
依存
- blasr（Pacbio long readのアライナー）
blasrはconda installでも導入できるし、ubuntuならバイナリを直接ダウンロードできる（リンク）。
wget https://github.com/ylipacbio/blasrbinary/raw/master/blasr
本体 Github
https://github.com/yechengxi/Sparc
git clone https://github.com/yechengxi/Sparc.git
cd Sparc/
g++ -O3 -o Sparc *.cpp
./Sparc
$ ./Sparc
For help: Sparc -h
Example command:
Sparc b BackboneFile.fa m Mapped.m5 c 2 k 2 g 2 o ConsensusOutput
Parameters:
b: backbone file.
m: the reads mapping files produced by blasr, using option -m 5.
k: k-mer size. (range: [1,5])
c: coverage threshold. (range: [1,5])
g: skip size, the larger the value, the more memory efficient the algorithm is. (range: [1,5])
HQ_Prefix: Shared prefix of the high quality read names.
boost: boosting weight for the high quality reads. (range: [1,5])
Author: Chengxi Ye cxy@umd.edu.
last update: Jan 2, 2015.
パスの通ったディレクトリにコピーしておく。
ラン
１、ロングリードを使いアセンブルを実行する。
２、blasrを使い、１で得たcontig配列（backbone.fasta）にロングリードをマッピングする。
blasr -nproc 32 query.reads.fasta backbone.fasta -bestn 1 -m 5 -minMatch 19 -out backbone.mapped.m5
３、ロングリードだけ使いコンセンサス配列を得る。
Sparc b Backbone.fa m backbone.mapped.m5 k 2 g 2 c 2 t 0.1 o ConsensusOutput
- b backbone file.
- m the reads mapping files produced by blasr, using option -m 5.
- k k-mer size (suggested range: [1,2]).
- c coverage threshold (range: [1,5], suggest: 2).
- t adaptive threshold (suggested range[0.0,0.3]).
- g skip size, the larger the value, the more memory efficient the algorithm is (suggested range: [1,3]).
３、またはロングリードとNGSリードの両方を使いコンセンサス配列を得る。NGSリードをContig_1.fqとContig_2.fqとするなら、オプションHQ_Prefixで"Contig"というprefixを指定する。
Sparc b backbone.fasta m backbone.mapped.m5 k 2 g 2 c 2 t 0.1 HQ_Prefix Contig boost 5 o ConsensusOutput
- boost boosting weight for the high quality reads (suggested range: [1,10]).
- HQ_Prefix Shared prefix of the high quality read names. (e.g. if the sec-gen sequences have names >Contig_xxx, then ‘Contig’ is a shared prefix of the high quality reads)
引用
Sparc: a sparsity-based consensus algorithm for long erroneous sequencing reads
Chengxi Ye, Zhanshan (Sam) Ma
PeerJ. 2016; 4: e2016.
