Quantifying the Rearrangement Complexity of Pangenomes

The study of evolution within a species and the study of evolution between species are closely connected, as they share fundamental biological mechanisms. However, their research has been hindered by differences in time scales and data types. Both fields have unique specializations, with comparative genomics focusing on whole-genome comparisons and pangenomics concentrating on multiple genome variants.

The emergence of graphical pangenomics has highlighted similarities between data structures used in both fields, yet they remain separate disciplines. Despite extensive theoretical work on rearrangement models in comparative genomics, adapting these models to pangenomic data faces challenges due to the limitations of rearrangement problem formulations.

Classical problems, such as parsimony, are impractical for large pangenomes, and all-vs-all comparisons using rearrangement distances are computationally expensive. Additionally, assumptions like the underlying tree in rearrangement problems do not apply to many pangenomes. To address these limitations while maintaining connections to classical rearrangement problems and pangenome graphs, the authors introduce the Complete Ancestral Reconstruction for Pangenomes (CARP) problem.