Alignment of biological networks by integer linear programming: virus-host protein-protein interaction networks.
Graph matching
Integer linear programming
Network alignment
Systems biology
Virus-host protein-protein interaction
Journal
BMC bioinformatics
ISSN: 1471-2105
Titre abrégé: BMC Bioinformatics
Pays: England
ID NLM: 100965194
Informations de publication
Date de publication:
18 Nov 2020
18 Nov 2020
Historique:
received:
10
08
2020
accepted:
03
09
2020
entrez:
18
11
2020
pubmed:
19
11
2020
medline:
5
2
2021
Statut:
epublish
Résumé
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.
Sections du résumé
BACKGROUND
BACKGROUND
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
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
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.
Identifiants
pubmed: 33203352
doi: 10.1186/s12859-020-03733-w
pii: 10.1186/s12859-020-03733-w
pmc: PMC7671827
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
434Références
Bioinformatics. 2007 Jul 1;23(13):1631-9
pubmed: 17468121
Nucleic Acids Res. 2017 Jan 4;45(D1):D491-D498
pubmed: 27789703
BMC Microbiol. 2015 Jul 28;15:146
pubmed: 26215368
Bacteriol Rev. 1971 Sep;35(3):235-41
pubmed: 4329869
Bioinformatics. 2012 May 1;28(9):1239-45
pubmed: 22419782
Bioinformatics. 2015 Jul 1;31(13):2182-9
pubmed: 25725498
Nucleic Acids Res. 2011 Jan;39(Database issue):D576-82
pubmed: 20947564
Sci Rep. 2017 Apr 19;7(1):953
pubmed: 28424527
Genome Biol. 2017 Oct 3;18(1):186
pubmed: 28974235
Nucleic Acids Res. 2004 Jul 1;32(Web Server issue):W83-8
pubmed: 15215356
Bioinformatics. 2014 Aug 15;30(16):2351-9
pubmed: 24794929
Viruses. 2018 Sep 23;10(10):
pubmed: 30249048
Bioinformatics. 2014 Sep 1;30(17):i438-44
pubmed: 25161231
Nucleic Acids Res. 2017 Jan 4;45(D1):D457-D465
pubmed: 27799466
Bioinformatics. 2013 Apr 1;29(7):917-24
pubmed: 23413436