Biology subjects

Sanaullah, A.

Publications and source records attributed to Sanaullah, A..

9 recordsLinked to original sources

bioRxiv2026

Detection of Maximal Exact Matches in Terabases of Genome Assemblies in Compressed Space and Sublinear Time

Detection of long exact matches between a pair of genomes has historically been a fundamental operation in genomics. Similarly, detection of long exact matches between all pairs of haplotypes in a large panel of genotyping array data or whole-genome sequencing variant calls is a fundamental operation in population genetics. Thanks to various recent pangenome efforts, for the first time, large panels of high-quality genome assemblies are being constructed. Therefore, we propose the intersection of these two approaches: detection of long exact matches between all pairs of assemblies in panels of hundreds to thousands of high-quality assemblies. Since these datasets would contain trillions of basepairs, practically detecting all exact matches requires algorithms operating in at most linear time and compressed space. Previous methods such as Mumemto achieve this, but running them on terabase-sized pangenomes still took very large space and long time. Here, we describe more efficient algorithms for outputting all long exact matches between all pairs of assemblies in compressed space and sublinear time given a compressed index of the panel. Given the construction of an O(r) space compressed index--a one-time cost that can be done in compressed space and close to linear time with previous work--we describe three algorithms taking O(r) words of memory: (1) computing all supermaximal exact matches (SMEMs) in O(r) time, (2) computing all supermaximal exact matches and their occurrences in O(r + occ) time, and (3) computing all maximal exact matches (MEMs) in O(r + occ) time, where r is the number of runs in the Burrows-Wheeler transform of the panel of assemblies and occ is the number of occurrences or matches outputted. Our algorithms use 7.5 times less memory than state-of-the-art competitors on a dataset of human centromere assemblies from 625 haplotypes. They are also 20 times faster if index construction time is counted, and 2,500 times faster if index construction is excluded. Finally, we perform an analysis of all-vs-all MEMs in all well-assembled centromeres of the Human Pangenome Reference Consortium Release 2 dataset that reveals multiple novel insights into structural variation in centromeres. For example, we find that the active -satellite higher-order repeat (HOR) array of Chromosome 2 is flanked by a ~200 kbp inversion on one side and a ~200-300 kbp pseudopalindromic sequence on the other. We also detect large segmental duplications in the centromere of every chromosome except Chromosome Y. These segmental duplications range in size from hundreds of kbp to multiple Mbp and occur both in and out of the active -satellite HOR arrays. Our computational results make pairwise MEM analyses possible in pangenomes, while our biological results show they are likely to be useful. Our algorithms are implemented as TeraMEM in the TeraTools suite available at https://github.com/ucfcbb/TeraTools.

bioinformatics↗

bioRxiv2026

Fast Pangenome Matching Statistics in Compressed Space with Move Structures

Matching statistics and supermaximal exact matches (SMEMs) are key inputs for sequence homology search and classification. Methods such as MONI, PHONI, and ropebwt3 compute these statistics using compressed pangenome indexes, but are substantially slower than methods that compute approximations of matching statistics, such as pseudo-matching lengths (PMLs). PMLs can be computed quickly in a single pass, but SMEM computation can require overlapping forward or backward passes over the query. We present ms2, a suite of algorithms that use "move structures" to compute matching statistics and SMEMs efficiently in compressed space. Our four algorithms compose move structures for the LF, {Psi}, {varphi}, and {varphi}-1 permutations with additional longest common prefix (LCP) array summaries and samples. The algorithms offer different tradeoffs among speed, index size, and support for reporting SMEM offsets. They inherit the move structure's fast, constant-time operations and achieve high throughput by leveraging the move structure's locality of reference. Thanks to recent advances, move structures can be constructed in optimal time and compressed space, including the LCP information needed for "match recovery" during SMEM computation. On 100 haplotypes of human chromosome 22, ms2's fastest algorithm computes matching statistics 35 to 48 times as fast as PHONI's online approach, while using an index of similar size. On the 472-haplotype HPRC2 pangenome and human reads, three ms2 modes achieve speedups of at least 22, 19, and 15 times over ropebwt3, whose index is about 15% the size of ms2's fastest mode. When additionally reporting SMEMs and their offsets, ms2 achieves speedups of 25 to 34 times over ropebwt3. Together, these advances enable online computation of matching statistics and SMEMs at a throughput that supports real-time processing of approximately 21 PromethION nanopore flow cells on a single thread. The ms2 software is open source and available at https://github.com/langmead-lab/ms2. It builds on the open-source TeraTools suite (https://github.com/ucfcbb/TeraTools) and Orbit library (https://github.com/drnatebrown/orbit). Experimental scripts and other details are described in: https://github.com/langmead-lab/ms2-experiments.

bioinformatics↗

bioRxiv2026

SLAB: A Sweep Line Algorithm in PBWT for Finding Haplotype Block Cores

