Skip to Main content Skip to Navigation
Journal articles

On the consistency of orthology relationships

Mark Jones 1 Christophe Paul 1 Celine Scornavacca 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 C on a collection of n genes. Results: We give the first polynomial algorithm-more precisely a O(n 3) time algorithm-to decide whether C 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
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Wednesday, December 18, 2019 - 3:50:55 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Thursday, March 19, 2020 - 9:25:38 PM


Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution 4.0 International License



Mark Jones, Christophe Paul, Celine Scornavacca. On the consistency of orthology relationships. BMC Bioinformatics, BioMed Central, 2016, 17 (S14), pp.11-14. ⟨10.1186/s12859-016-1267-3⟩. ⟨lirmm-01481206⟩



Record views


Files downloads