2019 5/17 誤字修正
2023/02/10 リンク修正
シーケンサのスループットの増加および価格の低下に伴い、高カバレッジシーケンシングデータセットの生成は日常的になっている。これは、ゲノムおよびトランスクリプトームのデノボアセンブリのためのいくつかの異なるアプローチの開発を促進した(Miller et al、2010; Moreton et al、2016)。しかし、大きなゲノムやトランスクリプトームのアセンブリは、リソース集約的な作業である。
データセットのサイズが大きいため、ゲノムおよびメタゲノムシーケンシングに適用される1つまたはいくつかのデータセットについて、de novoアセンブリのデータ構造をよりスペース効率的にすることに集中している(Chikhi et al、2016; Pell et al, 2012)。圧縮ゲノミクスと呼ばれる別のアプローチは、高速化計算のためにデータセットの圧縮表現を見つけることを扱い、これはリードアラインメントおよびSNPコールに首尾よく適用されている(Berger et al、2013; Loh et al、2012)。
ここでは、de novo transcriptome assemblyのためのデータ削減アプローチが不均一なRNAシーケンスデータセットのパフォーマンスに与える影響を調べる。これは、de Bruijnグラフ(DBG)に依存する現在のアセンブリ方法が大量のメインメモリを消費するため、重要な問題である(Grabherr et al、2011; Robertson et al、2010; Schulz et al、2012)。しかし、それは情報理論の観点からも興味深い問題である。データのどの部分が実際にアセンブラによって使用されているのか?
シーケンスエラーを取り除き、データサイズを減らすための簡単な方法は、リードサフィックスと低品質のプレフィックスを削除することである。これは一般にアセンブリ性能の低下につながり(MacManes、2014; Mbandi et al、2014)、現在のデータセットの高い冗長性には対処していない。他のアプローチは、RNA-seqデータセットにおけるシーケンシングエラーの効率的な訂正を可能にし、それはデータがエラー訂正されなければならないので実行時間は増加するが、一般にアセンブリ性能の改善につながる (Le et al., 2013; Song and Florea, 2015)。
冗長性を除去するための直接的なアプローチはCD-HIT(Fu et al、2012)のようなアルゴリズムを使用して配列類似性に従ってリードをクラスター化し、そしてクラスター中の非常に類似したリードを除去することである。最近アセンブリ転写物をクラスター化するの改良がなされたが(Srivastava et al、2016)、アセンブリ前に何億ものリードをクラスター化することは依然として困難である。
特にアセンブリと組み合わせて使用される別のアプローチは、khmerパッケージに実装された「デジタル正規化」(Diginorm; Brown et al、2012)である(Crusoe et al、2015)。 Diginormは、最小カウントスケッチデータ構造を使用して、リードデータセットをストリーミングしてk-merの存在量を推定する。ユーザが選択した存在量のしきい値tを使用して、中央値のk-merカバレッジがtを超えると、リードが削除される。これに似たアイデアがTrinityのin silico正規化(TIS)で、これはTrinityアセンブラー・パッケージの一部である(Haas et al、2013)。データセット内のリードごとに、TISはリード内のk-merのカバレッジ中央値を計算する。カバレッジ中央値が目的のカバレッジよりも小さい場合、リードは常に保持される。そうでなければ、それは所望のカバレッジとmedianカバレッジの比に等しい確率で保たれる。さらに、リードの平均k-merカバレッジに対するk-merカバレッジのSDの比率がカットオフより高い場合、リードは削除される。最近開発されたNeatFreqアルゴリズム(McCorrison et al、2014)は、中央値のk-mer頻度に基づいてリードをビンにクラスタ化する。
k-merカバレッジベースの正規化の利点は3 foldである。(i)冗長性の高いリードが削除され、アセンブリに必要なメモリおよびランタイム要件が軽減される。(ii)このプロセスにより誤ったリードが削除される。(iii) 正規化は高速で、アセンブラが消費するメモリのごく一部しか消費しない。アセンブリのパフォーマンスに大きな影響を与えることなく、多くの場合データの大部分を削除できることが示されているため、これによりアセンブリ問題の計算の複雑さが本質的に軽減される(Brown et al、2012; Haas et al、2013)。しかしながら、以前のアルゴリズムは、有用なk-merを含むデータの重要な部分を保存することに関していかなる確実性も与えない。少量ではあるが重要なk-merを含むリードは削除される可能性がある。これにより、DBG内の接続が失われる可能性があるため、断片化されたアセンブリが生成される可能性がある。これはRNA-seqやメタゲノミクスのように、カバレッジが不均一なシーケンシングデータセットにとって特に問題となる。
ここで、DBGバックボーン(重み付けされていないノードおよびエッジ)を失うことなくリードを削減し、相対ノード存在量は元のDBGと比較して削減データセットで保持されるという考えに基づいてOptimized Read Normalization Algorithm (ORNA)を提案する。 各リードがm k-mersからなるn個のリードセットが与えられると、リード正規化は、リードに関するset multi-cover(SMC)最適化問題として表現される。 この研究では、実際にうまくいくことが証明されている𝒪(nm log(nm))時間の発見的アルゴリズムが示唆されている。 正規化データとECデータを分析すると、実行時間とメモリ消費量を大幅に節約しながら、より優れたアセンブリを作成できることがわかる。 ソフトウェアはMITライセンスの下でhttps://github.com/SchulzLab/ORNAで無料で入手できる。
ORNAはDiginormのスピリットで開発されたリード正規化ソフトウェアである。 ORNAは計算コストが安く、オリジナルのデータセットからすべてのkmerを確実に保持する。ユーザーがカバレッジの高いデータセットを使用しているが、データの冗長性を排除するために、de novoアセンブリを実行するのに十分な計算能力(特にメモリだけでなく時間も限られている)を持っていない場合に使用できる。多くのシーケンスデータセットをマージするのにも使用できる。データセットに大きく依存するため、作成されるアセンブリに大きな影響を与える可能性があることに注意する必要がある。
インストール
ubuntu16.0.4でテストした(docker使用、ホストmacos10.12)。
依存
- Linux operating system with gcc version >=4.7
- All the analysis for the manuscript was performed on Debain 8 operating system
- cmake
本体 Github
git clone https://github.com/SchulzLab/ORNA
cd ORNA/
bash install.sh
cd build/bin/
> ./ORNA -h
# ./ORNA -h
ERROR: Unknown parameter '-h'
[ORNA options]
-cs (1 arg) : Collect stat [default '0']
-type (1 arg) : Type for the output file (fasta/fastq) [default 'fasta']
-binsize (1 arg) : Bin Size [default '1000']
-ksorting (1 arg) : Kmer based Sorting [default '0']
-sorting (1 arg) : Quality Sorting [default '0']
-pair2 (1 arg) : Second read of the pair [default 'ORNAERROR']
-pair1 (1 arg) : First read of the pair [default 'ORNAERROR']
-base (1 arg) : Base for the logarithmic function [default '1.7']
-output (1 arg) : Prefix of the output File [default 'Normalized']
-input (1 arg) : Input File [default 'ORNAERROR']
-kmer (1 arg) : kmer required [default '21']
-nb-cores (1 arg) : number of cores [default '0']
-verbose (1 arg) : verbosity level [default '1']
-version (0 arg) : version
-help (0 arg) : help
実行方法
ORNAは元のデータセットのすべてのkmerを保持しようとするため、誤ったkmerも保持される。 よって、前もってデータのエラー訂正しておく方がより多くの不要なリードを削減できる。 RNA-seqまたは他の不均一なデータの場合は、ORNAとうまく機能することが著者らによって確認されているSEECERアルゴリズム(github)を使用することが推奨されている。
fastqまたはfastaを指定する。
シングルエンドfastq
ORNA -input single.fq -output output -base 1.7 -kmer 21 -nb-cores 16 -type fastq
- -input Input File [default 'ORNAERROR']
- -base Base for the logarithmic function [default '1.7']
- -kmer kmer required [default '21']
- -output Prefix of the output File [default 'Normalized']
- -type Type for the output file (fasta/fastq) [default 'fasta']
ペアエンド fastq
ORNA -input -pair1 pair1.fq -pair2 pair2.fq -output output -base 1.7 -kmer 21 -nb-cores 16 -type fastq
- -pair1 First read of the pair [default 'ORNAERROR']
- -pair2 Second read of the pair [default 'ORNAERROR']
output_1.fqとoutput_2.fqが出力される。
引用
In silico read normalization using set multi-cover optimization
Dilip A Durai, Marcel H Schulz
Bioinformatics, Volume 34, Issue 19, 01 October 2018, Pages 3273–3280,
関連
BBnorm
KATにはk-merとGCでフィルタリングする機能があります。