macでインフォマティクス

macでインフォマティクス

HTS (NGS) 関連のインフォマティクス情報についてまとめています。

線形時間のロングリードゲノムアセンブラ GoldRush

2022 Preprint 高速なツール assembly

2023/02/112 誤字修正

 

　最新のロングリードDNOVOゲノムアセンブラは、OLC（Overlap Layout Consensus）パラダイムに従っており、そのネイティブ実装ではO(n2)アルゴリズムであった。OLCの最も時間とメモリを消費するステップであるall-vs-allシーケンシングリードアライメントは改良され、最新のロングリードアセンブラに再実装されたが、典型的な50Xヒトゲノムデータセットを組み立てる際に、これらのツールは依然として過剰な計算メモリを必要とすることがしばしばである。
　本発表では、入力されたロングリードの数に対して線形的な時間複雑度を持つde novoゲノムアセンブリーアルゴリズムであるGoldRushを紹介する。著者らは、GoldRushを3つのヒト細胞株（NA24385、HG01243、HG02055）、Oryza sativa（米）、Solanum lycopersicum（トマト）のゲノムを異なるベースエラープロファイルのOxford Nanopore Technologiesデータセットでテストした。GoldRushは、3つのヒトのデータセットで18.3～22.2 MbpのNGA50長を達成し、3つのうち2つは最も広範囲なミスアセンブリが少なく、コメとトマトの373 Mbpと824 MbpゲノムではそれぞれNGA50長が0.3 Mbpと2.6 Mbpであることが確認された。さらに、GoldRushは、最大54.5GBのRAMを使用して、1日以内にすべてのゲノムを組み上げた。この結果は、本アルゴリズムと新しいアセンブリパラダイムが、計算機メモリ空間において大規模ゲノムのde novoアセンブリを効率的に行うことができ、アセンブリの連続性も最新のOLCゲノムアセンブラに匹敵することを実証している。

レポジトリより

GoldRushは、入力されたロングリードを繰り返し処理し、ターゲットゲノムを1倍程度カバーするリードからなる「ゴールデンパス」を生成します。これらの「ゴールデンパス」リード（goldtig）は、研磨され、ミスアセンブリが修正された後、最終的なゲノムアセンブリを生成するためにスキャフォールドされます。GoldRushはメモリ効率が高く、リード数に対して線形な時間複雑性を持ちます。

アルゴリズムの一般的なステップ

  • GoldRush-Path：ゴールデンパスリードの選択
  • GoldRush-Edit：ゲノムの研磨
  • Tigmint-long：ゲノムの修正
  • GoldRush-Link：ゲノムのscaffold構築

 

wiki（2023年2月現在はまだあまり整備されていない）

https://github.com/bcgsc/goldrush/wiki

Poster

http://www.birollab.ca/assets/posts/CoombeLauren_HitSeq_ISMB2022_goldrush-link.pdf

 

インストール

mambaで環境を作って導入した。リリースからも入手できる。

依存

  • GCC 7+ with OpenMP
  • python 3.9+
  • zlib
  • meson
  • ninja
  • tcmalloc
  • sdsl-lite
  • boost
  • libdivsufsort
  • sparsehash
  • btllib
  • Tigmint 1.2.6+
  • ntLink 1.3.3+
  • minimap2

Github

#conda
mamba create -n goldrush python=3.9 -y
conda activate goldrush
mamba install -c conda-forge -c bioconda goldrush

#from source
git clone https://github.com/bcgsc/goldrush.git
cd goldrush
git submodule init
git submodule update
meson --prefix /path/to/install build
cd build
ninja install

> goldrush -h

Usage: make [options] [target] ...

Options:

  -b, -m                      Ignored for compatibility.

  -B, --always-make           Unconditionally make all targets.

  -C DIRECTORY, --directory=DIRECTORY

                              Change to DIRECTORY before doing anything.

  -d                          Print lots of debugging information.

  --debug[=FLAGS]             Print various types of debugging information.

  -e, --environment-overrides

                              Environment variables override makefiles.

  -E STRING, --eval=STRING    Evaluate STRING as a makefile statement.

  -f FILE, --file=FILE, --makefile=FILE

                              Read FILE as a makefile.

  -h, --help                  Print this message and exit.

  -i, --ignore-errors         Ignore errors from recipes.

  -I DIRECTORY, --include-dir=DIRECTORY

                              Search DIRECTORY for included makefiles.

  -j [N], --jobs[=N]          Allow N jobs at once; infinite jobs with no arg.

  -k, --keep-going            Keep going when some targets can't be made.

  -l [N], --load-average[=N], --max-load[=N]

                              Don't start multiple jobs unless load is below N.

  -L, --check-symlink-times   Use the latest mtime between symlinks and target.

  -n, --just-print, --dry-run, --recon

                              Don't actually run any recipe; just print them.

  -o FILE, --old-file=FILE, --assume-old=FILE

                              Consider FILE to be very old and don't remake it.

  -O[TYPE], --output-sync[=TYPE]

                              Synchronize output of parallel jobs by TYPE.

  -p, --print-data-base       Print make's internal database.

  -q, --question              Run no recipe; exit status says if up to date.

  -r, --no-builtin-rules      Disable the built-in implicit rules.

  -R, --no-builtin-variables  Disable the built-in variable settings.

  -s, --silent, --quiet       Don't echo recipes.

  --no-silent                 Echo recipes (disable --silent mode).

  -S, --no-keep-going, --stop

                              Turns off -k.

  -t, --touch                 Touch targets instead of remaking them.

  --trace                     Print tracing information.

  -v, --version               Print the version number of make and exit.

  -w, --print-directory       Print the current directory.

  --no-print-directory        Turn off -w, even if it was turned on implicitly.

  -W FILE, --what-if=FILE, --new-file=FILE, --assume-new=FILE

                              Consider FILE to be infinitely new.

  --warn-undefined-variables  Warn when an undefined variable is referenced.

 

This program built for x86_64-conda-linux-gnu

Report bugs to <bug-make@gnu.org>

 

 

テストラン

C. elegans 第3染色体の ~1Mbp セグメントから小さなロングリードのセット（ファイルサイズ98-Mb、3795リード、平均長13450-bp）を自動的にダウンロードし、 GoldRush を実行するスクリプトが用意されている。

git clone https://github.com/bcgsc/goldrush.git
cd goldrush/tests/
./goldrush_test_demo.sh

カレントパスに多くの中間ファイルができるが、最終的なアセンブリファイルはgoldrush_test_golden_path.goldrush-edit-polished.span2.dist500.tigmint.faとなる（累積長1.1-Mb、平均長7321-bp、contig数156）。テストしたときはダウンロード後、20秒程度で終了した。

 

テストラン

ロングリード（.fq or .fastqのみ対応）とゲノムサイズを指定する。リードのパス指定時、拡張子は指定しない。

goldrush run reads=long_reads G=3e9

 

必要なリソース要件についてはレポジトリのSystem Requirementsを見てください。ヒト50x全ゲノムアセンブリでもわずか64GBメモリで足りるようです。論文内でもほかのアセンブラと比較して議論されています。

引用

GoldRush: A de novo long read genome assembler with linear time complexity
Johnathan Wong, Lauren Coombe,  View ORCID ProfileVladimir Nikolić, Emily Zhang, Ka Ming Nip, Puneet Sidhu, René L Warren

bioRxiv, Posted October 27, 2022