Genomic tessellations

Periodicity is ubiquitous in genomic data. Assembled sequences are dense with homopolymers, microsatellites, and large satellite arrays, which contribute to phenotype, variation, and disease. Third-generation sequencing technologies, such as Oxford Nanopore (ONT) and PacBio HiFi, has enabled longer and increasingly accurate reads, but have brought with them systematic error biases in repetitive regions, where insertions and deletions can distort array lengths and mimic or obscure biological variation. This periodicity is not benign: local repetitiveness makes sequence alignment ambiguous and genome assembly error-prone. In sequence analysis, these two manifestations of periodicity are simultaneously at play, each compounding the challenges of the other; a unified representation of repetitive and non-repetitive sequence is necessary to account for their combined effects consistently. We propose a paradigm under which (either repetitive and non-repetitive) DNA is split into its identity (its irreducible components) and its geometry (how its components are realized). A genomic tessellation τ is a canonical factorization of any sequence S of length n over the DNA alphabet into a sequence of tiles partitioning S , where each t in τ S is described as a quasi-periodic run of a canonical unit identity u t with geometry consisting of span s t , phase φ t , and a set of exceptions X t . We show that, for a prescribed error bound k ≥ 1 and fixed maximum unit length P , S can be tessellated in O(n) time such that every tile has a unique identity whose periodic expansion differs from the tiled sequence by at most k edits, and that tiles sharing an identity are related by a bounded number of geometric adjustments. We introduce the tessellated Burrows-Wheeler transform (tBWT), which indexes τ S by concatenating, over all tiles in order, the identity u t of each tile. For a tessellated query q of m tiles, the tBWT counts the repeat-agnostic occurrences of q in O(m) time, and for sampling interval r locates its h occurrences in τ S in O(m + hr) time. We demonstrate that tessellations avoid the well-known speed-accuracy tradeoff and outperform state-of-the-art long-read mappers in repeat-dense regions in both speed and accuracy. On a 20× simulated set of both ONT and HiFi reads on the HG002 maternal X chromosome with synthetically-expanded repeat arrays, locating and chaining exact tile identity matches obtained from the tBWT is up to 57× and 83× faster, respectively, than the state-of-the-art mappers minimap2 and Winnowmap2, with comparable accuracy. Furthermore, by abstracting away differences in geometry, tessellations of a set of input sequences onto itself (an autotessellation ) reveals homology otherwise obscured by array-length variation and local sequence divergence. A geometry-only polishing of an an ONT-only assembly of the HG002 maternal X chromosome with ∼50× PacBio HiFi reads improves assembly QV from 45.4 to 60.6 in under a minute using less than 10GB of memory. Tessellated-read evidence over the autotessellation of this assembly organizes 167 mitochondrial contigs totaling ∼4 Mbp into a single family with a ∼16.5kbp representative, which aligns to the HG002 Q100 mitochondrial genome with 100% identity. Genomic tessellations provide a canonical representation of repetitive and non-repetitive DNA and enable efficient sequence analyses while preserving homology.

Authors

Institutions

Publication Details

Journal
bioRxiv (Cold Spring Harbor Laboratory)
Published
2026-11-16
DOI
https://doi.org/10.64898/2026.11.13.766490
Primary Topic
Algorithms and Data Compression
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Genomic tessellations

Haoyu Cheng, Barış Ekim
bioRxiv (Cold Spring Harbor Laboratory)
Algorithms and Data Compression
preprint

Genomic tessellations

Haoyu Cheng, Barış Ekim
preprint en

Abstract

Periodicity is ubiquitous in genomic data. Assembled sequences are dense with homopolymers, microsatellites, and large satellite arrays, which contribute to phenotype, variation, and disease. Third-generation sequencing technologies, such as Oxford Nanopore (ONT) and PacBio HiFi, has enabled longer and increasingly accurate reads, but have brought with them systematic error biases in repetitive regions, where insertions and deletions can distort array lengths and mimic or obscure biological variation. This periodicity is not benign: local repetitiveness makes sequence alignment ambiguous and genome assembly error-prone. In sequence analysis, these two manifestations of periodicity are simultaneously at play, each compounding the challenges of the other; a unified representation of repetitive and non-repetitive sequence is necessary to account for their combined effects consistently. We propose a paradigm under which (either repetitive and non-repetitive) DNA is split into its identity (its irreducible components) and its geometry (how its components are realized). A genomic tessellation τ is a canonical factorization of any sequence S of length n over the DNA alphabet into a sequence of tiles partitioning S , where each t in τ S is described as a quasi-periodic run of a canonical unit identity u t with geometry consisting of span s t , phase φ t , and a set of exceptions X t . We show that, for a prescribed error bound k ≥ 1 and fixed maximum unit length P , S can be tessellated in O(n) time such that every tile has a unique identity whose periodic expansion differs from the tiled sequence by at most k edits, and that tiles sharing an identity are related by a bounded number of geometric adjustments. We introduce the tessellated Burrows-Wheeler transform (tBWT), which indexes τ S by concatenating, over all tiles in order, the identity u t of each tile. For a tessellated query q of m tiles, the tBWT counts the repeat-agnostic occurrences of q in O(m) time, and for sampling interval r locates its h occurrences in τ S in O(m + hr) time. We demonstrate that tessellations avoid the well-known speed-accuracy tradeoff and outperform state-of-the-art long-read mappers in repeat-dense regions in both speed and accuracy. On a 20× simulated set of both ONT and HiFi reads on the HG002 maternal X chromosome with synthetically-expanded repeat arrays, locating and chaining exact tile identity matches obtained from the tBWT is up to 57× and 83× faster, respectively, than the state-of-the-art mappers minimap2 and Winnowmap2, with comparable accuracy. Furthermore, by abstracting away differences in geometry, tessellations of a set of input sequences onto itself (an autotessellation ) reveals homology otherwise obscured by array-length variation and local sequence divergence. A geometry-only polishing of an an ONT-only assembly of the HG002 maternal X chromosome with ∼50× PacBio HiFi reads improves assembly QV from 45.4 to 60.6 in under a minute using less than 10GB of memory. Tessellated-read evidence over the autotessellation of this assembly organizes 167 mitochondrial contigs totaling ∼4 Mbp into a single family with a ∼16.5kbp representative, which aligns to the HG002 Q100 mitochondrial genome with 100% identity. Genomic tessellations provide a canonical representation of repetitive and non-repetitive DNA and enable efficient sequence analyses while preserving homology.

bioRxiv (Cold Spring Harbor Laboratory)
Yale University (US)
Algorithms and Data Compression
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon