K-Mer Counting Using Bloom Filters with an FPGA-Attached HMC
Authors:
- Nathaniel McvicarNMNathaniel Mcvicar
- Chih-Ching LinCLChih-Ching Lin
- Scott HauckSHScott Hauck
- 1 April 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 203-210
Abstract
As FPGAs are integrated into to the cloud, they become useful in a number of areas where they were not traditionally considered, such as processing genomics data. For many genomics applications, such as K-mer counting, the off-chip DRAM (and sometimes SRAM) memory subsystems provided by most FPGA boards for high capacity storage are not efficient. Recently new styles of memory have been developed, though their role in reconfigurable computing systems can be unclear. One of the challenges these memory systems present to FPGA designers is identifying how they can be used in current systems, and what new applications become possible. In this paper we describe how and why K-mer counting is one such use for an FPGA-attached Hybrid Memory Cube (HMC). The HMC's high random-access rate is ideal for large Bloom filters, an efficient structure for checking membership in a set, or even counting occurrences. Our HMC based counting Bloom filter, useful in a bioinformatics context, achieves a speedup of 13x over traditional FPGA-attached DRAM and 9.31x to 17.6x over multi-core, multi-threaded software on our host system.Keywords
This publication has 29 references indexed in Scilit:
- Disk-based k-mer counting on a PCBMC Bioinformatics, 2013
- DSK: k-mer counting with very low memory usageBioinformatics, 2013
- Space-efficient and exact de Bruijn graph representation based on a Bloom filterAlgorithms for Molecular Biology, 2013
- A tale of three next generation sequencing platforms: comparison of Ion torrent, pacific biosciences and illumina MiSeq sequencersBMC Genomics, 2012
- Efficient counting of k-mers in DNA sequences using a bloom filterBMC Bioinformatics, 2011
- Cloud computing and the DNA data raceNature Biotechnology, 2010
- De novo assembly of human genomes with massively parallel short read sequencingGenome Research, 2009
- Accurate whole human genome sequencing using reversible terminator chemistryNature, 2008
- Velvet: Algorithms for de novo short read assembly using de Bruijn graphsGenome Research, 2008
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000