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

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 consistency with the original algorithm. These improvements allow the PanDelos methodology to be applied to population-scale comparative genomics, thus enabling more precise characterisation of pangenome structure and dynamics.PanDelos-plus is available at github.com/synbionics/PanDelos-plus.Author summary: The identification of homologous gene families across multiple genomes requires computationally demanding all-against-all comparisons. Recent solutions based on k-mer profiles have shown that competitive accuracy can be achieved with state-of-the-art methods, while being faster and easier to use. Among these, PanDelos stands out for its alignment-free and parameter-free approach, combining high speed and ease of use. However, the increasing availability of genomic data requires tools that can scale efficiently to larger datasets. To address this need, we developed PanDelos-plus, a fully parallel, gene-centric redesign of PanDelos. This new version of the algorithm parallelizes the most computationally intensive phases through data decomposition and a thread pool strategy, while employing lightweight data structures to reduce memory usage. Benchmarks show that PanDelos-plus outperforms the original version in terms of speed and memory usage. These improvements allow substantially larger bacterial genome collections to be analyzed on standard multicore workstations, lowering computational barriers and facilitating scalable alignment-free gene-focused prokaryotic pangenome reconstruction.