Optimal Reconstruction of Graph Evolution History Under Preferential Attachment Model.

Area of Science:

• * Computational Biology
• * Network Science
• * Bioinformatics

Background:

• * Understanding biological network evolution is crucial for deciphering biomolecular functions.
• * Protein-protein interaction (PPI) networks evolve dynamically, often modeled by graph growth principles like Preferential Attachment (PA).
• * Existing PA-based ancestral graph reconstruction methods frequently use greedy algorithms, yielding suboptimal results.

Purpose of the Study:

• * To introduce ILP-PA, a novel Integer Linear Programming (ILP) approach for reconstructing historical PPI graphs.
• * To maximize likelihood within the Preferential Attachment model for improved ancestral graph reconstruction.
• * To enable analysis of near-optimal and multiple optimal solutions for diverse applications.

Main Methods:

• * Developed an Integer Linear Programming (ILP) formulation for ancestral PPI graph reconstruction under the PA model.
• * Utilized heuristics from general-purpose ILP solvers to enhance the reconstruction process.
• * Evaluated the ILP-PA approach on synthetic datasets and three real-world PPI networks (Commander complex, bZIP transcription factor family, herpesvirus).

Main Results:

• * ILP-PA solutions achieved higher likelihoods compared to existing techniques.
• * Demonstrated superior robustness against model mismatches and data noise.
• * Reconstructed ancestral graphs showed closer alignment with established biological findings across real datasets.

Conclusions:

• * ILP-PA offers a more accurate and robust method for reconstructing ancestral PPI networks within the PA model.
• * The approach provides valuable insights into the evolutionary dynamics of biological networks.
• * ILP-PA's ability to find multiple optimal solutions enhances its utility in biological research.