Search bioRxiv⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.1101/2025.07.22.666196

Efficient Grammar Compression via RLZ-based RePair

Varki, R.·Gagie, T.·Boucher, C.
View original source ↗Export metadata ↓

Abstract

Among grammar-based compression techniques, RePair is a notable offline encoding scheme known for its simplicity and powerful combinatorial properties, producing compact grammars by repeatedly replacing the most frequent adjacent pairs of symbols, known as bigrams. However, RePairs memory usage scales poorly with input size, as it loads the entire text into memory. In contrast, Relative Lempel-Ziv (RLZ) parsing offers a scalable and lightweight online encoding scheme that losslessly represents a text in terms of phrases that refer to a reference string, but it often fails to expose deeper structural patterns. We introduce an algorithm that produces a RePair grammar from the RLZ parse of the input, leveraging the strengths of both methods. Our method, RLZ-RePair, performs bigram replacements systematically, preserving the integrity of the RLZ phrases throughout the RePair iterations. When the reference is well chosen, our method achieves the same grammar as standard RePair while significantly reducing both memory usage and the number of bigram replacements. In particular, we show that RLZ-RePair can reduce memory usage by more than 80% while incurring only a modest runtime increase compared to RePair. To our knowledge, RLZ-RePair is one of the first scalable methods that constructs exact RePair grammars, resulting in a grammar-based compressor that is both practical for large datasets and faithful to the theoretical elegance of RePair.

Explore related subjects

genomicsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Varki, R., Gagie, T., Boucher, C.. 2025-07-26. Efficient Grammar Compression via RLZ-based RePair. https://doi.org/10.1101/2025.07.22.666196

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related preprints

bioRxiv2026

Sequence and epigenetic characterization of chromosome 21 centromeres in a family with recurrent Trisomy 21

Trisomy 21 (T21) is the most common genetic cause of intellectual disability, yet the molecular mechanisms underlying maternal meiosis I errors--responsible for ~70% of free T21 cases--remain poorly understood. In this preliminary study, we used long-read sequencing and genome assembly to investigate the DNA sequence and epigenetic features of chromosome 21 (chr21) centromeres in a family with recurrent free T21 due to maternal meiosis I errors. The mother, who had two affected and three unaffected children, showed no mosaicism or structural rearrangements. One of her two chr21 centromeres lacked a pronounced centromere dip region (CDR), displaying instead a diffuse hypomethylation pattern (dCDR) with much higher methylated CpG levels (55%) compared to its homologue (36%). This dCDR was transmitted to an unaffected child and the affected proband analyzed, suggesting it was present in one of the maternal chr21 since she was at least 32 years of age. Chr21 dCDRs were not observed in seven young mothers with children with T21 or previously described in the literature in 108 population haplotypes. We hypothesize that dCDRs may weaken kinetochore function, increasing nondisjunction risk, and propose two models linking such epigenetic variation to maternal age-related T21 risk. These findings highlight the value of complete centromere characterization in families with children with T21 and suggest centromere methylation status of chr21 as a potential T21 risk factor for future investigation.

genomics↗
bioRxiv2026

Single-Cell Analytics for Dose Response (SCADR) discriminates PTEN missense variants by lipid and protein phosphatase dysfunction

The proliferation of sequencing efforts has revealed a vast and expanding catalog of single nucleotide gene variants, many associated to, but with unclear roles in disease. Fully charactering variant impacts and linking specific protein dysfunctions to disease are challenging due to the multi-functional nature of many proteins and varying degree of variant effects on these functions. Lagging are sensitive approaches to empirically assess the impact of missense variant-induced single amino acid changes on a wide range of protein functions. To address these issues, we have developed an open-source computational analysis tool called SCADR (Single-Cell Analytics for Dose Response) for simultaneously measuring and comparing impacts of exogenously-expressed variants on multiple signaling pathways using multiplex phospho-antibody spectral flow cytometry in human cell lines. SCADR retains and correlates single-cell measures of signal protein activity states along with expression levels of exogenously-expressed variants, providing rich characterization of multiple protein functions, signaling protein interactions, and enhanced discrimination of variant impacts on different signaling pathways, highlighting each variants unique dysfunction profile. Here, we apply SCADR for analyses of the impact of 6 variants of the tumor-suppressor protein PTEN (P38H, C124S, G129E, Y138L, D268E, 4A) expressed in HEK293 cells on the phosphorylation states of the canonical and noncanonical downstream signaling proteins Akt, S6, CREB, ERK, and p38 detected with fluorophore-conjugated phospho-antibodies, along with an antibody detecting an N-terminal HA tag on PTEN variants allowing measures of dose-response effects of each variants expression on signaling cascades. Results identify variant-specific impacts on downstream signaling cascades.

genomics↗
bioRxiv2026

Microsecond molecular dynamics of SOD1 variants suggest a structural basis for divergent ALS clinical outcomes

Amyotrophic lateral sclerosis (ALS) is a fatal neurodegenerative disease characterised by progressive motor neuron degeneration. Mutations in the SOD1 gene represent the second most common genetic cause of ALS (ALS), and distinct SOD1 missense variants present with markedly different clinical profiles. A4V leads to an aggressive form of the disease (median survival [~]1y), H46R confers a mild, slowly progressive course and I113T exhibits an intermediate phenotype. The molecular basis by which these mutations produce divergent clinical outcomes remains poorly understood. We performed extensive classical molecular dynamics simulations of wild-type SOD1 and the three ALS-associated variants in the apo monomeric state to attempt to investigate the mechanisms behind such phenotypic differences. Structural stability, global compactness, and conformational flexibility, as well as analysis of collective motions between residues and estimation of free energy, were assessed. The H46R, A4V, and I113T variants exhibited distinct dynamic behaviours, highlighting differences in structural stability, local flexibility, and intramolecular interactions. These findings suggest that specific structural regions may contribute differently to protein dysfunction and could represent key elements for understanding the relationship between molecular dynamic properties and the differing clinical severity associated with these variants. Most strikingly, H46R exhibited exceptional structural stability across every analytical level, the lowest global deviation, most attenuated local flexibility, strongest internal dynamic coordination, and the deepest, most confined free energy basins of any system examined. This convergent multi-layered evidence of structural restraint provides a compelling mechanistic basis for the mild and slowly progressive clinical course of H46R ALS, suggesting that enhanced conformational rigidity, rather than bulk destabilisation, is the defining biophysical feature of this variant, and that its pathogenic mechanism operates through a route fundamentally decoupled from the aggregation-driven toxicity that characterises the more aggressive SOD1-ALS mutations.

genomics↗