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(n 3) 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 .
Keywords: Inapproximability; Orthology detection; Para-NP hardness; Polynomial-time algorithms.