{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T04:01:14Z","timestamp":1777521674546,"version":"3.51.4"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T00:00:00Z","timestamp":1604275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education Academic Research Fund","doi-asserted-by":"publisher","award":["R-253-000-139-114"],"award-info":[{"award-number":["R-253-000-139-114"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"publisher","award":["GBMF4554"],"award-info":[{"award-number":["GBMF4554"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1256087"],"award-info":[{"award-number":["CCF-1256087"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319998"],"award-info":[{"award-number":["CCF-1319998"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"publisher","award":["DBI-2019771"],"award-info":[{"award-number":["DBI-2019771"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM122935"],"award-info":[{"award-number":["R01GM122935"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>The study of the evolutionary history of biological networks enables deep functional understanding of various bio-molecular processes. Network growth models, such as the Duplication\u2013Mutation with Complementarity (DMC) model, provide a principled approach to characterizing the evolution of protein\u2013protein interactions (PPIs) based on duplication and divergence. Current methods for model-based ancestral network reconstruction primarily use greedy heuristics and yield sub-optimal solutions.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present a new Integer Linear Programming (ILP) solution for maximum likelihood reconstruction of ancestral PPI networks using the DMC model. We prove the correctness of our solution that is designed to find the optimal solution. It can also use efficient heuristics from general-purpose ILP solvers to obtain multiple optimal and near-optimal solutions that may be useful in many applications. Experiments on synthetic data show that our ILP obtains solutions with higher likelihood than those from previous methods, and is robust to noise and model mismatch. We evaluate our algorithm on two real PPI networks, with proteins from the families of bZIP transcription factors and the Commander complex. On both the networks, solutions from our ILP have higher likelihood and are in better agreement with independent biological evidence from other studies.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>A Python implementation is available at https:\/\/bitbucket.org\/cdal\/network-reconstruction.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa931","type":"journal-article","created":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T07:32:18Z","timestamp":1603438338000},"page":"1083-1092","source":"Crossref","is-referenced-by-count":3,"title":["Maximum likelihood reconstruction of ancestral networks by integer linear programming"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6748-6864","authenticated-orcid":false,"given":"Vaibhav","family":"Rajan","sequence":"first","affiliation":[{"name":"Department of Information Systems and Analytics, School of Computing, National University of Singapore , Singapore 117417, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, College of Computing, Georgia Institute of Technology , Atlanta 30308, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[{"name":"Computational Biology Department, School of Computer Science, Carnegie Mellon University , Pittsburgh, PA 15213, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiuwei","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, College of Computing, Georgia Institute of Technology , Atlanta 30308, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,12,10]]},"reference":[{"key":"2023051701215171800_btaa931-B1","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1093\/molbev\/msl211","article-title":"One billion years of bZIP transcription factor evolution: conservation and change in dimerization and DNA-binding site specificity","volume":"24","author":"Amoutzias","year":"2006","journal-title":"Mol. Biol. Evol"},{"key":"2023051701215171800_btaa931-B2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2023051701215171800_btaa931-B3","doi-asserted-by":"crossref","first-page":"10961","DOI":"10.1038\/ncomms10961","article-title":"CCC- and WASH-mediated endosomal sorting of LDLR is required for normal clearance of circulating LDL","volume":"7","author":"Bartuzi","year":"2016","journal-title":"Nat. Commun"},{"key":"2023051701215171800_btaa931-B4","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1089\/cmb.2008.06TT","article-title":"Topological signatures of species interactions in metabolic networks","volume":"16","author":"Borenstein","year":"2009","journal-title":"J. Comput. Biol"},{"key":"2023051701215171800_btaa931-B5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1089\/106652703322539024","article-title":"Duplication models for biological networks","volume":"10","author":"Chung","year":"2003","journal-title":"J. Comput. Biol"},{"key":"2023051701215171800_btaa931-B6","doi-asserted-by":"crossref","first-page":"i149","DOI":"10.1093\/bioinformatics\/btm194","article-title":"Identification of functional modules from conserved ancestral protein\u2013protein interactions","volume":"23","author":"Dutkowski","year":"2007","journal-title":"Bioinformatics"},{"key":"2023051701215171800_btaa931-B7","doi-asserted-by":"crossref","first-page":"R11","DOI":"10.1186\/gb-2004-5-2-r11","article-title":"Predicting specificity in bZIP coiled-coil protein interactions","volume":"5","author":"Fong","year":"2004","journal-title":"Genome Biol"},{"key":"2023051701215171800_btaa931-B8","doi-asserted-by":"crossref","first-page":"e1000570","DOI":"10.1371\/journal.ppat.1000570","article-title":"Evolutionarily conserved herpesviral protein interaction networks","volume":"5","author":"Fossum","year":"2009","journal-title":"PLoS Pathog"},{"key":"2023051701215171800_btaa931-B9","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1089\/cmb.2015.0072","article-title":"Bayesian inference for duplication\u2013mutation with complementarity network models","volume":"22","author":"Jasra","year":"2015","journal-title":"J. Comput. Biol"},{"key":"2023051701215171800_btaa931-B10","doi-asserted-by":"crossref","first-page":"e58134","DOI":"10.1371\/journal.pone.0058134","article-title":"The evolutionary dynamics of protein\u2013protein interaction networks inferred from the reconstruction of ancient networks","volume":"8","author":"Jin","year":"2013","journal-title":"PLoS One"},{"key":"2023051701215171800_btaa931-B11","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Karp","year":"1972"},{"key":"2023051701215171800_btaa931-B12","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1093\/biomet\/33.3.239","article-title":"The treatment of ties in ranking problems","volume":"33","author":"Kendall","year":"1945","journal-title":"Biometrika"},{"key":"2023051701215171800_btaa931-B13","doi-asserted-by":"crossref","first-page":"6976","DOI":"10.1073\/pnas.0712149105","article-title":"The evolution of modularity in bacterial metabolic networks","volume":"105","author":"Kreimer","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051701215171800_btaa931-B14","doi-asserted-by":"crossref","first-page":"D807","DOI":"10.1093\/nar\/gky1053","article-title":"OrthoDB v10: sampling the diversity of animal, plant, fungal, protist, bacterial and viral genomes for evolutionary and functional annotations of orthologs","volume":"47","author":"Kriventseva","year":"2019","journal-title":"Nucleic Acids Res"},{"key":"2023051701215171800_btaa931-B15","first-page":"177","author":"Leskovec","year":"2005"},{"key":"2023051701215171800_btaa931-B16","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1109\/TCBB.2013.14","article-title":"Maximum likelihood inference of the evolutionary history of a PPI network from the duplication history of its proteins","volume":"10","author":"Li","year":"2013","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023051701215171800_btaa931-B17","doi-asserted-by":"crossref","first-page":"e1007396","DOI":"10.1371\/journal.pcbi.1007396","article-title":"Ancestral reconstruction of protein interaction networks","volume":"15","author":"Liebeskind","year":"2019","journal-title":"PLoS Comput. Biol"},{"key":"2023051701215171800_btaa931-B18","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1016\/j.cels.2017.04.006","article-title":"Systems-wide studies uncover commander, a multiprotein complex essential to human development","volume":"4","author":"Mallam","year":"2017","journal-title":"Cell Syst"},{"key":"2023051701215171800_btaa931-B19","doi-asserted-by":"crossref","first-page":"3192","DOI":"10.1073\/pnas.0409515102","article-title":"Inferring network mechanisms: the Drosophila melanogaster protein interaction network","volume":"102","author":"Middendorf","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051701215171800_btaa931-B20","doi-asserted-by":"crossref","DOI":"10.1242\/jcs.217216","article-title":"The unfolded protein response in metazoan development","volume":"132,","author":"Mitra","year":"2019","journal-title":"J. Cell. Sci"},{"key":"2023051701215171800_btaa931-B21","doi-asserted-by":"crossref","first-page":"e1001119","DOI":"10.1371\/journal.pcbi.1001119","article-title":"Network archaeology: uncovering ancient networks from present-day interactions","volume":"7","author":"Navlakha","year":"2011","journal-title":"PLoS Comput. Biol"},{"key":"2023051701215171800_btaa931-B22","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol"},{"key":"2023051701215171800_btaa931-B23","doi-asserted-by":"crossref","first-page":"12451","DOI":"10.1073\/pnas.0604065103","article-title":"Early evolution of animal cell signaling and adhesion genes","volume":"103","author":"Nichols","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051701215171800_btaa931-B24","doi-asserted-by":"crossref","first-page":"i237","DOI":"10.1093\/bioinformatics\/btt224","article-title":"Predicting protein interactions via parsimonious network history inference","volume":"29","author":"Patro","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051701215171800_btaa931-B25","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1186\/1748-7188-7-25","article-title":"Parsimonious reconstruction of network evolution","volume":"7","author":"Patro","year":"2012","journal-title":"Algorithms Mol. Biol"},{"key":"2023051701215171800_btaa931-B26","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1098\/rstb.2005.1807","article-title":"The origins and evolution of functional modules: lessons from protein complexes","volume":"361","author":"Pereira-Leal","year":"2006","journal-title":"Philos. Trans. R. Soc. Lond. B Biol. Sci"},{"key":"2023051701215171800_btaa931-B27","doi-asserted-by":"crossref","first-page":"20449","DOI":"10.1073\/pnas.0706339104","article-title":"Reconstruction of ancestral protein interaction networks for the bZIP transcription factors","volume":"104","author":"Pinney","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051701215171800_btaa931-B28","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1002\/jcb.26151","article-title":"COMMD1: a multifunctional regulatory protein","volume":"119","author":"Riera-Romo","year":"2018","journal-title":"J. Cell. Biochem"},{"key":"2023051701215171800_btaa931-B29","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci"},{"key":"2023051701215171800_btaa931-B30","first-page":"2539","article-title":"Weisfeiler\u2013Lehman Graph Kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res"},{"key":"2023051701215171800_btaa931-B31","first-page":"521","article-title":"A tutorial guide to mixed-integer programming models and solution techniques","author":"Smith","year":"2008","journal-title":"pp."},{"key":"2023051701215171800_btaa931-B32","doi-asserted-by":"crossref","first-page":"3057","DOI":"10.1038\/s41598-019-38912-0","article-title":"Inferring temporal information from a snapshot of a dynamic network","volume":"9","author":"Sreedharan","year":"2019","journal-title":"Sci. Rep"},{"key":"2023051701215171800_btaa931-B33","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1159\/000067642","article-title":"Modeling of protein interaction networks","volume":"1","author":"V\u00e1zquez","year":"2003","journal-title":"Complexus"},{"key":"2023051701215171800_btaa931-B34","doi-asserted-by":"crossref","first-page":"986","DOI":"10.1016\/j.cell.2011.02.016","article-title":"Interactome networks and human disease","volume":"144","author":"Vidal","year":"2011","journal-title":"Cell"},{"key":"2023051701215171800_btaa931-B35","first-page":"1201","article-title":"Graph kernels","volume":"11","author":"Vishwanathan","year":"2010","journal-title":"J. Mach. Learn. Res"},{"key":"2023051701215171800_btaa931-B36","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1093\/oxfordjournals.molbev.a003913","article-title":"The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes","volume":"18","author":"Wagner","year":"2001","journal-title":"Mol. Biol. Evol"},{"key":"2023051701215171800_btaa931-B37","author":"Wolsey"},{"key":"2023051701215171800_btaa931-B38","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1038\/nrm2787","article-title":"Evolution of biomolecular networks \u2013 lessons from metabolic and protein interactions","volume":"10","author":"Yamada","year":"2009","journal-title":"Nat. Rev. Mol. Cell Biol"},{"key":"2023051701215171800_btaa931-B39","first-page":"041056","article-title":"Phase transition in the recoverability of network history","volume":"9","author":"Young","year":"2019","journal-title":"Phys. Rev. X"},{"key":"2023051701215171800_btaa931-B40","doi-asserted-by":"crossref","first-page":"15893","DOI":"10.1109\/ACCESS.2017.2690664","article-title":"An improved archaeology algorithm based on integrated multi-source biological information for yeast protein interaction network","volume":"5","author":"Zhang","year":"2017","journal-title":"IEEE Access"},{"key":"2023051701215171800_btaa931-B41","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1109\/TCBB.2012.62","article-title":"Refining regulatory networks through phylogenetic transfer of information","volume":"9","author":"Zhang","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa931\/34841198\/btaa931.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/8\/1083\/50340554\/btaa931.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/8\/1083\/50340554\/btaa931.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T21:23:06Z","timestamp":1684272186000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/8\/1083\/5949735"}},"subtitle":[],"editor":[{"given":"Ponty","family":"Yann","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,12,10]]},"references-count":41,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,5,23]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa931","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/574814","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,4,15]]},"published":{"date-parts":[[2020,12,10]]}}}