title: On the consistency of orthology relationships.
abstract: BACKGROUND
  Orthologs inference is the starting point of most comparative genomics studies, and a plethora of methods have been designed in the last decade to address this challenging task. In this paper we focus on the problems of deciding consistency with a species tree (known or not) of a partial set of orthology/paralogy relationships [Formula: see text] on a collection of n genes.
  
  
  RESULTS
  We give the first polynomial algorithm - more precisely a O(n3) time algorithm - to decide whether [Formula: see text] is consistent, even when the species tree is unknown. We also investigate a biologically meaningful optimization version of these problems, in which we wish to minimize the number of duplication events; unfortunately, we show that all these optimization problems are NP-hard and are unlikely to have good polynomial time approximation algorithms.
  
  
  CONCLUSIONS
  Our polynomial algorithm for checking consistency has been implemented in Python and is available at https://github.com/UdeM-LBIT/OrthoPara-ConstraintChecker .
authors.affiliation: LIRMM, CNRS, Université de Montpellier, Montpellier, France.
authors.forename: Mark
authors.initials: M
authors.lastname: Jones
authors.affiliation: ISE-M, CNRS, IRD, EPHE, Université, Montpellier, France.
authors.forename: Christophe
authors.initials: C
authors.lastname: Paul
authors.affiliation: ISE-M, CNRS, IRD, EPHE, Université, Montpellier, France. celine.scornavacca@umontpellier.fr.
authors.forename: Céline
authors.initials: C
authors.lastname: Scornavacca
mesh_terms: D000465:Algorithms; D023281:Genomics; D020407:Internet; D014584:User-Computer Interface
keywords: Inapproximability; Orthology detection; Para-NP hardness; Polynomial-time algorithms