On the consistency of orthology relationships - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles BMC Bioinformatics Year : 2016

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 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.
Fichier principal
Vignette du fichier
Scornavacca_07.pdf (716.61 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-01481206 , version 1 (18-12-2019)

Licence

Attribution

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More