Algorithms and Data Compression

Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index

This paper introduces a mixed integer program to find optimal search schemes for approximate string matching using bidirectional FM-index, significantly improving speed over previous methods.

Asymptotically optimal minimizers schemes

The paper analyzes minimizers schemes and shows that asymptotically optimal schemes with lower density than previously thought exist, leading to more efficient bioinformatics tools.

AllSome Sequence Bloom Trees

The paper introduces an improved Sequence Bloom Tree data structure that enhances query performance for RNA-seq databases.

Improved Search of Large Transcriptomic Sequencing Databases Using Split Sequence Bloom Trees

The paper introduces an improved indexing method, Split Sequence Bloom Tree (SSBT), for efficiently searching large RNA-seq databases and demonstrates its performance on breast, blood, and brain tissue data.

FaStore - a space-saving solution for raw sequencing data

FaStore compresses FASTQ files with lossy modes, achieving better compression ratios than existing methods while maintaining variant calling accuracy.

Metannot: A succinct data structure for compression of colors in dynamic de Bruijn graphs

The paper introduces a dynamic data structure called Metannot for compressing and indexing graph metadata in HTS data, achieving better compression ratios than existing methods.

GTC: a novel attempt to maintenance of huge genome collections compressed

GTC is a compressed data structure for genetic variation data that improves compression ratio and query speed compared to existing solutions.

TahcoRoll: An Efficient Approach for Signature Profiling in Genomic Data through Variable-Length k-mers

TahcoRoll improves k-mer profiling by efficiently handling variable-length k-mers, outperforming existing tools in time and memory usage without disk space.

Aligning sequences to general graphs in O(V + mE) time

The paper introduces an algorithm to align sequences to node-labeled directed graphs in O(V + mE) time, improving efficiency for genome assembly and variant calling.

ChIPWig: A Random Access-Enabling Lossless And Lossy Compression Method For ChIP-Seq Data

ChIPWig compresses ChIP-seq Wig data with lossless and lossy modes, achieving high compression rates while preserving peak calling and motif discovery accuracy.

Analytic combinatorics for bioinformatics I: seeding methods

The paper introduces a theoretical framework using analytic combinatorics to estimate the success rate and error rates of seeding heuristics in bioinformatics.

Squeakr: An Exact and Approximate k-mer Counting System

Squeakr is a k-mer counting and multiset representation system that improves speed and memory efficiency compared to existing methods.

CHIC: a short read aligner for pan-genomic references

CHIC is a short-read aligner designed for pan-genomic references, using a hybrid compression and alignment approach to handle large and repetitive datasets.

Quark enables semi-reference-based compression of RNA-seq data

Quark compresses RNA-seq data using a semi-reference-based approach, achieving better compression than reference-free methods while allowing reference-free decompression.

Rainbowfish: A Succinct Colored de Bruijn Graph Representation

Grouping k-mer color sets into equivalence classes and entropy-compressing them shrinks colored de Bruijn graph color storage up to 20-fold versus VARI, keeping BOSS for topology.

LEAP: A Generalization Of The Landau-Vishkin Algorithm With Custom Gap Penalties

The paper introduces LEAP, a generalized algorithm for approximate string matching that outperforms existing methods in speed under various scoring schemes.

Improving the performance of minimizers andwinnowing schemes

The paper improves minimizers and winnowing schemes by analyzing k-mer ordering and introducing universal hitting sets to enhance performance.

Bit-twiddling on Nucleotides

The paper explores bit manipulation techniques for nucleotide data to improve computational efficiency.