Algorithms and Data Compression

aaHash is a recursive amino acid sequence hashing algorithm that improves speed and sensitivity for protein sequence analysis.

The paper introduces a method to reduce the space required for reference indexing by using spectrum preserving tilings and sampling schemes, achieving significant space savings with minimal query slowdown.

The paper introduces exact algorithms and approximate heuristics for mapping sequences onto De Bruijn graphs using edit distance as a similarity metric.

The paper introduces Syllable-PBWT, a space-efficient data structure for haplotype long-match queries, reducing memory use by over 100 times compared to existing methods.

The paper introduces the GBZ file format for efficiently storing pangenome graphs, providing compression tools and demonstrating efficient system usage.

The paper introduces a dataset-adaptive minimizer order method to reduce memory usage in k-mer counting with minimal runtime increase.

The paper shows that the minimizer Jaccard estimator is biased and inconsistent, affecting the accuracy of sequence similarity estimation and a read mapping tool.

The paper introduces a compressed k-mer dictionary that improves space/time efficiency using statistical properties of k-mer minimizers.

CoLoRd compresses third-generation sequencing data by an order of magnitude without affecting downstream analysis accuracy.

BWA-MEME improves short-read alignment efficiency by using a machine learning approach to reduce computational overhead while maintaining accuracy.

The paper develops faster and more memory-efficient tools for computing and analyzing matching statistics between large genomes, enabling practical applications in comparative genomics.

The paper introduces Set-Min sketch, a probabilistic data structure for representing k-mer count tables with improved accuracy over existing methods.

CRAM 3.1 improves compression efficiency for DNA sequencing data, reducing file sizes by 7-15% compared to CRAM 3.0 and 50-70% compared to BAM for Illumina data.

The paper introduces mcPBWT, an algorithm for efficiently scanning composite haplotype patterns in PBWT data, identifying crossover events and gene-conversion tracts.

This paper presents efficient algorithms for co-linear chaining with anchor overlaps and gap costs, showing strong correlation with edit distance.

kmtricks improves Bloom filter construction for large sequencing data by efficiently counting k-mers and preserving low-abundant ones, enhancing metagenomics analysis.

The paper introduces a differentiable framework for optimizing sequence-specific minimizer schemes, showing improved performance on genomic sequences.

MBGC is a specialized genome compressor for bacteria that achieves high compression ratios and speeds, outperforming existing tools on bacterial genomes.

The paper introduces an optimized FM-index library for nucleotide and amino acid sequence search, showing improved speed and scalability over existing implementations.

The paper develops a theoretical framework for evaluating k-mer selection methods and demonstrates improved long-read alignment using an optimized method.

FASTAFS provides a filesystem virtualization solution for compressed FASTA files, enabling fast random access and metadata management.

This paper improves population genetic data compression and GWAS computation using finite-state entropy algorithms, achieving 10-40% speed and size improvements over dictionary compression methods.

The paper demonstrates that using universal hitting sets improves de Bruijn graph construction efficiency by reducing runtime and memory usage in genome assembly.

Raptor is a fast and memory-efficient tool for searching large nucleotide sequence collections, outperforming existing tools in speed and memory usage.

RENANO improves nanopore FASTQ compression by 39.8% for base call sequences using reference-based methods, with overall improvements of 12.7% in some scenarios.

The paper introduces polar sets for sequence-specific minimizer construction, showing their effectiveness on the human reference genome.

The paper introduces RowDiff, a method to compactly store graph labels by exploiting annotation similarities, achieving significant space reductions when combined with compression techniques.

The paper introduces RLZ-Graph, a space-efficient genome graph constructed using Lempel-Ziv compression, reducing disk space by 40.7% compared to colored de Bruijn graphs.

VCFShark compresses VCF files more efficiently than standard methods, reducing their size by up to an order of magnitude.

The paper introduces d-PBWT, a dynamic version of the PBWT data structure, enabling efficient insertion and deletion of haplotypes while maintaining PBWT functionality.