Optimal Reconstruction of Graph Evolution History Under Preferential Attachment Model

Research into the evolution of biological networks enhances our understanding of the functional roles of various biomolecular properties. Graph growth models, such as the Preferential Attachment (PA) model, help characterize the evolutionary dynamics of protein interaction networks by modeling the preferential attachment of duplicated proteins' new interactions to existing ones. This approach generates realistic, scale-free PPI networks in a systematic manner. However, existing methods for reconstructing ancestral graphs based on the PA model have predominantly relied on greedy algorithms, often leading to suboptimal results. In this study, we introduce ILP-PA, a novel approach based on Integer Linear Programming (ILP), designed to reconstruct historical PPI graphs by maximizing likelihood within the Preferential Attachment model. Our ILP formulation also leverages systematic heuristics from general-purpose ILP solvers, allowing the analysis of near-optimal and multiple optimal solutions, which can be valuable for various applications across different fields. We evaluate the effectiveness of our approach on both synthetic data and three real protein-protein interaction graphs, specifically the Commander complex, bZIP transcription factor family, and herpesvirus interaction network. Compared to existing techniques, our ILP-PA solutions achieve higher likelihoods and demonstrate greater robustness to model mismatches and noise in the data. Furthermore, our solutions align more closely with biological findings from various studies across real datasets.