With the increasing availability of high-quality phased haplotype data, researchers can more effectively identify detailed patterns of haplotype sharing and investigate the population genetic processes that shape them. In this work, we define block cores as genomic segments where multiple haplotype blocks overlap. We develop an efficient algorithm to analyze haplotype blocks, focusing on width-maximal matches and the identification of haplotype block cores. We apply our algorithm to UK Biobank haplotypes to quantify block cores and demonstrate the biological and population-level insights that can be inferred from their patterns. Specifically, identified block cores can serve as a basis for detecting signals of selection. Although our results are largely consistent with those from methods such as IBD rate analysis, they also reveal complementary information not captured by IBD rates or other conventional approaches. Source code is available at https://github.com/ZhiGroup/SLAB.

bioinformatics↗

bioRxiv2026

RLBWT-Based LCP Computation in Compressed Space for Terabase-Scale Pangenome Analysis

Lossless full text indexes are utilized in a myriad of applications in bioinformatics. The continuously decreasing cost of generating biological data has resulted in the need to build full text indexes on biological datasets of increasing size. Many compressed full text indexes have been developed to address this problem. In particular, run-length Burrows-Wheeler transform (RLBWT) based compressed full text indexes have seen wide development and adoption. However, the construction of these RLBWT-based compressed full text indexes is still computationally expensive, sometimes prohibitively so, even for current dataset sizes. Therefore, we present algorithms for the construction of RLBWT-based compressed full text indexes and their supporting data structures in compressed space. The algorithms have a space complexity of O(r) words and run in O(n) time for repetitive datasets, where r is the number of runs in the BWT, n is the length of the text, and repetitive datasets implies the average run length is at least log n. We provide the first algorithm to compute LCP-related information for repetitive datasets in optimal time and O(r) space, greatly reducing memory requirements. The key idea behind this algorithm is the utilization of r samples of the inverse suffix array at regular intervals. For example, on the Human Pangenome Reference Consortium Release 2 dataset, this reduces peak memory from 2,135 GiB to 170 GiB (12.6x reduction) compared to the previous best method (pfp-thresholds). AvailabilityThe implementation is available at https://github.com/ucfcbb/TeraTools. Supplementary InformationSupplementary Material is available online at bioRxiv.

bioinformatics↗

bioRxiv2025

Haplotype-based Parallel PBWT for Biobank Scale Data

Durbins positional Burrows-Wheeler transform (PBWT) enables algorithms with the optimal time complexity of O(MN) for reporting all vs all haplotype matches in a population panel with M haplotypes and N variant sites. However, even this efficiency may still be too slow when the number of haplotypes reaches millions. To further reduce the run time, in this paper, a parallel version of the PBWT algorithms is introduced for all versus all haplotype matching, which is called HP-PBWT (haplotype-based parallel PBWT). HP-PBWT parallelly executes the PBWT by splitting a haplotype panel into blocks of haplotypes. HP-PBWT algorithms achieve parallelization for PBWT construction, reporting all versus all L-long matches, and reporting all versus all set-maximal matches while maintaining memory efficiency. HP-PBWT has an [Formula] time complexity in PBWT construction, and an [Formula] time complexity for reporting all versus all L-long matches and reporting all versus all set-maximal matches, where T is the number of threads and c* is the maximum number of matches (of length L or maximum divergence value for L-long matches and set-maximal matches, re-spectively) per haplotype per site. HP-PBWT achieves 4-fold speed-up in UK Biobank genotyping array data with 30 threads in the IO-included benchmarks. When applying HP-PBWT to a dataset of 8 million randomized haplotypes (random binary strings of equal length) in the IO-excluded benchmarks, it can achieve a 22-fold speed-up with 60 cores on the Amazon EC2 server. With further hardware optimization, HP-PBWT is expected to handle billions of haplotypes efficiently.

bioinformatics↗

bioRxiv2025

Dynamic μ-PBWT: Dynamic Run-length Compressed PBWT for Biobank Scale Data

Durbins positional Burrows-Wheeler transform (PBWT) supports efficient haplotype matching and queries given a panel of haplotypes. It has been widely used for statistical phasing, imputation and identity-by-descent (IBD) detection. However, the original PBWT panel doesnt support dynamic updates when haplotypes need to be added or deleted from the panel. Dynamic-PBWT (d-PBWT) solved this problem but it is not memory efficient. While the memory constraint problem of the PBWT has been tackled by Syllable-PBWT and {micro}-PBWT, these are static data structures that do not allow updates. Additionally, Syllable-PBWT only supports long-match query and {micro}-PBWT only supports set-maximal match query, limiting their functionality in the compressed form. In this paper, we present Dynamic {micro}-PBWT (which can also be seen as compressed d-PBWT) that is memory efficient and supports dynamic updates. We run-length compress PBWT to achieve better compression rate and store the runs in the self-balancing trees to enable dynamic updates. We show that the number of updates per insertion or deletion in the tree at each site is constant regardless of the number of haplotypes in the panel and the updates can be made without decompressing the index. In addition, we use orders of magnitude less memory than d-PBWT. We also provide a long match query algorithm that can easily be extended back to the original {micro}-PBWT. Overall, the flexibility and space-efficiency of Dynamic {micro}-PBWT makes it a potential index data structure for biobank scale genetic data analyses. The source code for Dynamic {micro}-PBWT is available at https://github.com/ucfcbb/Dynamic-mu-PBWT.

