title: Predicting protein interactions via parsimonious network history inference.
abstract: BACKGROUND
  Reconstruction of the network-level evolutionary history of protein-protein 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.
  
  
  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.
  
  
  BACKGROUND
  The algorithm is implemented in C++, is open source and is available at http://www.cs.cmu.edu/ckingsf/software/parana2.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Lane Center for Computational Biology, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA. robp@cs.cmu.edu
authors.forename: Rob
authors.initials: R
authors.lastname: Patro
authors.forename: Carl
authors.initials: C
authors.lastname: Kingsford
mesh_terms: D000465:Algorithms; D050976:Basic-Leucine Zipper Transcription Factors / Q000378:metabolism; D005075:Biological Evolution; D006564:Herpesviridae / Q000378:metabolism; D010802:Phylogeny; D011336:Probability; D025941:Protein Interaction Mapping / Q000379:methods*; D014764:Viral Proteins / Q000378:metabolism
chemical_list: D050976:Basic-Leucine Zipper Transcription Factors; D014764:Viral Proteins