Sparse and skew hashing of K-mers.
Ontology highlight
ABSTRACT: Motivation
A dictionary of k-mers is a data structure that stores a set of n distinct k-mers and supports membership queries. This data structure is at the hearth of many important tasks in computational biology. High-throughput sequencing of DNA can produce very large k-mer sets, in the size of billions of strings-in such cases, the memory consumption and query efficiency of the data structure is a concrete challenge.Results
To tackle this problem, we describe a compressed and associative dictionary for k-mers, that is: a data structure where strings are represented in compact form and each of them is associated to a unique integer identifier in the range [0,n). We show that some statistical properties of k-mer minimizers can be exploited by minimal perfect hashing to substantially improve the space/time trade-off of the dictionary compared to the best-known solutions.Availability and implementation
https://github.com/jermp/sshash.Supplementary information
Supplementary data are available at Bioinformatics online.
SUBMITTER: Pibiri GE
PROVIDER: S-EPMC9235479 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:MotivationHashing has been widely used for indexing, querying and rapid similarity search in many bioinformatics applications, including sequence alignment, genome and transcriptome assembly, k-mer counting and error correction. Hence, expediting hashing operations would have a substantial impact in the field, making bioinformatics applications faster and more efficient.ResultsWe present ntHash, a hashing algorithm tuned for processing DNA/RNA sequences. It performs the best when calculating hash values for adjacent k-mers in an input sequence, operating an order of magnitude faster than the best performing alternatives in typical use cases.Availability and implementationntHash is available online at http://www.bcgsc.ca/platform/bioinfo/software/nthash and is free for academic use.Contactshmohamadi@bcgsc.ca or ibirol@bcgsc.caSupplementary information: Supplementary data are available at Bioinformatics online.
| S-EPMC5181554 | biostudies-literature
Project description:Middle East respiratory syndrome coronavirus (MERS-CoV) is an emerging viral pathogen that primarily causes respiratory illness. We conducted a seroprevalence study of banked human serum samples collected in 2012 from Southern Saudi Arabia. Sera from 300 animal workers (17% with daily camel exposure) and 50 non-animal-exposed controls were examined for serological evidence of MERS-CoV infection by a pseudoparticle MERS-CoV spike protein neutralization assay. None of the sera reproducibly neutralized the MERS-CoV-pseudotyped lentiviral vector. These data suggest that serological evidence of zoonotic transmission of MERS-CoV was not common among animal workers in Southern Saudi Arabia during July 2012.
| S-EPMC4353318 | biostudies-literature
Project description:SMERS - sediment microbial electrochemial remediation systems
| PRJEB18734 | ENA
Project description:Fluids may store and manipulate information, enabling complex applications ranging from digital logic gates to algorithmic self-assembly. While controllable hydrodynamic chaos has previously been observed in viscous fluids and harnessed for efficient mixing, its application to the manipulation of digital information has been sparsely investigated. We show that chaotic stirring of a viscous fluid naturally produces a characteristic signature of the stirring process in the arrangement of particles in the fluid, and that this signature directly satisfies the requirements for a cryptographic hash function. This includes strong divergence between similar stirring protocols' hashes and avoidance of collisions (identical hashes from distinct stirs), which are facilitated by noninvertibility and a broad chaotic attractor that samples many points in the fluid domain. The hashing ability of the chaotic fluidic map implicates several unexpected mechanisms, including incomplete mixing at short time scales that produces a hyperuniform hash distribution. We investigate the dynamics of hashing using interparticle winding statistics, and find that hashing starts with large-scale winding of kinetically disjoint regions of the chaotic attractor, which gradually gives way to smaller scale braiding of single-particle trajectories. In addition to providing a physically motivated approach to implementing and analyzing deterministic chaotic maps for cryptographic applications, we anticipate that our approach has applications in microfluidic proof-of-work systems and characterizing large-scale turbulent flows from sparse tracer data.
| S-EPMC5948985 | biostudies-literature
Project description:MotivationVastly greater quantities of microbial genome data are being generated where environmental samples mix together the DNA from many different species. Here, we present Opal for metagenomic binning, the task of identifying the origin species of DNA sequencing reads. We introduce 'low-density' locality sensitive hashing to bioinformatics, with the addition of Gallager codes for even coverage, enabling quick and accurate metagenomic binning.ResultsOn public benchmarks, Opal halves the error on precision/recall (F1-score) as compared with both alignment-based and alignment-free methods for species classification. We demonstrate even more marked improvement at higher taxonomic levels, allowing for the discovery of novel lineages. Furthermore, the innovation of low-density, even-coverage hashing should itself prove an essential methodological advance as it enables the application of machine learning to other bioinformatic challenges.Availability and implementationFull source code and datasets are available at http://opal.csail.mit.edu and https://github.com/yunwilliamyu/opal.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC6330020 | biostudies-literature
Project description:MotivationK -mer hashing is a common operation in many foundational bioinformatics problems. However, generic string hashing algorithms are not optimized for this application. Strings in bioinformatics use specific alphabets, a trait leveraged for nucleic acid sequences in earlier work. We note that amino acid sequences, with complexities and context that cannot be captured by generic hashing algorithms, can also benefit from a domain-specific hashing algorithm. Such a hashing algorithm can accelerate and improve the sensitivity of bioinformatics applications developed for protein sequences.ResultsHere, we present aaHash, a recursive hashing algorithm tailored for amino acid sequences. This algorithm utilizes multiple hash levels to represent biochemical similarities between amino acids. aaHash performs ∼10X faster than generic string hashing algorithms in hashing adjacent k -mers.Availability and implementationaaHash is available online at https://github.com/bcgsc/btllib and is free for academic use.
| S-EPMC10197579 | biostudies-literature
Project description:MotivationK-mer hashing is a common operation in many foundational bioinformatics problems. However, generic string hashing algorithms are not optimized for this application. Strings in bioinformatics use specific alphabets, a trait leveraged for nucleic acid sequences in earlier work. We note that amino acid sequences, with complexities and context that cannot be captured by generic hashing algorithms, can also benefit from a domain-specific hashing algorithm. Such a hashing algorithm can accelerate and improve the sensitivity of bioinformatics applications developed for protein sequences.ResultsHere, we present aaHash, a recursive hashing algorithm tailored for amino acid sequences. This algorithm utilizes multiple hash levels to represent biochemical similarities between amino acids. aaHash performs ∼10× faster than generic string hashing algorithms in hashing adjacent k-mers.Availability and implementationaaHash is available online at https://github.com/bcgsc/btllib and is free for academic use.
| S-EPMC10660294 | biostudies-literature
Project description:A highly efficient template-based protein-protein docking algorithm, nicknamed SnapDock, is presented. It employs a Geometric Hashing-based structural alignment scheme to align the target proteins to the interfaces of non-redundant protein-protein interface libraries. Docking of a pair of proteins utilizing the 22?600 interface PIFACE library is performed in?<?2?min on the average. A flexible version of the algorithm allowing hinge motion in one of the proteins is presented as well.To evaluate the performance of the algorithm a blind re-modelling of 3547 PDB complexes, which have been uploaded after the PIFACE publication has been performed with success ratio of about 35%. Interestingly, a similar experiment with the template free PatchDock docking algorithm yielded a success rate of about 23% with roughly 1/3 of the solutions different from those of SnapDock. Consequently, the combination of the two methods gave a 42% success ratio.A web server of the application is under development.michaelestrin@gmail.com or wolfson@tau.ac.il.
| S-EPMC5870628 | biostudies-literature
Project description:GC skew is a phenomenon observed in many bacterial genomes, wherein the two replication strands of the same chromosome contain different proportions of guanine and cytosine nucleotides. Here we demonstrate that this phenomenon, which was first discovered in the mid-1990s, can be used today as an analysis tool for the 15,000+ complete bacterial genomes in NCBI's Refseq library. In order to analyze all 15,000+ genomes, we introduce a new method, SkewIT (Skew Index Test), that calculates a single metric representing the degree of GC skew for a genome. Using this metric, we demonstrate how GC skew patterns are conserved within certain bacterial phyla, e.g. Firmicutes, but show different patterns in other phylogenetic groups such as Actinobacteria. We also discovered that outlier values of SkewIT highlight potential bacterial mis-assemblies. Using our newly defined metric, we identify multiple mis-assembled chromosomal sequences in previously published complete bacterial genomes. We provide a SkewIT web app https://jenniferlu717.shinyapps.io/SkewIT/ that calculates SkewI for any user-provided bacterial sequence. The web app also provides an interactive interface for the data generated in this paper, allowing users to further investigate the SkewI values and thresholds of the Refseq-97 complete bacterial genomes. Individual scripts for analysis of bacterial genomes are provided in the following repository: https://github.com/jenniferlu717/SkewIT.
| S-EPMC7717575 | biostudies-literature
Project description:A fundamental question appears in many bioinformatics applications: Does a sequencing read belong to a large dataset of genomes from some broad taxonomic group, even when the closest match in the set is evolutionarily divergent from the query? For example, low-coverage genome sequencing (skimming) projects either assemble the organelle genome or compute genomic distances directly from unassembled reads. Using unassembled reads needs contamination detection because samples often include reads from unintended groups of species. Similarly, assembling the organelle genome needs distinguishing organelle and nuclear reads. While k-mer-based methods have shown promise in read-matching, prior studies have shown that existing methods are insufficiently sensitive for contamination detection. Here, we introduce a new read-matching tool called CONSULT that tests whether k-mers from a query fall within a user-specified distance of the reference dataset using locality-sensitive hashing. Taking advantage of large memory machines available nowadays, CONSULT libraries accommodate tens of thousands of microbial species. Our results show that CONSULT has higher true-positive and lower false-positive rates of contamination detection than leading methods such as Kraken-II and improves distance calculation from genome skims. We also demonstrate that CONSULT can distinguish organelle reads from nuclear reads, leading to dramatic improvements in skim-based mitochondrial assemblies.
| S-EPMC8340999 | biostudies-literature