AlfaPang Builds Pangenome Graphs Without Sequence Alignment

Published in Algorithms for Molecular Biology, the study presents a method that significantly reduces the computational resources required to model the genetic diversity of large genome collections. By moving away from alignment-based approaches, the new tool addresses a critical bottleneck in modern genomics, where the sheer volume of data from population sequencing projects often exceeds the capacity of existing software.

Pangenome graphs serve as comprehensive models for representing populations of genomes, capturing both shared and unique genetic variations. These structures are essential for analyzing sequence evolution and reducing reference bias, a common issue where genomic analyses are skewed by the choice of a single reference genome. The success of these approaches depends heavily on the efficiency of the construction methods, particularly when applied to thousands of high-quality assemblies. Previous tools, such as the VG toolkit and Minigraph-Cactus, have relied on aligning genomes to a reference or to each other, processes that are computationally intensive and can introduce biases based on the order of input sequences or the choice of reference.

AlfaPang utilizes an alignment-free approach based on a mathematical framework involving k-completeness and k-faithfulness properties. The algorithm builds a variation graph directly from input sequences, ensuring that the resulting structure is unique up to isomorphism for a given set of sequences and a chosen k-mer size. This method avoids the arbitrary choices inherent in alignment-based tools, such as the selection of a reference genome or the order in which genomes are added to the graph. The core of the algorithm involves constructing a generic representation of the sequences and then applying a quotient construction to merge nodes that represent common k-mers, thereby creating a compact and accurate graph structure.

The study evaluated the performance of AlfaPang on two series of genome collections: Escherichia coli and Saccharomyces cerevisiae. The E. coli series included datasets ranging from 50 to 3,412 haplotypes, with total lengths extending up to 17.3 gigabases. The S. cerevisiae series comprised 16 to 118 haplotypes, with total lengths up to 1.44 gigabases. To guide the selection of the k-mer size, the researchers analyzed the fraction of rare k-mers in intermediate-sized datasets, opting for a k value that yielded 5% rare k-mers. This choice was intended to balance the detection of sequence similarity with the prevention of merging non-homologous fragments, a trade-off that is crucial for the accuracy of the resulting pangenome graph.

In terms of computational efficiency, AlfaPang demonstrated substantial advantages over existing state-of-the-art tools. When compared to the wfmash and seqwish pipeline, which forms the first two steps of the pggb workflow, AlfaPang was more than 20 times faster and consumed five times less memory on a dataset of 100 E. coli sequences. On a larger dataset of 200 E. coli sequences, the speed advantage increased to more than 30 times, with memory usage reduced by a factor of 13. Notably, these results were achieved using only a single thread for AlfaPang, whereas the competing tools were tested on 20 CPU threads. The algorithm’s runtime and memory usage scale almost linearly with the number of genomes, a property that is vital for handling the terabytes of data expected from future population sequencing projects.

The researchers also developed a modified pipeline, referred to as AlfaPang+, which integrates AlfaPang with the graph refinement tools smoothxg and gfaffix. This pipeline was compared against the full pggb pipeline and Minigraph-Cactus. For the E. coli datasets, AlfaPang+ proved to be the most efficient tool, showing almost linear scalability with respect to data size. On a dataset of 400 E. coli sequences, AlfaPang+ was more than three times as fast as pggb with sparsification enabled and four times faster than Minigraph-Cactus, while using four to five times less memory. The efficiency gains are particularly significant for large datasets, where the memory constraints of alignment-based tools often lead to process crashes or the need for complex sparsification techniques.

Despite the computational advantages, the structural properties of the graphs produced by AlfaPang+ are similar to those generated by pggb. Minigraph-Cactus, however, produced graphs with a noticeably larger number of nodes and edges, ranging from 10% to 77% more nodes than AlfaPang+ on E. coli data. The total length of node labels, which indicates the compression of input sequences, was lower for AlfaPang+ than for pggb, which in turn was lower than for Minigraph-Cactus. Across all datasets, AlfaPang+ showed a higher rate of compression than pggb, which in turn had a higher rate of compression than Minigraph-Cactus.

The study also examined the similarity between the sequence alignments induced by the graphs constructed with different tools. Using the Jaccard index to measure the overlap of aligned pairs, the researchers found that AlfaPang+ identified a larger number of aligned pairs than pggb and Minigraph-Cactus. For E. coli datasets, AlfaPang+ found 88% to 99% of the pairs identified by both pggb and Minigraph-Cactus. The authors noted that identifying a larger number of aligned residues reflects AlfaPang's high sensitivity to sequence similarity, although the decision to align given fragments is somewhat arbitrary. The differences in the sets of aligned pairs are primarily due to the varying sensitivity of the tools to sequence similarity, rather than fundamental differences in the underlying genomic data.

To assess the biological relevance of these differences, the researchers analyzed the annotation of aligned pairs in the graphs. They sampled one million pairs from each graph and classified them based on GenBank annotations, focusing on gene, pseudogene, and intergenic regions. For S. cerevisiae datasets, approximately 70% to 71% of AlfaPang+ pairs were located in genes, compared to 67% to 69% for pggb and 72% for Minigraph-Cactus. In E. coli datasets, the proportion of gene-gene pairs was similar across all tools for smaller datasets, but for the 400-sequence dataset, AlfaPang+ showed a significantly higher proportion of gene-intergenic pairs at 3.7%, compared to 1.5% for pggb and 1% for Minigraph-Cactus.

One limitation of the AlfaPang approach is the close relationship between the resulting variation graphs and de Bruijn graphs. This similarity can lead to excessive entanglement in areas representing low-complexity sequence regions, a drawback common to de Bruijn graph-based methods. However, the refinement step in the AlfaPang+ pipeline, performed by the smoothxg tool, effectively removes this entanglement. Due to the high efficiency of AlfaPang, this refinement step dominates the computation time of the entire AlfaPang+ pipeline, accounting for approximately 95% of runtime across all datasets. Future work may focus on incorporating the refinement procedure directly into the graph building process to further reduce computation time.

The development of AlfaPang represents a significant step forward in the scalability of pangenome graph construction. As population sequencing projects aim to assemble the genomes of thousands of individuals, the need for efficient and memory-saving tools becomes paramount. The alignment-free nature of AlfaPang allows it to process much larger sets of genomes than current state-of-the-art tools, potentially enabling new insights into human genetic diversity and evolution. The code for AlfaPang is freely available, allowing the research community to test and apply the algorithm to their own datasets.

Subject of Research: Development of an alignment-free algorithm for efficient pangenome graph construction

Article Title: AlfaPang: alignment free algorithm for pangenome graph construction

Article References: Cicherski, A., Lisiecka, A., & Dojer, N. (2025). AlfaPang: alignment free algorithm for pangenome graph construction. Algorithms for Molecular Biology, 20(1), Article 7. https://doi.org/10.1186/s13015-025-00277-7

Image Credits: AI Generated

DOI: 10.1186/s13015-025-00277-7

Keywords: pangenome, graph construction, bioinformatics, alignment-free, genomics, AlfaPang, computational efficiency, sequence similarity, alignment, free, algorithm, graph