PanDelos-plus: A parallel algorithm for computing sequence homology in pangenomic analysis

Simone Colli, Emiliano Maresi, Vincenzo Bonnici · 2025

Read PanDelos-plus: A parallel algorithm for computing sequence homology in pangenomic analysis by Simone Colli, Emiliano Maresi, Vincenzo Bonnici (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-2510-23679.txt.

Introduction

Simone Colli and two co-authors present PanDelos-plus, a faster rebuild of a tool that finds matching gene families across many bacterial genomes. Finding families is a core task in pangenome work, but the standard method compares everything against everything, which grows brutal as genome sets swell. PanDelos skipped alignments and tuning knobs, comparing short k-mer profiles instead, and stayed fast and accurate.

The new version is built around genes and runs in parallel. Its heaviest steps are split across a pool of threads: finding each gene's best hit, then the pairs that hit each other back. Leaner data structures cut memory use. On tests, PanDelos-plus ran up to fourteen times faster and used up to ninety-six percent less memory, with accuracy intact. The authors argue that population-scale comparisons now fit on a normal multicore workstation, putting pangenome studies within everyday reach.

Catalog record

CREATORSimone Colli, Emiliano Maresi, Vincenzo Bonnici
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-23679

Browse the full library · About the Tower of Babel

Full text

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

PanDelos-plus: A parallel algorithm for computing sequence homology in pangenomic analysis Simone Colli, Emiliano Maresi, Vincenzo Bonnici Abstract The identification of homologous gene families across multiple genomes is a central task in bacterial pangenomics traditionally requiring computationally demanding all-against-all comparisons. PanDelos addresses this challenge with an alignment-free and parameter-free approach based on k-mer profiles, combining high speed, ease of use, and competitive accuracy with state-of-the-art methods. However, the increasing availability of genomic data requires tools that can scale efficiently to larger datasets. To address this need, we present PanDelos-plus, a fully parallel, gene-centric redesign of PanDelos. The algorithm parallelizes the most computationally intensive phases (Best Hit detection and Bidirectional Best Hit extraction) through data decomposition and a thread pool strategy, while employing lightweight data structures to reduce memory usage. Benchmarks on synthetic datasets show that PanDelos-plus achieves up to 14x faster execution and reduces memory usage by up to 96%, while maintaining accuracy. These improvements enable population-scale comparative genomics to be performed on standard multicore workstations, making large-scale bacterial pangenome analysis accessible for routine use in everyday research. keywords Homology, PanDelos parallel, K-mer dictionary, Pangenome Introduction With the rapid progress of high-throughput sequencing projects, biological data is growing exponentially, creating a need for efficient and scalable algorithms for further analysis. Yeh et al. 2023 This need is particularly evident in pangenomics, a discipline that has emerged to study the entire repertoire of gene families in genomes of a given clade. In order to understand the genetic diversity within a species, an abstract structure called pangenome is used. A pangenome is built by identifying groups of homologous genes. Vernikos et al. 2015 ; Muthamilarasan et al. 2019 ; Kim et al. 2020 The pangenome is a collection of all the genes present in a set of genomes divided into core, accessory and singleton genes. Core genes, shared by all genomes, encode essential cellular functions. Dispensable genes occur in only part of the genomes and often provide adaptive advantages in specific environments. Singleton genes, unique to a single genome, usually arise from horizontal gene transfer or reflect organism-specific adaptations Vernikos et al. 2015 Approaches to pangenome content discovery should take into account that gene mutations, which can occur during gene replication and transitions may introduce sequence alterations. Brittnacher et al. 2011 ; Contreras-Moreira and Vinuesa 2013 ; Benedict et al. 2014 ; Chaudhari et al. 2016 Mutations, along with strong evolutionary selection of core genes even if transmitted with few modifications, make the task of recognizing homologous genes difficult. In fact, the number of variations that affect dispensable genes varies and the similarity between homologous sequences tends to decrease depending on their phylogenetic distance. Bonnici et al. 2018 The importance of pangenome information is revealed in terms of clinical applications. Pangenomic studies have been helpful in the identification of drug targets in vaccines, allowing the targeting of possible vaccine candidates and antibacterials, helping researchers to decipher their virulence mechanisms Serruto et al. 2009 ; Muzzi et al. 2007 , to detect strain-specific virulence factors D’Auria et al. 2010 , to distinguish between lineage and niche-specific bacterial population Zhang and Sievert 2014 and to investigate pathogens in epidemic diseases Holt et al. 2008 . Computationally, retrieval of a pangenome is an NP-hard problem Nguyen et al. 2015 , mainly due to all-against-all comparisons between gene sets. For this reason, the analysis of pangenomes is a complex and time-consuming task. So far, many tools have been developed by combining different techniques, algorithms, and thresholds. A variety of bioinformatic tools have been developed to address the challenge of pangenome reconstruction, each with distinct methodologies for gene clustering, leading to different trade-offs in terms of speed, accuracy, and scalability. Among the state-of-the-art used tools are Roary Page et al. 2015 , Panaroo Tonkin-Hill et al. 2020 , PPanGGOLiN Gautreau et al. 2020 , and PanDelos Bonnici et al. 2018 . Roary is widely recognized for its speed, particularly when dealing with complete high-quality genomes, but its performance can be highly sensitive to assembly errors present in the input genomes. Panaroo is designed to specifically address and correct errors often found in draft genome assemblies, making it suitable for less refined datasets. PPanGGOLiN aims for scalability across a large number of genomes, though it often requires careful tuning of its parameters to achieve optimal results. Finally, PanDelos distinguishes itself by excelling in speed through its alignment-free approach. It is also able to automatically determine the optimal k-mer value using a ’context-aware parameter inference’ method, thus eliminating the need for manual parameter tuning. This makes it particularly effective in scenarios that involve high phylogenetic diversity. Benchmarks have demonstrated that single-core PanDelos has demonstrated significant advantages in this landscape, outperforming other tools. Bonnici et al. 2021 And thanks to its architecture PanDelos is part of new methodologies like PanDelos-frags, that infers missing genetic information and thus manages incomplete genomes. Bonnici et al. 2023 Despite the advancements offered by these tools, many existing solutions are not fully optimized for analyzing very large datasets. They often rely on single-threaded algorithms or employ memory-intensive data structures, or both, making the analysis of large datasets a time-consuming and resource-intensive task. PanDelos, while being a fast and accurate tool, is not scalable due to its memory-intensive data structures, which limits its ability to handle larger datasets efficiently. We introduce PanDelos-plus, a re-engineered, parallelized version of PanDelos designed for high-throughput pangenomic analysis. This work leverages a multi-threading approach and optimized, low-memory data structures to enable the rapid and efficient analysis overcoming the scalability limitations of PanDelos. In this work, we present an evaluation of PanDelos-plus on both real dataset (including Escherichia coli, Salmonella enterica, Mycoplasma and Xanthomonas campestris) and synthetic collections generated with PANPROVA (a benchmarking tool that simulates prokaryotic pangenome evolution starting from a complete ancestral genome) Bonnici and Giugno 2022 . comprising up to 600 genomes. Results show up to a 14x speedup and a memory reduction of up to 96% compared to PanDelos, while preserving accuracy. Basic notions Given a dataset consisting of a list of n genomes \mathbb{G}=\{G_{1},\ G_{2},\ldots,\ G_{n}\} , each genome G_{i} is represented by a list of m genes G_{i}=\{g_{i,1},\ g_{i,2},\ldots,\ g_{i,m}\} . The number of genes in the genome G_{i} is denoted as |G_{i}| . A gene g_{i,j}\in\Gamma^{*} is a string s=a_{1}a_{2}\ldots a_{n} constructed over a nucleotide or amino acid alphabet \Gamma . For a sequence s=a_{1}a_{2}a_{y}\ldots a_{w}\ldots a_{n} , with y<w\leq n , the substring of s starting at position y and ending at position w is denoted by s[y,\ w] . Given a fixed value k it’s possible to identify a k-mer, defined as a string \alpha\in\Gamma^{*} such that |\alpha|=k . Inside a gene g represented by the sequence s of length, defined as the number of characters inside the sequence, denoted as |s| can occurs |s|-k-1 k-mers. For a fixed length k , the k-mer dictionary of a gene g , represents all k-mers contained inside the gene, and is defined as: D_{k}(g)=\{\alpha\in\Gamma^{*}:\exists\rho\text{ such that }g[\rho,\ \rho+k]=\alpha,\ 1\leq\rho\leq|g|\}. (1) where k is the length of the k-mers, \alpha is a string built using the alphabet \Gamma , and g[\rho,\ \rho+k] denotes the substring of g starting at position \rho and ending at position \rho+k

Read the complete text