{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T23:18:08Z","timestamp":1722813488809},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"S6","license":[{"start":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:00:00Z","timestamp":1604188800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"vor","delay-in-days":17,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2020,11]]},"abstract":"Abstract<\/jats:title>\nBackground<\/jats:title>\nThe 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.<\/jats:p>\n<\/jats:sec>\nResults<\/jats:title>\nWe 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.<\/jats:p>\n<\/jats:sec>\nConclusions<\/jats:title>\nThe 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.<\/jats:p>\n<\/jats:sec>","DOI":"10.1186\/s12859-020-03733-w","type":"journal-article","created":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T04:14:07Z","timestamp":1605672847000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Alignment of biological networks by integer linear programming: virus-host protein-protein interaction networks"],"prefix":"10.1186","volume":"21","author":[{"given":"Merc\u00e8","family":"Llabr\u00e9s","sequence":"first","affiliation":[]},{"given":"Gabriel","family":"Riera","sequence":"additional","affiliation":[]},{"given":"Francesc","family":"Rossell\u00f3","sequence":"additional","affiliation":[]},{"given":"Gabriel","family":"Valiente","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,18]]},"reference":[{"issue":"9","key":"3733_CR1","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1093\/bioinformatics\/bts119","volume":"28","author":"HTT Phan","year":"2012","unstructured":"Phan HTT, Sternberg MJE. PINALOG: A novel approach to align protein interaction networks\u2014implications for complex detection and function prediction. Bioinformatics. 2012; 28(9):1239\u201345.","journal-title":"Bioinformatics"},{"issue":"7","key":"3733_CR2","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","volume":"29","author":"AE Aladag\u030c","year":"2013","unstructured":"Aladag\u030c AE, Erten C. SPINAL: Scalable protein interaction network alignment. Bioinformatics. 2013; 29(7):917\u201324.","journal-title":"Bioinformatics"},{"issue":"17","key":"3733_CR3","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1093\/bioinformatics\/btu450","volume":"30","author":"S Hashemifar","year":"2014","unstructured":"Hashemifar S, Xu J. HubAlign: An accurate and efficient method for global alignment of protein-protein interaction networks. Bioinformatics. 2014; 30(17):438\u201344.","journal-title":"Bioinformatics"},{"issue":"13","key":"3733_CR4","doi-asserted-by":"publisher","first-page":"2182","DOI":"10.1093\/bioinformatics\/btv130","volume":"31","author":"N Malod-Dognin","year":"2015","unstructured":"Malod-Dognin N, Pr\u017eulj N. L-GRAAL: Lagrangian graphlet-based network aligner. Bioinformatics. 2015; 31(13):2182\u20139.","journal-title":"Bioinformatics"},{"key":"3733_CR5","first-page":"1902","volume":"11490","author":"R Alberich","year":"2019","unstructured":"Alberich R, Alcal\u00e0 A, Llabr\u00e9s M, Rossell\u00f3 F, Valiente G. AligNet: Alignment of protein-protein interaction networks. arXiv e-prints. 2019; 11490:1902\u201307107.","journal-title":"arXiv e-prints"},{"key":"3733_CR6","volume-title":"Proc. 28th IEEE EMBS Ann. Int. Conf","author":"Z Li","year":"2006","unstructured":"Li Z, Wang Y, Zhang S, Zhang X-S, Chen L. Alignment of protein interaction networks by integer quadratic programming. In: Proc. 28th IEEE EMBS Ann. Int. Conf. New York, NY: IEEE: 2006. p. 5527\u201330."},{"issue":"13","key":"3733_CR7","doi-asserted-by":"publisher","first-page":"1631","DOI":"10.1093\/bioinformatics\/btm156","volume":"23","author":"Z Li","year":"2007","unstructured":"Li Z, Zhang S, Wang Y, Zhang X-S, Chen L. Alignment of molecular networks by integer quadratic programming. Bioinformatics. 2007; 23(13):1631\u20139.","journal-title":"Bioinformatics"},{"issue":"10","key":"3733_CR8","doi-asserted-by":"publisher","first-page":"519","DOI":"10.3390\/v10100519","volume":"10","author":"HV Cook","year":"2018","unstructured":"Cook HV, Doncheva NT, Szklarczyk D, Mering CV, Jensen LJ. Viruses.STRING: A virus-host protein-protein interaction database. Viruses. 2018; 10(10):519.","journal-title":"Viruses"},{"key":"3733_CR9","volume-title":"AMPL: a modeling language for mathematical programming","author":"R Fourer","year":"2002","unstructured":"Fourer R, Gay DM, Kernighan BW. AMPL: a modeling language for mathematical programming, 2nd edn. Boston, Massachusetts: Cengage Learning; 2002."},{"issue":"16","key":"3733_CR10","doi-asserted-by":"publisher","first-page":"2351","DOI":"10.1093\/bioinformatics\/btu307","volume":"30","author":"C Clark","year":"2014","unstructured":"Clark C, Kalita J. A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics. 2014; 30(16):2351\u20139.","journal-title":"Bioinformatics"},{"issue":"1","key":"3733_CR11","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1038\/s41598-017-01085-9","volume":"7","author":"N Malod-Dognin","year":"2017","unstructured":"Malod-Dognin N, Ban K, Pr\u017eulj N. Unified alignment of protein-protein interaction networks. Sci Rep. 2017; 7(1):953.","journal-title":"Sci Rep"},{"issue":"1","key":"3733_CR12","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1186\/s13059-017-1319-7","volume":"18","author":"A Zielezinski","year":"2017","unstructured":"Zielezinski A, Vinga S, Almeida J, Karlowski WM. Alignment-free sequence comparison: benefits, applications, and tools. Genome Biol. 2017; 18(1):186.","journal-title":"Genome Biol"},{"issue":"3","key":"3733_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1128\/MMBR.35.3.235-241.1971","volume":"35","author":"D Baltimore","year":"1971","unstructured":"Baltimore D. Expression of animal virus genomes. Bacteriol Rev. 1971; 35(3):235\u201341.","journal-title":"Bacteriol Rev"},{"key":"3733_CR14","first-page":"457","volume":"45","author":"D Paez-Espino","year":"2017","unstructured":"Paez-Espino D, Chen I-MA, Palaniappan K, et al. IMG\/VR: A database of cultured and uncultured DNA viruses and retroviruses. Nucleic Acids Res. 2017; 45:457\u201365.","journal-title":"Nucleic Acids Res"},{"key":"3733_CR15","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1093\/nar\/gkw975","volume":"45","author":"AL Grazziotin","year":"2017","unstructured":"Grazziotin AL, Koonin EV, Kristensen DM. Prokaryotic virus orthologous groups (pVOGs): A resource for comparative genomics and protein family annotation. Nucleic Acids Res. 2017; 45:491\u20138.","journal-title":"Nucleic Acids Res"},{"key":"3733_CR16","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1093\/nar\/gkq901","volume":"39","author":"C Hulo","year":"2011","unstructured":"Hulo C, Castro ED, Masson P, Bougueleret L, Bairoch A, Xenarios I, Mercier PL. ViralZone: A knowledge resource to understand virus diversity. Nucleic Acids Res. 2011; 39:576\u201382.","journal-title":"Nucleic Acids Res"},{"key":"3733_CR17","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1186\/s12866-015-0481-x","volume":"15","author":"RE Foulger","year":"2015","unstructured":"Foulger RE, Osumi-Sutherland D, McIntosh BK, Hulo C, Masson P, Poux S, Mercier PL, Lomax J. Representing virus-host interactions and other multi-organism processes in the Gene Ontology. BMC Microbiol. 2015; 15:146.","journal-title":"BMC Microbiol"},{"key":"3733_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1093\/nar\/gkh411","volume":"32","author":"BP Kelley","year":"2014","unstructured":"Kelley BP, Yuan B, Lewitter F, Sharan R, Stockwell BR, Ideker T. PathBLAST: a tool for alignment of protein interaction networks. Nucleic Acids Res. 2014; 32:83\u201388.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"3733_CR19","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1287\/opre.21.1.156","volume":"21","author":"F Glover","year":"1973","unstructured":"Glover F, Woolsey E. Further reduction of 0-1 polynomial programming problems to 0-1 linear programming problems. Oper Res. 1973; 21(1):156\u201361.","journal-title":"Oper Res"},{"issue":"1","key":"3733_CR20","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/opre.22.1.180","volume":"22","author":"F Glover","year":"1974","unstructured":"Glover F, Woolsey E. Converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper Res. 1974; 22(1):180\u20132.","journal-title":"Oper Res"},{"issue":"3","key":"3733_CR21","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0377-2217(78)90095-4","volume":"2","author":"L Kaufmann","year":"1978","unstructured":"Kaufmann L, Broeckx F. An algorithm for the quadratic assignment problem using Benders\u2019 decomposition. Eur J Oper Res. 1978; 2(3):207\u201311.","journal-title":"Eur J Oper Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03733-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-020-03733-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03733-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T04:17:09Z","timestamp":1605673029000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-020-03733-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":21,"journal-issue":{"issue":"S6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["3733"],"URL":"https:\/\/doi.org\/10.1186\/s12859-020-03733-w","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11]]},"assertion":[{"value":"10 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"434"}}