On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees.
IEEE/ACM Trans Comput Biol Bioinform
; 14(3): 587-599, 2017.
Article
em En
| MEDLINE
| ID: mdl-28055898
ABSTRACT
Duplication-Transfer-Loss (DTL) reconciliation has emerged as a powerful technique for studying gene family evolution in the presence of horizontal gene transfer. DTL reconciliation takes as input a gene family phylogeny and the corresponding species phylogeny, and reconciles the two by postulating speciation, gene duplication, horizontal gene transfer, and gene loss events. Efficient algorithms exist for finding optimal DTL reconciliations when the gene tree is binary. However, gene trees are frequently non-binary. With such non-binary gene trees, the reconciliation problem seeks to find a binary resolution of the gene tree that minimizes the reconciliation cost. Given the prevalence of non-binary gene trees, many efficient algorithms have been developed for this problem in the context of the simpler Duplication-Loss (DL) reconciliation model. Yet, no efficient algorithms exist for DTL reconciliation with non-binary gene trees and the complexity of the problem remains unknown. In this work, we resolve this open question by showing that the problem is, in fact, NP-hard. Our reduction applies to both the dated and undated formulations of DTL reconciliation. By resolving this long-standing open problem, this work will spur the development of both exact and heuristic algorithms for this important problem.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Linhagem
/
Família Multigênica
/
Mapeamento Cromossômico
/
Deleção de Genes
/
Evolução Molecular
/
Duplicação Gênica
/
Transferência Genética Horizontal
Tipo de estudo:
Prognostic_studies
/
Risk_factors_studies
Idioma:
En
Revista:
ACM Trans Comput Biol Bioinform
Assunto da revista:
BIOLOGIA
/
INFORMATICA MEDICA
Ano de publicação:
2017
Tipo de documento:
Article