Alignment of biological networks by integer linear programming: virus-host protein-protein interaction networks.

Area of Science:

• Computational Biology
• Bioinformatics
• Network Science

Background:

• Protein-protein interaction (PPI) network alignment is crucial for understanding biological systems.
• Previous formulations as integer quadratic programming led to computationally intractable integer linear programs.
• Existing methods struggled with scalability and practical application due to numerous variables and constraints.

Purpose of the Study:

• To develop a computationally efficient and practical integer linear programming (ILP) reformulation for PPI network alignment.
• To enable the alignment of complex biological networks, including virus-host interactions.
• To provide a method that generates biologically meaningful and structurally coherent network alignments.

Main Methods:

• Developed a compact integer linear programming (ILP) reformulation for the PPI network alignment problem.
• Utilized state-of-the-art mathematical modeling and ILP software tools for solving the reformulated problem.
• Applied the method to small biological networks, specifically virus-host PPI networks.

Main Results:

• The compact ILP reformulation successfully aligned virus-host protein-protein interaction networks.
• Alignments were achieved in a reasonable time on a personal computer, demonstrating computational efficiency.
• The resulting network alignments were found to be structurally coherent and biologically meaningful.

Conclusions:

• The implemented ILP reformulation provides a practical and effective solution for PPI network alignment.
• This method successfully generated biologically meaningful alignments for virus-host PPI networks.
• The approach leverages current mathematical modeling and ILP software for robust biological network analysis.