IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2017 · 28 citations · 38 references
ComputingBioinformaticsComputer ScienceGenome AssemblyParallel AlgorithmsParallel ComputingData ParallelismDistributed Memory ParallelismDna SequencingNext-generation SequencingParallel Data StructuresSequence AlignmentDistributed MemoryDistributed Memory AlgorithmsDistributed Shared MemoryHigh PerformanceIndexingIndexing Data StructuresK-mer IndexingShared Memory Systems
Counting and indexing fixed length substrings, or $k$k-mers, in biological sequences is a key step in many bioinformatics tasks including genome alignment and mapping, genome assembly, and error correction. While advances in next generation sequencing technologies have dramatically reduced the cost and improved latency and throughput, few bioinformatics tools can efficiently process the datasets at the current generation rate of 1.8 terabases per 3-day experiment from a single sequencer. We present Kmerind, a high performance parallel $k$k-mer indexing library for distributed memory environments. The Kmerind library provides a set of simple and consistent APIs with sequential semantics and parallel implementations that are designed to be flexible and extensible. Kmerind's $k$k-mer counter performs similarly or better than the best existing $k$k-mer counting tools even on shared memory systems. In a distributed memory environment, Kmerind counts $k$k-mers in a 120 GB sequence read dataset in less than 13 seconds on 1024 Xeon CPU cores, and fully indexes their positions in approximately 17 seconds. Querying for 1 percent of the $k$k-mers in these indices can be completed in 0.23 seconds and 28 seconds, respectively. Kmerind is the first $k$k-mer indexing library for distributed memory environments, and the first extensible library for general $k$k-mer indexing and counting. Kmerind is available at https://github.com/ParBLiSS/kmerind.
38
Basic local alignment search tool
Stephen F. Altschul, Warren Gish, Webb Miller et al. · Journal of Molecular Biology · 1990 · 94.5K citations
A global reference for human genetic variation
Richard Durbin, Peter Donnelly, Paul Flicek et al. · Nature · 2015 · 20K citations · Full text
Basic Local Alignment Search Tool
Stephen F. Altschul · Journal of Molecular Biology · 1990 · 13.9K citations
Velvet: Algorithms for de novo short read assembly using de Bruijn graphs
Daniel R. Zerbino, Ewan Birney · Genome Research · 2008 · 9.7K citations · Full text
The Cancer Genome Atlas Pan-Cancer analysis project
John N. Weinstein, Gordon B. Mills, Kenna Shaw et al. · Nature Genetics · 2013 · 9.5K citations · Full text