macでインフォマティクス

macでインフォマティクス

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

効率的なk-merカウンタ kmcEx

 

K-merは、それらの頻度と共に、エラー訂正、リピート検出、マルチプルシーケンスアラインメント、ゲノム構築などの基本的なビルディングブロックとして役立ち、k-merカウントにおける集中的な研究を引き付けた。ただし、k-merカウンタの出力自体は大きい。非常に多くの場合、メインメモリに収まるには大きすぎるため、ユーザビリティが非常に狭くなる。
 本著者らは、k-merならびにそれらの頻度を符号化し、良好なメモリ節約および検索効率を達成する新規なアイデアを紹介する。具体的には、カウントされたk-merを結合ビットアレイ(1つはk-mer表現用、もう1つは頻度符号化用)によって符号化するブルームフィルタのようなデータ構造を提案する。 5つのリアルデータセットでテストした結果、31-merのメモリ節約率の平均は、7つのハッシュ関数を持つ生の入力と比較して13.81と高いことがわかった。同時に、検索時間の複雑さはうまく制御され(事実上一定)、そして偽陽性率は2桁減少する。

 


インストール

ubuntu16.04でbuildしてテストした(docker使用、ホストOS macos10.14)。

依存

kmcEx is based on C++11.

Github

git clone https://github.com/lzhLab/kmcEx.git
cd kmcEx/
make

./kmcEx

# ./kmcEx 

----------------------------------------------------------------------

           kmcEx: counted k-mer encoding & decoding                   

----------------------------------------------------------------------

VERSION: 1.3

DATE   : Apr 2nd, 2019

----------------------------------------------------------------------

 

1. USAGE

     kmcEx [options] <input_file_name> <output_file_name> <working_directory>

     kmcEx [options] <@input_file_names> <output_file_name> <working_directory>

2. OPTIONS

     1) REQUIRED

        input_file_name    - single file in FASTQ format (gziped or not)

        @input_file_names  - file name with list of input files in FASTQ format (gziped or not)

        working_directory  - save temporary files

     2) OPTIONAL

        -k<len>            - k-mer length (default: 31)

        -t<value>          - total number of threads (default: 4)

        -ci<value>         - exclude k-mers occurring less than <value> times (default: 1)

        -cs<value>         - maximal value of a counter (default: 1023)

        -nh<value>         - number of hash (default: 7)

        -nb<value>         - number of bit array (default: 5)

3. EXAMPLES

     kmcEx -k31 -nh7 -nb5  rs.fastq rs.res /tmp

     kmcEx -k31 -nh7 -nb5  @rs.lst rs.res /tmp

 

 

 

実行方法

fastq、出力、作業ディレクトリを指定して実行する。

kmcEx -k 31 -nh 7 -nb 5 -t 8 rs.fastq output /tmp
  • -t      total number of threads (default: 4)
  • -k     k-mer length (default: 31)
  • -nh   number of hash (default: 7)
  • -nb   number of bit array (default: 5)

***********

Stage 1: 100%

Stage 2: 100%

1st stage: 1.59445s

2nd stage: 0.901676s

Total    : 2.49613s

Tmp size : 61MB

 

Stats:

   No. of k-mers below min. threshold :            0

   No. of k-mers above max. threshold :            0

   No. of unique k-mers               :      4523834

   No. of unique counted k-mers       :      4523834

   Total no. of k-mers                :     62516374

   Total no. of reads                 :       254371

   Total no. of super-k-mers          :      5097219

 

kmcEx status:

   Number of hash functions              :  7

   Number of coupled-bit arrays          :  5

   Number of k-mers having count=1       :  669035

   Number of k-mers having count>1       :  3854799

   kmcEx model construction time         :  1.92668

   Memory usage for coupled-bit arrays   :  16MB

   Memory usage for hash_map             :  9MB

   (k-2)-mer BF size for count>1 k-mers  :  1MB

   k-mer BF size for count=1 k-mers      :  0MB

   (k-2)-mer BF size for count=1 k-mers  :  0MB

   Total memory usage                    :  27MB

   No.1 coupled-bit array occupancy rate :  0.337

   No.2 coupled-bit array occupancy rate :  0.339

   No.3 coupled-bit array occupancy rate :  0.340

   No.4 coupled-bit array occupancy rate :  0.341

   No.5 coupled-bit array occupancy rate :  0.333

 

-------

   kmcEx model is successfully saved in  :  /tmp/rs.res

カレントにoutput.kmc_preとoutput.kmc_sufができる。/tmp/outputにモデルファイルができる。

ls /tmp/output/

bit1.bin  bit2.bin  bloom.bin  bloom2.bin  hash.bin  km_back.bin  last_map.bin  param.conf

 

あとはkmcで処理できる。

全k-merを書き出す。

kmc_dump output count
head count #開く

# head count  

AAAAAAAATGGCGATCGCCGCTGTGAGCCAA 15

AAAAAAAATTACCGGGGGGCGATCGCCATTT 23

AAAAAAAATTTTCGGGCGATCGCCATTGATT 18

AAAAAAACTGCCATGGTTGCCCCCAATGAAG 16

AAAAAAAGCTTGATCTCCCACAGCCATGGTT 19

AAAAAAAGGCGATCGCAAAGGCTTTTCCCGC 1

AAAAAAAGGCGATCGCCACAGTCAATGACGA 11

AAAAAAATCCAAGGCGATCGCCTCTGCTACC 22

AAAAAAATGGCGATCGCCGCTGTGAGCCAAT 16

AAAAAAATTACCGGGGGGCGATCGCCATTTT 22

他の例

 

引用

kmcEx: memory-frugal and retrieval-efficient encoding of counted k-mers
Peng Jiang Jie Luo Yiqi Wang Pingji Deng Bertil Schmidt Xiangjun Tang Ningjiang Chen Limsoon Wong Liang Zhao
Bioinformatics, Published: 30 April 2019