An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT
Ahsan Sanaullah, Degui Zhi, Shaojie Zhang · 2025
Read An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT by Ahsan Sanaullah, Degui Zhi, Shaojie Zhang (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-2505-15698.txt.
Introduction
Ahsan Sanaullah, Degui Zhi, and Shaojie Zhang present a 2025 paper on finding long matches inside compressed genome-scale text. Their quarry is locally maximal exact matches: stretches shared by a query and a text that cannot be extended on the query side. Short ones are noise, so only matches past a length bar count.
Genomic data sets are too big for classic indexes but are highly repetitive. The authors work inside an index built on the runs of the Burrows-Wheeler transform, which shrinks with repetition. Their algorithm lists all long matches in expected time proportional to the pattern plus the output, using space tied to the run count. The method suits pan-genome searches where the same sequence recurs many times. It keeps queries fast as collections grow.
Catalog record
| CREATOR | Ahsan Sanaullah, Degui Zhi, Shaojie Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-15698
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT Ahsan Sanaullah, Degui Zhi, Shaojie Zhang Abstract String matching problems in bioinformatics are typically for finding exact substring matches between a query and a reference text. Previous formulations often focus on maximum exact matches (MEMs). However, multiple occurrences of substrings of the query in the text that are long enough but not maximal may not be captured by MEMs. Such long matches can be informative, especially when the text is a collection of similar sequences such as genomes. In this paper, we describe a new type of match between a pattern and a text that aren’t necessarily maximal in the query, but still contain useful matching information: locally maximal exact matches (LEMs). There are usually a large amount of LEMs, so we only consider those above some length threshold ℒ \mathcal{L} . These are referred to as long LEMs. The purpose of long LEMs is to capture substring matches between a query and a text that are not necessarily maximal in the pattern but still long enough to be important. Therefore efficient long LEMs finding algorithms are desired for these datasets. However, these datasets are too large to query on traditional string indexes. Fortunately, these datasets are very repetitive. Recently, compressed string indexes that take advantage of the redundancy in the data but retain efficient querying capability have been proposed as a solution. We therefore give an efficient algorithm for computing all the long LEMs of a query and a text in a BWT runs compressed string index. We describe an O ( m + o c c ) O(m+occ) expected time algorithm that relies on an O ( r ) O(r) words space string index for outputting all long LEMs of a pattern with respect to a text given the matching statistics of the pattern with respect to the text. Here m m is the length of the query, o c c occ is the number of long LEMs outputted, and r r is the number of runs in the BWT of the text. The O ( r ) O(r) space string index we describe relies on an adaptation of the move data structure by Nishimoto and Tabei. We are able to support L C P [ i ] LCP[i] queries in constant time given S A [ i ] SA[i] . In other words, we answer P L C P [ i ] PLCP[i] queries in constant time. Long LEMs may provide useful similarity information between a pattern and a text that MEMs may ignore. This information is particularly useful in pangenome and biobank scale haplotype panel contexts. Department of Computer Science, University of Central Florida, Orlando, FL, [email protected] School of Biomedical Informatics, University of Texas Health Science Center at Houston, Houston, TX, [email protected] Department of Computer Science, University of Central Florida, Orlando, FL, [email protected] ccs Theory of computation Pattern matching ccs Theory of computation Data compression keywords BWT, LEM, Long LEM, MEM, Run Length Compressed BWT, Move Data Structure, Pangenome † † runningtitle: Long LEM Query in BWT-Runs Space † † runningauthor: A. Sanaullah, D. Zhi, and S. Zhang † † copyright: Ahsan Sanaullah, Degui Zhi, and Shaojie Zhang † † funding: This work was supported by the National Institutes of Health grant R01 HG010086. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Bioinformatics sequence data is often large and very repetitive. Furthermore, efficient matching queries on the data are frequently needed for many biological analyses. Therefore, bioinformatics problems have incentivized and profited from the development of efficient string indexes. The Burrows-Wheeler transform (BWT) has thus been used in bioinformatics algorithms. The BWT is a permutation of a text that has found wide use in string indexing and data compression [ 11 ] . Position i in the BWT of the text is essentially the character behind the i -th lexicographically smallest suffix of the text. Therefore, adjacent characters of the BWT correspond to highly locally similar suffixes of the text. Therefore, the BWT of highly repetitive texts tends to have large runs of one character, with an overall small number of runs. The BWT of highly repetitive texts therefore compresses well. In fact, the number of runs in BWT, r , is sometimes used as a measure of the repetitiveness of a string [ 35 ] . Finally, given only the BWT of a text, the text can be reconstructed in linear time [ 11 ] and the BWT of a text can be constructed in linear time by construction of the suffix array [ 22 ] . The BWT ordering also allows efficient string indexes. In other words, given a pattern, find all occurrences of the pattern within the text. String indexes have been shown that output all occurrences of a pattern (a locate query) in space linear to the product of the length of the text and the size of the alphabet and time linear to the sum of the length of the pattern and the number of occurrences [ 18 ] . Compressed string indexes have also been shown [ 18 , 3 , 32 ] . These indexes output all occurrences of a pattern in space sublinear to the size of the text. Although the time complexity of locating these occurrences is not linear in the length of the pattern and the number of occurrences, they are typically independent of the length of the text barring logarithmic factors and close to linear in the length of the pattern and number of occurrences. In particular for highly repetitive texts, the space of the index can be much smaller than the space of the text. Notably, recent compressed string indexes have achieved space linear to the number of runs in the BWT ( r ) [ 19 , 36 ] . The r-index by Gagie et al. was the first compressed string index offering close to linear time locate queries in O(r) space [ 19 ] . Nishimoto and Tabei recently improved on this result with their OptBWTR, which achieves linear time locate queries for texts with alphabets of size polylogarithmic in the length of the text. OptBWTR relies on the move data structure, which was also introduced by Nishimoto and Tabei [ 36 ] . Compressed string indexes have been fruitfully applied to the growing collection of bioinformatics data. Over the past two decades, large collections of genomics data have grown increasingly larger in size. For example, the UK Biobank has whole genome sequencing data of roughly one million haplotypes [ 29 ] , and the All of Us program has released whole genome sequencing data of half a million haplotypes [ 7 ] . Furthermore, recent arguments have been made that a human reference pangenome should be used instead of a singular human reference