bioinformatics↗

bioRxiv2025

Haplotype Matching with GBWT for Pangenome Graphs

Traditionally, variations from a linear reference genome were used to represent large sets of haplotypes compactly. In the linear reference genome based paradigm, the positional Burrows-Wheeler transform (PBWT) has traditionally been used to perform efficient haplotype matching. Pangenome graphs have recently been proposed as an alternative to linear reference genomes for representing the full spectrum of variations in the human genome. However, haplotype matches in pangenome graph based haplotype sets are not trivially generalizable from haplotype matches in the linear reference genome based haplotype sets. Work has been done to represent large sets of haplotypes as paths through a pangenome graph. The graph Burrows-Wheeler transform (GBWT) is one such work. The GBWT essentially stores the haplotype paths in a run length compressed BWT with compressed local alphabets. Although efficient in practice count and locate queries on the GBWT were provided by the original authors, the efficient haplotype matching capabilities of the PBWT have never been shown on the GBWT. In this paper, we formally define the notion of haplotype matches in pangenome graph-based haplotype sets by generalizing from haplotype matches in linear reference genome-based haplotype sets. We also describe the relationship between set maximal matches, long matches, locally maximal matches, and text maximal matches on the GBWT, PBWT, and the BWT. We provide algorithms for outputting some of these matches by applying the data structures of the r-index (introduced by Gagie et al.) to the GBWT. We show that these structures enable set maximal match and long match queries on the GBWT in almost linear time and in space close to linear in the number of runs in the GBWT. We also provide multiple versions of the query algorithms for different combinations of the available data structures. The long match query algorithms presented here even run on the BWT in the same time complexity as the GBWT due to their similarity.

bioinformatics↗

bioRxiv2023

Minimal Positional Substring Cover: A Haplotype Threading Alternative to Li & Stephens Model

The Li & Stephens (LS) hidden Markov model (HMM) models the process of reconstructing a haplotype as a mosaic copy of haplotypes in a reference panel (haplotype threading). For small panels the probabilistic parameterization of LS enables modeling the uncertainties of such mosaics, and has been the foundational model for haplotype phasing and imputation. However, LS becomes inefficient when sample size is large (tens of thousands to millions), because of its linear time complexity (O(MN), where M is the number of haplotypes and N is the number of sites in the panel). Recently the PBWT, an efficient data structure capturing the local haplotype matching among haplotypes, was proposed to offer fast methods for giving some optimal solution (Viterbi) to the LS HMM. But the solution space of the LS for large panels is still elusive. Previously we introduced the Minimal Positional Substring Cover (MPSC) problem as an alternative formulation of LS whose objective is to cover a query haplotype by a minimum number of segments from haplotypes in a reference panel. The MPSC formulation allows the generation of a haplotype threading in time constant to sample size (O(N)). This allows haplotype threading on very large biobank scale panels on which the LS model is infeasible. Here we present new results on the solution space of the MPSC by first identifying a property that any MPSC will have a set of required regions, and then proposing a MPSC graph. In addition, we derived a number of optimal algorithms for MPSC, including solution enumerations, the Length Maximal MPSC, and h-MPSC solutions. In doing so, our algorithms reveal the solution space of LS for large panels. Even though we only solved an extreme case of LS where the emission probability is 0, our algorithms can be made more robust by PBWT smoothing. We show that our method is informative in terms of revealing the characteristics of biobank-scale data sets and can improve genotype imputation.

bioinformatics↗

bioRxiv2020

d-PBWT: dynamic positional Burrows-Wheeler transform

Durbins PBWT, a scalable data structure for haplotype matching, has been successfully applied to identical by descent (IBD) segment identification and genotype imputation. Once the PBWT of a haplotype panel is constructed, it supports efficient retrieval of all shared long segments among all individuals (long matches) and efficient query between an external haplotype and the panel. However, the standard PBWT is an array-based static data structure and does not support dynamic updates of the panel. Here, we generalize the static PBWT to a dynamic data structure, d-PBWT, where the reverse prefix sorting at each position is represented by linked lists. We developed efficient algorithms for insertion and deletion of individual haplotypes. In addition, we verified that d-PBWT can support all algorithms of PBWT. In doing so, we systematically investigated variations of set maximal match and long match query algorithms: while they all have average case time complexity independent of database size, they have different worst case complexities, linear time complexity with the size of the genome, and dependency on additional data structures.

bioinformatics↗