ntHash2: recursive spaced seed hashing for nucleotide sequences.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 36000872.
- Also identified by DOI 10.1093/bioinformatics/btac564 and PMC identifier 9563681.
- Licence recorded as CC BY.
- The licence permits redistribution, so the abstract is shown in full and the full text is available from the publisher.
Abstract
Spaced seeds are robust alternatives to k-mers in analyzing nucleotide sequences with high base mismatch rates. Hashing is also crucial for efficiently storing abundant sequence data. Here, we introduce ntHash2, a fast algorithm for spaced seed hashing that can be integrated into various bioinformatics tools for efficient sequence analysis with applications in genome research. ntHash2 is up to 2.1× faster at hashing various spaced seeds than the previous version and 3.8× faster than conventional hashing algorithms with naïve adaptation. Additionally, we reduced the collision rate of ntHash for longer k-mer lengths and improved the uniformity of the hash distribution by modifying the canonical hashing mechanism. ntHash2 is freely available online at github.com/bcgsc/ntHash under an MIT license. Supplementary data are available at Bioinformatics online.
Medical subject headings
- Algorithms
- Software