Mapping proteins in the presence of paralogs using units of coevolution

BMC Bioinformatics

Proceedings

Jaap Heringa¹  Tobias Marschall²  Murray Patterson²  Alexander Schönhuth²  Gunnar W Klau²  Mohammed El-Kebir³  Inken Wohlers⁴ 

[1] Centre for Integrative Bioinformatics VU, VU University Amsterdam, The Netherlands;Centrum Wiskunde & Informatica (CWI), Life Sciences Group, Amsterdam, The Netherlands;Centrum Wiskunde & Informatica (CWI), Life Sciences Group, Amsterdam, The Netherlands;Centre for Integrative Bioinformatics VU, VU University Amsterdam, The Netherlands;Centrum Wiskunde & Informatica (CWI), Life Sciences Group, Amsterdam, The Netherlands;University of Duisburg-Essen, Genome Informatics, Essen, Germany;

关键词: Maximum Cardinality;    Optimal Score;    Network Alignment;    Bipartite Match;    Generative Statistical Model;   

DOI  :  10.1186/1471-2105-14-S15-S18

来源: Springer

【 摘 要 】

BackgroundWe 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.ResultsSimilar 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.ConclusionCUPID, 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.

【 授权许可】

CC BY   
© El-Kebir et al.; licensee BioMed Central Ltd. 2013