Efficient counting of k-mers in DNA sequences using a bloom filter.
Efficient counting of k-mers in DNA sequences using a bloom filter.
复制标题
DOI：
10.1186/1471-2105-12-333
复制
发表时间：
2011-08-10
影响因子：
3
通讯作者：
Pritchard JK
中科院分区：
文献类型：
--
作者：
Melsted P;Pritchard JK
计数k-mer（DNA序列数据中长度为k的子串）是生物信息学中许多方法的重要组成部分，包括基因组和转录组组装，宏基因组测序以及序列读取的错误校正。虽然原理上很简单，但在大型现代序列数据集中计算k聚体很容易超过标准计算机的内存容量。在当前的数据集中，存储容量的很大一部分-通常超过50%-可能花费在存储包含测序错误的k-mer上，并且通常在数据中仅观察到一次。这些单体k-mer对于没有某种纠错的许多算法来说是没有信息的。我们提出了一种新方法，可以识别DNA序列数据集中出现多次的所有k聚体。我们的方法使用布隆过滤器，一种概率数据结构，将所有观察到的k-mer隐式存储在内存中，大大降低了内存需求。然后，我们对数据进行第二次扫描，以提供所有非唯一k聚体的精确计数。例如数据集，我们报告与当前软件相比节省了高达50%的内存使用，计算速度成本适中。这种方法可以减少任何算法的存储器需求，该算法通过对具有错误的序列数据中的k聚体进行计数而开始。这种方法的参考实现BFCounter是用C++编写的，并且是GPL许可的。它可以在http://pritch.bsd.uchicago.edu/bfcounter.html上免费下载
Counting k-mers (substrings of length k in DNA sequence data) is an essential component of many methods in bioinformatics, including for genome and transcriptome assembly, for metagenomic sequencing, and for error correction of sequence reads. Although simple in principle, counting k-mers in large modern sequence data sets can easily overwhelm the memory capacity of standard computers. In current data sets, a large fraction-often more than 50%-of the storage capacity may be spent on storing k-mers that contain sequencing errors and which are typically observed only a single time in the data. These singleton k-mers are uninformative for many algorithms without some kind of error correction. We present a new method that identifies all the k-mers that occur more than once in a DNA sequence data set. Our method does this using a Bloom filter, a probabilistic data structure that stores all the observed k-mers implicitly in memory with greatly reduced memory requirements. We then make a second sweep through the data to provide exact counts of all nonunique k-mers. For example data sets, we report up to 50% savings in memory usage compared to current software, with modest costs in computational speed. This approach may reduce memory requirements for any algorithm that starts by counting k-mers in sequence data with errors. A reference implementation for this methodology, BFCounter, is written in C++ and is GPL licensed. It is available for free download at http://pritch.bsd.uchicago.edu/bfcounter.html
登录
查看更多内容
影响因子：
3.7
作者：
Baird NA;Etter PD;Atwood TS;Currey MC;Shiver AL;Lewis ZA;Selker EU;Cresko WA;Johnson EA
通讯作者：
Johnson EA
影响因子：
1.7
作者：
Shi, Haixiang;Schmidt, Bertil;Mueller-Wittig, Wolfgang
通讯作者：
Mueller-Wittig, Wolfgang
影响因子：
7
作者：
Li, Ruiqiang;Zhu, Hongmei;Wang, Jun
通讯作者：
Wang, Jun
影响因子：
5.8
作者：
Stranneheim, Henrik;Kaller, Max;Lundeberg, Joakim
通讯作者：
Lundeberg, Joakim
影响因子：
7
作者：
Simpson, Jared T.;Wong, Kim;Birol, Inanc
通讯作者：
Birol, Inanc