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.
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