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 #N#                    #N#                      #N#                    #N#                    #N#                      #N#                        C#N#                      #N#                    #N#                    $\mathcal {C}$#N#                   on a collection of n genes. We give the first polynomial algorithm – more precisely a O(n#N#                           3) time algorithm – to decide whether #N#                    #N#                      #N#                    #N#                    #N#                      #N#                        C#N#                      #N#                    #N#                    $\mathcal {C}$#N#                   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. Our polynomial algorithm for checking consistency has been implemented in Python and is available at #N#                    https://github.com/UdeM-LBIT/OrthoPara-ConstraintChecker#N#                    #N#                  .
['M. P. A. Jones', 'Christophe Paul', 'Celine Scornavacca']
On the consistency of orthology relationships