A relation graph for a gene family is a graph with vertices representing the genes, edges connecting pairs of orthologous genes and “missing” edges representing paralogs. While a gene tree directly leads to a set of orthology and paralogy relations, the converse is not always true. Indeed a relation graph cannot necessarily be inferred from any tree, and even if it is “satisfiable” by a tree, this tree is not necessarily “consistent”, i.e. does not necessarily reflect a valid history for the genes, in agreement with a species tree. Here, we consider the problems of minimally correcting a relation graph for satisfiability and consistency, when a degree of confidence is assigned to each orthology or paralogy relation, leading to a weighted relation graph. We provide complexity and algorithmic results for minimizing corrections on a weighted graph, and also for the maximization variant of the problems for unweighted graphs.

(2016). Correction of weighted orthology and paralogy relations. Complexity and algorithmic results . Retrieved from http://hdl.handle.net/10446/78440

Correction of weighted orthology and paralogy relations. Complexity and algorithmic results

DONDI, Riccardo;
2016-01-01

Abstract

A relation graph for a gene family is a graph with vertices representing the genes, edges connecting pairs of orthologous genes and “missing” edges representing paralogs. While a gene tree directly leads to a set of orthology and paralogy relations, the converse is not always true. Indeed a relation graph cannot necessarily be inferred from any tree, and even if it is “satisfiable” by a tree, this tree is not necessarily “consistent”, i.e. does not necessarily reflect a valid history for the genes, in agreement with a species tree. Here, we consider the problems of minimally correcting a relation graph for satisfiability and consistency, when a degree of confidence is assigned to each orthology or paralogy relation, leading to a weighted relation graph. We provide complexity and algorithmic results for minimizing corrections on a weighted graph, and also for the maximization variant of the problems for unweighted graphs.
2016
Dondi, Riccardo; El Mabrouk, Nadia; Lafond, Manuel
File allegato/i alla scheda:
File Dimensione del file Formato  
RelatCorrection.pdf

accesso aperto

Versione: postprint - versione referata/accettata senza referaggio
Licenza: Licenza default Aisberg
Dimensione del file 373.45 kB
Formato Adobe PDF
373.45 kB Adobe PDF Visualizza/Apri
chp_10.1007_978-3-319-43681-4_10.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 320 kB
Formato Adobe PDF
320 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/78440
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact