Finding low-complexity DNA sequences with longdust

2025/09/09 by Heng Li, Brian Li, Li, Heng +1 · 2 voices · 1 citation
#q-bio.GN

paper · pdf · doi:10.48550/arxiv.2509.07357

Abstract

Motivation: Low-complexity (LC) DNA sequences are compositionally repetitive sequences that are often associated with spurious homologous matches and variant calling artifacts. While algorithms for identifying LC sequences exist, they either do not define complexity mathematically or are inefficient with long or variable context windows. Results: Longdust is a new algorithm that efficiently identifies long LC sequences including centromeric satellite and tandem repeats with moderately long motifs. It defines string complexity by statistically modeling the k-mer count distribution with the parameters: the k-mer length, the context window size and a threshold on complexity. Longdust exhibits high performance on real data and high consistency with existing methods. Availability and implementation: https://github.com/lh3/longdust

Citations

• Challenges in structural variant calling in low-complexity regions
• Complete sequencing of ape genomes

Cited by

• Challenges in structural variant calling in low-complexity regions

Discussions

• Now preprinted at arxiv.org/abs/2509.07357 [bsky, 22 points, 0 comments]
• Heng Li, Brian Li: Finding low-complexity DNA sequences with longdust https://arxiv.org/abs/2509.07357 https://arxiv.org/pdf/2509.07357 https://arxiv.org/html/2509.07357 [bsky, 0 points, 0 comments]

Related

• Fast low-level pattern matching algorithm
• Constrained Consensus Sequence Algorithm for DNA Archiving
• New Error Tolerant Method to Search Long Repeats in Symbol Sequences
• Finding Approximate Palindromes in Strings Quickly and Simply
• Introducing difference recurrence relations for faster semi-global alignment of long sequences