Orthology and paralogy constraints: satisfiability and consistency

BMC Genomics

Research

Nadia El-Mabrouk¹  Manuel Lafond¹ 

[1] Department of Computer Science and Operational Research, University of Montreal, Chemin de la Tour, H3C3J7, Montreal, Canada;

关键词: orthology;    paralogy;    gene tree;    species tree;    satisfiability;    consistency;   

DOI  :  10.1186/1471-2164-15-S6-S12

来源: Springer

【 摘 要 】

BackgroundA variety of methods based on sequence similarity, reconciliation, synteny or functional characteristics, can be used to infer orthology and paralogy relations between genes of a given gene family G. But is a given set C of orthology/paralogy constraints possible, i.e., can they simultaneously co-exist in an evolutionary history for G? While previous studies have focused on full sets of constraints, here we consider the general case where C does not necessarily involve a constraint for each pair of genes. The problem is subdivided in two parts: (1) Is C satisfiable, i.e. can we find an event-labeled gene tree G inducing C? (2) Is there such a G which is consistent, i.e., such that all displayed triplet phylogenies are included in a species tree?ResultsPrevious results on the Graph sandwich problem can be used to answer to (1), and we provide polynomial-time algorithms for satisfiability and consistency with a given species tree. We also describe a new polynomial-time algorithm for the case of consistency with an unknown species tree and full knowledge of pairwise orthology/paralogy relationships, as well as a branch-and-bound algorithm in the case when unknown relations are present. We show that our algorithms can be used in combination with ProteinOrtho, a sequence similarity-based orthology detection tool, to extract a set of robust orthology/paralogy relationships.

【 授权许可】

CC BY   
© Lafond and El-Mabrouk; licensee BioMed Central Ltd. 2014