最近のシークエンシング技術の進歩により、これまで以上に大規模なゲノムデータにアクセスしやすくなり、ゲノム構造およびその種間および種内での多様性の特性評価が可能になった。シーケンシング後のデータの分析は困難な作業である。ハイスループットシークエンシングリード（すなわちショートDNAフラグメント）の分析における最大の課題の1つは、全ゲノムアセンブリ（Zhang et al、2011）であり、これはDNAフラグメントを再構築するためにDNAフラグメントをアライメントおよび併合するプロセスである。具体的には、de novoゲノムアセンブリは、ゲノムについての事前の知識なしに、重複してサンプリングされたDNA配列からゲノムを再構築する。デノボゲノムアセンブリは、以前には特徴付けられていなかったゲノムについての配列を生成することができる（Simpson and Durbin、2012）。リファレンスをすでに持っているゲノムの場合でも、de novoアセンブリは、リファレンスからの偏りなしに個人特有の遺伝的特徴の同定を可能にする。したがって、de novoアセンブリを通じて、種の全遺伝的変異にアクセスできるようになる。
現在のハイスループットシーケンシング法は、リード長に基づき、「ショートリード」と「ロングリード」の2つの主要なカテゴリに分類できる。ショートリード技術（Bentley et al、2008）の主な制限は、リード長より長いゲノム上のリピートを扱えないことであり、断片化されたアセンブリがもたらされる。逆に、Pacific Biosciences（PacBio）の1分子リアルタイム（SMRT）シークエンシング（Eid et al、2009）とOxford Nanopore Technologiesのナノポアシークエンシング（Goodwin et al、2015）は平均長が10,000塩基対（bp）に達することが多く、長いリードを生成する。これらは複雑なリピートの分解を可能にし、より正確なアンサンブルを可能にする。しかしながら、これらの改善された技術のリードは５％から３５％の範囲のエラー率で、より低い精度を犠牲にしてもたらされている。それにもかかわらず、エラーは、ショートリード技術と比較してよりランダムに、そしてより均等に分散される。
ショートリードのアセンブリは通常、de Bruijn Graph（DBG）抽象化に依存しているが、ロングリードのde Bruijnグラフは断片化しすぎてエラー率が高いために役に立たない。そのため、最先端のロングリードアセンブラの圧倒的多数が、オーバーラップレイアウトコンセンサス（OLC）パラダイムを使用している（Berlin et al、2015）。 OLCアセンブリでは、最初のステップはリード間のオーバーラップの検出とオーバーラップグラフの作成である。ゲノムをカバーするのに必要なリード数が大幅に少なく（100倍）、オーバーラップグラフのサイズが制限されるため、OLCパラダイムは部分的にロングリードに使用される。非常に正確なオーバーラップ検出は、主にペアワイズアライメントの計算集約的な性質のために、OLCアセンブリパイプライン（Myers、2014）の主要な計算上のボトルネックになっている。
現在のところ、いくつかのアルゴリズムは、エラーが発生しやすいロングリードデータをさまざまな精度で重ね合わせることができる。一般的な手法は、k-merインデックステーブルまたはサフィックスアレイなどのインデックス付けデータ構造を使用して初期候補リードペアのセットを識別することであり、したがって、第２段階でペアワイズアライメントを計算してコストを軽減する。
単純な重複として知られることもある初期候補リードペアの組を識別するプロセスは、精度とアルゴリズム実行時間の両方に影響を与える。最初の候補リードペアの正確な同定は、真にゲノム内で重複する全てのペアを保持しながら、アライメントのランニングタイムを最小にする。これらのペアを識別するためには堅牢な数学モデルが重要になる。さらに、計算効率がよく、非常に正確なオーバーラップおよびアラインメントアルゴリズムは、既存のロングリードアセンブラを改良する可能性があり、de novoアセンブリおよびより高品質の変異検出を可能にする。
（一部略）
BELLAは、アライメントスコアに応じて、Chernoff boundsに基づく新しい方法を使用して、真のアライメントと誤った検出を分離する。我々（著者ら）は、配列間の重複の長さが増加するにつれて、偽陽性の確率が指数関数的に低下することを示す。シミュレートされたデータでは、BELLAは無視できる精度の損失で（真のアライメントの）高い再現率を達成する。
インストール
ubuntu16.04のminiconda3-4.3.21環境でテストした（docker使用; ホスト macos10.14）。
依存
pip install simplesam
本体 Github
git clone https://github.com/giuliaguidi/bella.git
cd bella/
ln -s makefile-nersc Makefile
make bella
> ./bella -h
# ./bella -h
BELLA - Long Read Aligner for De Novo Genome Assembly
Usage:
-f : k-mer list from Jellyfish (required if Jellyfish k-mer counting is used)
-i : list of fastq(s) (required)
-o : output filename (required)
-d : depth/coverage (required)
-k : k-mer length [17]
-a : use fixed alignment threshold [50]
-x : alignment x-drop factor [7]
-e : error rate [auto estimated from fastq]
-m : total RAM of the system in MB [auto estimated if possible or 8,000 if not]
-z : skip the pairwise alignment [false]
-w : relaxMargin parameter for alignment on edges [300]
-c : alignment score deviation from the mean [0.1]
-n : filter out alignment on edge [false]
-r : kmerRift: bases separating two k-mers used as seeds for a read [1,000]
-p : output in PAF format [false]
実行方法
fastqのパスを書いたテキストファイルを指定してランする。depthも指定する必要がある。
bella -i text-file-listing-all-input-fastq-files -o output -d <depth>
出力はBLASRライクなフォーマットになる。詳細はGithub参照。
PAF出力（link）するには-pをつける。
bella -i text-file-listing-all-input-fastq-files -o output -d <depth> -p
miniasmを使えばPAFからGFAを出力でき、awkで整形すればそこからfastaを出力できる。
引用
BELLA: Berkeley Efficient Long-Read to Long-Read Aligner and Overlapper
Giulia Guidi1,2,*, Marquita Ellis1,2, Daniel Rokhsar3,4, Katherine Yelick1,2, Aydın Buluc
bioRxiv preprint first posted online Nov. 7, 2018
関連
