Llabrés Mercè, Riera Gabriel, Rosselló Francesc, Valiente Gabriel
Department of Mathematics and Computer Science, University of the Balearic Islands, Palma de Mallorca, E-07122, Spain.
Balearic Islands Health Research Institute, Palma de Mallorca, E-07010, Spain.
BMC Bioinformatics. 2020 Nov 18;21(Suppl 6):434. doi: 10.1186/s12859-020-03733-w.
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.
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.
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.
蛋白质-蛋白质相互作用网络的比对最近被表述为一个整数二次规划问题，以及一种可由整数线性规划软件工具求解的线性化形式。然而，由此产生的整数线性规划有大量的变量和约束条件，使其不具有实际用途。
我们提出了一种蛋白质-蛋白质相互作用网络比对问题的紧凑整数线性规划重新表述，它可以使用最先进的数学建模和整数线性规划软件工具来求解，同时实证结果表明，小型生物网络，如病毒-宿主蛋白质-蛋白质相互作用网络，能够在个人计算机上以合理的时间量进行比对，并且所得到的比对在结构上是连贯的且具有生物学意义。
使用当前数学建模和整数线性规划软件工具对整数线性规划重新表述的实现，提供了病毒-宿主蛋白质-蛋白质相互作用网络具有生物学意义的比对。
