title: Mapping proteins in the presence of paralogs using units of coevolution.
abstract: BACKGROUND
  We study the problem of mapping proteins between two protein families in the presence of paralogs. This problem occurs as a difficult subproblem in coevolution-based computational approaches for protein-protein interaction prediction.
  
  
  RESULTS
  Similar to prior approaches, our method is based on the idea that coevolution implies equal rates of sequence evolution among the interacting proteins, and we provide a first attempt to quantify this notion in a formal statistical manner. We call the units that are central to this quantification scheme the units of coevolution. A unit consists of two mapped protein pairs and its score quantifies the coevolution of the pairs. This quantification allows us to provide a maximum likelihood formulation of the paralog mapping problem and to cast it into a binary quadratic programming formulation.
  
  
  CONCLUSIONS
  CUPID, our software tool based on a Lagrangian relaxation of this formulation, makes it, for the first time, possible to compute state-of-the-art quality pairings in a few minutes of runtime. In summary, we suggest a novel alternative to the earlier available approaches, which is statistically sound and computationally feasible.
authors.forename: Mohammed
authors.initials: M
authors.lastname: El-Kebir
authors.forename: Tobias
authors.initials: T
authors.lastname: Marschall
authors.forename: Inken
authors.initials: I
authors.lastname: Wohlers
authors.forename: Murray
authors.initials: M
authors.lastname: Patterson
authors.forename: Jaap
authors.initials: J
authors.lastname: Heringa
authors.forename: Alexander
authors.initials: A
authors.lastname: Schönhuth
authors.forename: Gunnar W
authors.initials: GW
authors.lastname: Klau
mesh_terms: D000595:Amino Acid Sequence; D008969:Molecular Sequence Data; D011506:Proteins / Q000032:analysis* / Q000737:chemistry; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein; D012984:Software
chemical_list: D011506:Proteins