Finding low-complexity DNA sequences with longdust

Heng Li \ORCID 0000-0003-4874-2874, Brian Li · 2025

Read Finding low-complexity DNA sequences with longdust by Heng Li \ORCID 0000-0003-4874-2874, Brian Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07357.txt.

Introduction

Repetitive stretches of DNA cause false matches in genome searches and errors in variant calling. Heng Li and Brian Li introduce longdust in a 2025 research paper. Longdust is an algorithm that finds low-complexity sequences, regions built from short repeating patterns. Older tools either lacked a clear mathematical definition of complexity or ran slowly on long context windows.

Longdust defines complexity by modeling counts of short DNA words called k-mers. Users set the word length, window size, and a complexity threshold. The tool catches long repeats, including centromeric satellite DNA and tandem repeats with fairly long motifs. Tests on real data show strong performance and good agreement with existing methods. The code is freely available, so genome pipelines can add it as a cleaning step.

Catalog record

CREATORHeng Li \ORCID 0000-0003-4874-2874, Brian Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07357

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Finding low-complexity DNA sequences with longdust Heng Li \ORCID 0000-0003-4874-2874, Brian Li Abstract Motivation: Low-complexity (LC) DNA sequences are compositionally repetitive sequences that are often associated with increased variant density and variant calling artifacts. While algorithms for identifying LC sequences exist, they either lack rigorous mathematical foundation or are inefficient with long 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 k -mer count distribution with the parameters: the k 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 \ast ]Corresponding author. [email protected] † † journal: TBD † † doi: TBD † † copyright-year: 2025 † † year: 2025 † † access: Advance Access Publication Date: Day Month Year † † appnotes: Preprint † † firstpage: 1 † † address: Department of Biomedical Informatics, Harvard Medical School, 10 Shattuck St, Boston, MA 02215, USA † † address: Department of Data Science, Dana-Farber Cancer Institute, 450 Brookline Ave, Boston, MA 02215, USA † † address: Broad Insitute of MIT and Harvard, 415 Main St, Cambridge, MA 02142, USA † † address: Commonwealth School, Boston, MA 02116, USA † † corresponding: [ 1 Introduction In computer science, a string is of low complexity (LC) if it is repetitive in composition. LC strings tend to be tandemly repetitive and most of them can be identified with tandem repeat finding algorithms such as TRF ( Benson, 1999 ) , TANTAN ( Frith, 2011 ) , ULTRA ( Olson and Wheeler, 2024 ) and pytrf ( Du et al., 2025 ) . These algorithms do not rigorously define string complexity. They rely on heuristics to search for impure tandem repeats and cannot identify LC strings without clear tandem structures. SDUST ( Morgulis et al., 2006 ) is the only widely used algorithm that explicitly defines string complexity and finds the exact solutions. However, with O(w^{3}L) time complexity, where w is the window size and L is the genome length, SDUST is inefficient given a large w and is thus impractical for finding satellite or tandem repeats with long motifs. Furthermore, the complexity scoring function used by SDUST is not backed by rigorous modeling. The theoretical properties of LC strings defined this way are unclear. Inspired by SDUST, we sought an alternative way to define the k -mer complexity of a string and to identify LC regions in a genome. Our complexity scoring function is based on a statistical model of k -mer count distribution and our algorithm is practically close to O(wL) in time complexity, enabling the efficient identification of LC strings in long context windows. 2 Methods Similar to SDUST ( Morgulis et al., 2006 ) , we define the complexity of a DNA string with a function of the k -mer counts of the string. In this section, we will first model the k -mer count distribution of random strings. We will then describe the complexity scoring function and the condition on bounding LC substrings in a long string. We will compare our method to SDUST in the end. 2.1 Notations Let \Sigma=\{{\tt A},{\tt C},{\tt G},{\tt T}\} be the DNA alphabet, x\in\Sigma^{*} is a DNA string and |x| is its length. t\in\Sigma^{k} is a k -mer. For |x|\geq k , c_{x}(t) is the occurrence of k -mer t in x ; \ell(x)=\sum_{t}c_{x}(t)=|x|-k+1 is the total number of k -mers in x . \vec{c}_{x} denotes the count array over all k -mers. In this article, we assume there is one long genome string of length L . We use closed interval [i,j] to denote the substring starting at i and ending at j , including the end points i and j . We may use “interval” and “subsequence” interchangeably. 2.2 Modeling k -mer counts Suppose symbols in \Sigma all occur at equal frequency. Then for all k -mer t , c_{x}(t)\sim{\rm Poisson}(\lambda) where \lambda=\ell(x)/4^{k} . Let p(n|\lambda)\triangleq\frac{\lambda^{n}}{n!}e^{-\lambda} be the probability mass function of Poisson distribution. Notably, although c_{x}(t)\leq\ell(x) , given that \ell(x)\gg 1 in practice, p(\ell|\lambda)\approx\frac{e^{-\lambda}}{\sqrt{2\pi\ell}}\cdot\left(\frac{e}{4^{k}}\right)^{\ell}\ll 1 with the Sterling formula – p(\ell|\lambda) is very close to 0. This suggests Poisson remains a good approximation. The composite probability of string x can be modeled by P(\vec{c}_{x})=\prod_{t\in\Sigma^{k}}p(c_{x}(t)|\lambda) We have \log P(\vec{c}_{x})=4^{k}\lambda(\log\lambda-1)-\sum_{t}\log c_{x}(t)! (1) To get an intuition about P(\vec{c}_{x}) , suppose \ell(x)\ll 4^{k} . In this case, c_{x}(t) will be mostly 0 or 1 for a random string and the last term in Eq. ( 1 ) will be close to 0. Given an LC string of the same length, we will see more c_{x}(t) of 2 or higher, which will reduce \log P(\vec{c}_{x}) . Thus the probability of an LC string is lower under this model. Although \log P(\vec{c}_{x}) can be used to compare the complexity of strings of the same length, it does not work well for strings of different lengths because \log P(\vec{c}_{x}) decreases with \ell(x) . We would like to scale it to Q(\vec{c}_{x}) such that Q approaches 0 given a random string. We note that on the assumption of equal base frequency, the average of \log P(\vec{c}_{x}) can be approximated to \displaystyle H(\lambda) \displaystyle\triangleq \displaystyle\sum_{\vec{c}}P(\vec{c})\cdot\sum_{t}\log p(c_{t}|\lambda) \displaystyle= \displaystyle 4^{k}\sum_{n=0}^{\infty}p(n|\lambda)\log p(n|\lambda) \displaystyle= \displaystyle 4^{k}\lambda(\log\lambda-1)-4^{k}e^{-\lambda}\sum_{n=0}^{\infty}\log n!\cdot\frac{\lambda^{n}}{n!} which is the negative entropy of P . We can thus define Q(\vec{c}_{x})\triangleq H(\lambda)-\log P(\vec{c}_{x})=\sum_{t}\log c_{x}(t)!-f\left(\frac{\ell(x)}{4^{k}}\right) where f(\lambda)\triangleq 4^{k}e^{-\lambda}\sum_{n=0}^{\infty}\log n!\cdot\frac{\lambda^{n}}{n!} Q(\vec{c}_{x}) is higher for LC string x . 2.3 Scoring low-complexity intervals To put a threshold on the complexity, we finally use the following function to score string complexity: S(\vec{c}_{x})\triangleq Q(\vec{c}_{x})-T\cdot\ell(x)=\sum_{t}\log c_{x}(t)!-T\cdot\ell(x)-f\left(\frac{\ell(x)}{4^{k}}\right) (2) Threshold T controls the level of complexity in the output. It defaults to 0.6 , less than \log 2 . If S(\vec{c}_{x})>0 , x is considered to contain an LC substring. Note that we often do not want to classify the entire x as an LC substring in this case because the concatenation of a highly repetitive sequence and a random sequence could still lead to a positive score. Recall that we may use close intervals to represent substrings. For convenience, we write S(\vec{c}_{[i,j]}) as S(i,j) . In implementation, we precalculate f(\ell/4^{k}) and introduce \displaystyle U(i,j) \displaystyle\triangleq \displaystyle\sum_{t}\log c_{[i,j]}(t)!-T\cdot\ell([i,j]) \displaystyle= \displaystyle U(i,j-1)+\log c_{[i,j]}([j-k+1,j])-T We can thus compute the complexity scores of all prefixes of [i,j] by scanning each base in the interval from left to right; we can similarly compute all suffix scores from right to left. 2.4 Finding low-complexity regions We say x is a perfect LC string (or perfect LC interval ) if S(\vec{c}_{x})>0 and no substring of x is scored higher than S(\vec{c}_{x}) ; say x is a good LC string (or good LC interval ) if S(\vec{c}_{x})>0 and no prefix or suffix of x is scored higher than S(\vec{c}_{x}) . We can use U(i,j) above to test if [i,j] is a good LC interval in linear time. If we apply this method to all intervals up to w in length (5000bp by default), we can find LC regions of context length up to w in O(w^{2}L) time. The union of all good LC intervals marks the LC regions in a genome. {algorithm} [bt] Find LC

Read the complete text