{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:20:07Z","timestamp":1762323607561},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1201,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Reconstruction of the network-level evolutionary history of protein\u2013protein interactions provides a principled way to relate interactions in several present-day networks. Here, we present a general framework for inferring such histories and demonstrate how it can be used to determine what interactions existed in the ancestral networks, which present-day interactions we might expect to exist based on evolutionary evidence and what information extant networks contain about the order of ancestral protein duplications.<\/jats:p>\n               <jats:p>Results: Our framework characterizes the space of likely parsimonious network histories. It results in a structure that can be used to find probabilities for a number of events associated with the histories. The framework is based on a directed hypergraph formulation of dynamic programming that we extend to enumerate many optimal and near-optimal solutions. The algorithm is applied to reconstructing ancestral interactions among bZIP transcription factors, imputing missing present-day interactions among the bZIPs and among proteins from five herpes viruses, and determining relative protein duplication order in the bZIP family. Our approach more accurately reconstructs ancestral interactions than existing approaches. In cross-validation tests, we find that our approach ranks the majority of the left-out present-day interactions among the top 2 and 17% of possible edges for the bZIP and herpes networks, respectively, making it a competitive approach for edge imputation. It also estimates relative bZIP protein duplication orders, using only interaction data and phylogenetic tree topology, which are significantly correlated with sequence-based estimates.<\/jats:p>\n               <jats:p>Availability: The algorithm is implemented in C++, is open source and is available at http:\/\/www.cs.cmu.edu\/ckingsf\/software\/parana2.<\/jats:p>\n               <jats:p>Contact: \u00a0robp@cs.cmu.edu or carlk@cs.cmu.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt224","type":"journal-article","created":{"date-parts":[[2013,6,27]],"date-time":"2013-06-27T05:33:26Z","timestamp":1372311206000},"page":"i237-i246","source":"Crossref","is-referenced-by-count":23,"title":["Predicting protein interactions via parsimonious network history inference"],"prefix":"10.1093","volume":"29","author":[{"given":"Rob","family":"Patro","sequence":"first","affiliation":[]},{"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2013,6,19]]},"reference":[{"key":"2023062614312213900_btt224-B1","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":"2023062614312213900_btt224-B2","doi-asserted-by":"crossref","first-page":"14482","DOI":"10.1073\/pnas.0806162105","article-title":"Large-scale reconstruction and phylogenetic analysis of metabolic environments","volume":"105","author":"Borenstein","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023062614312213900_btt224-B3","doi-asserted-by":"crossref","first-page":"3209","DOI":"10.1073\/pnas.0712329105","article-title":"Centroid estimation in discrete high-dimensional spaces with applications in biology","volume":"105","author":"Carvalho","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023062614312213900_btt224-B4","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1089\/cmb.2006.13.320","article-title":"A hybrid micro-macroevolutionary approach to gene tree reconstruction","volume":"13","author":"Durand","year":"2006","journal-title":"J. Comp. Biol."},{"key":"2023062614312213900_btt224-B5","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":"2023062614312213900_btt224-B6","volume-title":"The Principle of Least Action in Quantum Mechanics","author":"Feynman","year":"1942"},{"key":"2023062614312213900_btt224-B7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0303-2647(93)90058-K","article-title":"Computation of biopolymers: a general approach to different problems","volume":"30","author":"Finkelstein","year":"1993","journal-title":"Biosystems"},{"key":"2023062614312213900_btt224-B8","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1101\/gr.5235706","article-title":"Graemlin: general and robust alignment of multiple large interaction networks","volume":"16","author":"Flannick","year":"2006","journal-title":"Genome Res."},{"key":"2023062614312213900_btt224-B9","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1089\/cmb.2009.0099","article-title":"Automatic parameter learning for multiple local network alignment","volume":"16","author":"Flannick","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023062614312213900_btt224-B10","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":"2023062614312213900_btt224-B11","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":"2023062614312213900_btt224-B12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","article-title":"Directed hypergraphs and applications","volume":"42","author":"Gallo","year":"1993","journal-title":"Discrete Appl. Math."},{"key":"2023062614312213900_btt224-B13","author":"Gesmundo","year":"2010"},{"key":"2023062614312213900_btt224-B14","first-page":"190","article-title":"Reverse engineering the evolution of protein interaction networks","author":"Gibson","year":"2009","journal-title":"Pac. Symp. Biocomput."},{"key":"2023062614312213900_btt224-B15","article-title":"Encyclopaedia of mathematics: an updated and annotated translation of the Soviet \u2018Mathematical encyclopaedia\u2019","volume-title":"Encyclopaedia of Mathematics","author":"Hazewinkel","year":"2000"},{"key":"2023062614312213900_btt224-B16","author":"Huang","year":"2005"},{"key":"2023062614312213900_btt224-B17","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1186\/1471-2105-11-24","article-title":"ETE: a python environment for tree exploration","volume":"11","author":"Huerta-Cepas","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023062614312213900_btt224-B18","author":"Klein","year":"2001"},{"key":"2023062614312213900_btt224-B19","doi-asserted-by":"crossref","first-page":"R171","DOI":"10.1186\/gb-2007-8-8-r171","article-title":"PyCogent: a toolkit for making sense from sequence","volume":"8","author":"Knight","year":"2007","journal-title":"Genome Biol."},{"key":"2023062614312213900_btt224-B20","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":"2023062614312213900_btt224-B21","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1093\/bioinformatics\/bts688","article-title":"A novel link prediction algorithm for reconstructing protein\u2013protein interaction networks by topological similarity","volume":"29","author":"Lei","year":"2013","journal-title":"Bioinformatics"},{"key":"2023062614312213900_btt224-B22","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-642-30191-9_16","article-title":"Reconstruction of network evolutionary history from extant network topology and duplication history","volume-title":"Proceedings of the 8th International Conference on Bioinformatics Research and Applications","author":"Li","year":"2012"},{"key":"2023062614312213900_btt224-B23","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1128\/JVI.79.2.725-731.2005","article-title":"Integrating reptilian herpesviruses into the family herpesviridae","volume":"79","author":"McGeoch","year":"2005","journal-title":"J. Virol."},{"key":"2023062614312213900_btt224-B24","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.virusres.2006.01.002","article-title":"Topics in herpesvirus genomics and evolution","volume":"117","author":"McGeoch","year":"2006","journal-title":"Virus Res."},{"key":"2023062614312213900_btt224-B25","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":"2023062614312213900_btt224-B26","doi-asserted-by":"crossref","first-page":"1528","DOI":"10.1093\/bioinformatics\/btp262","article-title":"A stochastic model for the evolution of metabolic networks with neighbor dependence","volume":"25","author":"Mithani","year":"2009","journal-title":"Bioinformatics"},{"key":"2023062614312213900_btt224-B27","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":"2023062614312213900_btt224-B28","doi-asserted-by":"crossref","first-page":"1477","DOI":"10.1016\/j.cor.2003.11.014","article-title":"Finding the k shortest hyperpaths","volume":"32","author":"Nielsen","year":"2005","journal-title":"Comput. Oper. Res."},{"key":"2023062614312213900_btt224-B29","first-page":"25","article-title":"Parsimonious reconstruction of network evolution","volume":"7","author":"Patro","year":"2012","journal-title":"Alg. Mol. Biol."},{"key":"2023062614312213900_btt224-B30","doi-asserted-by":"crossref","first-page":"R51","DOI":"10.1186\/gb-2007-8-4-r51","article-title":"Evolution of protein complexes by duplication of homomeric interactions","volume":"8","author":"Pereira-Leal","year":"2007","journal-title":"Genome Biol."},{"key":"2023062614312213900_btt224-B31","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":"2023062614312213900_btt224-B32","first-page":"250","article-title":"A combinatorial framework for designing (pseudoknotted) RNA algorithms","volume-title":"WABI","author":"Ponty","year":"2011"},{"key":"2023062614312213900_btt224-B33","author":"Singh","year":"2007"},{"key":"2023062614312213900_btt224-B34","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1016\/j.tree.2007.04.004","article-title":"Evolution at the system level: the natural history of protein interaction networks","volume":"22","author":"Stumpf","year":"2007","journal-title":"Trends Ecol. Evol."},{"key":"2023062614312213900_btt224-B35","doi-asserted-by":"crossref","first-page":"D71","DOI":"10.1093\/nar\/gkr981","article-title":"Reorganizing the protein space at the universal protein resource (UniProt)","volume":"40","author":"The UniProt Consortium","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023062614312213900_btt224-B36","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1021\/ci600426e","article-title":"Evaluating virtual screening methods: good and bad metrics for the \u2018early recognition\u2019 problem","volume":"47","author":"Truchon","year":"2007","journal-title":"J. Chem. Inf. Model."},{"key":"2023062614312213900_btt224-B37","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1089\/cmb.2008.0092","article-title":"Reconciliation with non-binary species trees","volume":"15","author":"Vernot","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023062614312213900_btt224-B38","first-page":"555","article-title":"Paml: a program package for phylogenetic analysis by maximum likelihood","volume":"13","author":"Yang","year":"1997","journal-title":"Comput. Appl. Biosci."},{"key":"2023062614312213900_btt224-B39","author":"Zhang","year":"2008"},{"key":"2023062614312213900_btt224-B40","first-page":"1","article-title":"Refining transcriptional regulatory networks using network evolutionary models and gene histories","volume":"5","author":"Zhang","year":"2010","journal-title":"Alg. Mol. Biol."},{"key":"2023062614312213900_btt224-B41","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-3-642-33122-0_5","article-title":"Reconstructing the evolution of molecular interaction networks under the DMC and link dynamics models","volume-title":"Algorithms in Bioinformatics","author":"Zhu","year":"2012"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i237\/50703656\/bioinformatics_29_13_i237.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i237\/50703656\/bioinformatics_29_13_i237.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T15:31:53Z","timestamp":1687793513000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/13\/i237\/193361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,19]]},"references-count":41,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt224","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2013,7]]},"published":{"date-parts":[[2013,6,19]]}}}