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 https://github.com/UdeM-LBIT/OrthoPara-ConstraintChecker.
Document type :
Journal articles
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481206
Contributor : Christophe Paul <>
Submitted on : Wednesday, December 18, 2019 - 3:50:55 PM
Last modification on : Tuesday, July 21, 2020 - 3:42:47 AM
Document(s) archivé(s) le : Thursday, March 19, 2020 - 9:25:38 PM

File

Scornavacca_07.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

393

Files downloads

167