Llabres, MerceRiera, GabrielRossello, FrancescValiente, Gabriel2024-09-132024-09-132020-11-18Llabres M, Riera G, Rossello F, Valiente G. Alignment of biological networks by integer linear programming: virus-host protein-protein interaction networks. BMC Bioinformatics. 2020 Nov 18;21 Suppl 6:434.1471-2105https://hdl.handle.net/20.500.13003/19432https://hdl.handle.net/20.500.12105/2286715th International Symposium on Bioinformatics Research and Applications (ISBRA) - Bioinformatics, JUN 03-06, 2019. Barcelona, SPAINBackground: The alignment of protein-protein interaction networks was recently formulated as an integer quadratic programming problem, along with a linearization that can be solved by integer linear programming software tools. However, the resulting integer linear program has a huge number of variables and constraints, rendering it of no practical use. Results: We present a compact integer linear programming reformulation of the protein-protein interaction network alignment problem, which can be solved using state-of-the-art mathematical modeling and integer linear programming software tools, along with empirical results showing that small biological networks, such as virus-host protein-protein interaction networks, can be aligned in a reasonable amount of time on a personal computer and the resulting alignments are structurally coherent and biologically meaningful. Conclusions: The implementation of the integer linear programming reformulation using current mathematical modeling and integer linear programming software tools provided biologically meaningful alignments of virus-host protein-protein interaction networks.enghttp://creativecommons.org/licenses/by/4.0/Systems biologyVirus-host protein-protein interactionInteger linear programmingNetwork alignmentGraph matchingSoftwareProtein Interaction MapsProgramming, LinearAlgorithmsModels, Theoreticalresearch articleAttribution 4.0 International3320335221S643410.1186/s12859-020-03733-wBMC Bioinformaticsopen accessModelos TeóricosAlgoritmosProgramas InformáticosMapas de Interacción de ProteínasProgramación Lineal2-s2.0-85096119380594994500011L633455102