title: Approximating the correction of weighted and unweighted orthology and paralogy relations.
abstract: BACKGROUND
  Given a gene family, the relations between genes (orthology/paralogy), are represented by a relation graph, where edges connect pairs of orthologous genes and "missing" edges represent paralogs. While a gene tree directly induces a relation graph, the converse is not always true. Indeed, a relation graph is not necessarily "satisfiable", i.e. does not necessarily correspond to a gene tree. And even if that holds, it may not be "consistent", i.e. the tree may not represent a true history in agreement with a species tree. Previous studies have addressed the problem of correcting a relation graph for satisfiability and consistency. Here we consider the weighted version of the problem, where a degree of confidence is assigned to each orthology or paralogy relation. We also consider a maximization variant of the unweighted version of the problem.
  
  
  RESULTS
  We provide complexity and algorithmic results for the approximation of the considered problems. We show that minimizing the correction of a weighted graph does not admit a constant factor approximation algorithm assuming the unique game conjecture, and we give ann-approximation algorithm,nbeing the number of vertices in the graph. We also provide polynomial time approximation schemes for the maximization variant for unweighted graphs.
  
  
  CONCLUSIONS
  We provided complexity and algorithmic results for variants of the problem of correcting a relation graph for satisfiability and consistency. For the maximization variants we were able to design polynomial time approximation schemes, while for the weighted minimization variants we were able to provide the first inapproximability results.
authors.affiliation: Dipartimento di Lettere, Filosofia, Comunicazione, Università degli Studi di Bergamo, Via Donizetti 3, 24129 Bergamo, Italy.
authors.forename: Riccardo
authors.initials: R
authors.lastname: Dondi
authors.affiliation: Department of Mathematics and Statistics, University of Ottawa, Ottawa, Canada.
authors.forename: Manuel
authors.initials: M
authors.lastname: Lafond
authors.affiliation: Département d'informatique et de recherche opérationnelle, Université de Montréal, Quebec, Canada.
authors.forename: Nadia
authors.initials: N
authors.lastname: El-Mabrouk
keywords: Approximation algorithms; Gene tree; Orthology; Paralogy; Species tree