The general problem of reconciling the information from evolutionary trees representing the relationships between distinct gene families is of great importance in bioinformatics and has been popularized among the computer science researchers by Ma et al. [From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729–752] where the authors pose the intriguing question if a certain definition of minimum tree that reconciles a gene tree and a species tree is correct. We answer affirmatively to this question; moreover, we show an efficient algorithm for computing such minimum- leaf reconciliation trees and prove the uniqueness of such trees. We then tackle some different versions of the biological problem by showing that the exemplar problem, arising from the exemplar analysis of multigene genomes, is NP-hard even when the number of copies of a given label is at most two. Finally, we introduce two novel formulations for the problem of recombining evolutionary trees, extending the gene duplication problem studied in [Ma et al., From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729–752; M. Fellows et al., On the multiple gene duplication problem, in: Proc. Ninth Internat. Symp. on Algorithms and Computation (ISAAC98), 1998; R. Page, Maps between trees

Bonizzoni, P., DELLA VEDOVA, G., & Dondi, R. (2005). Reconciling a Gene Tree to a Species Tree Under the Duplication Cost Model. THEORETICAL COMPUTER SCIENCE, 347(1-2), 36-53 [10.1016/j.tcs.2005.05.016].

Reconciling a Gene Tree to a Species Tree Under the Duplication Cost Model

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;
2005

Abstract

The general problem of reconciling the information from evolutionary trees representing the relationships between distinct gene families is of great importance in bioinformatics and has been popularized among the computer science researchers by Ma et al. [From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729–752] where the authors pose the intriguing question if a certain definition of minimum tree that reconciles a gene tree and a species tree is correct. We answer affirmatively to this question; moreover, we show an efficient algorithm for computing such minimum- leaf reconciliation trees and prove the uniqueness of such trees. We then tackle some different versions of the biological problem by showing that the exemplar problem, arising from the exemplar analysis of multigene genomes, is NP-hard even when the number of copies of a given label is at most two. Finally, we introduce two novel formulations for the problem of recombining evolutionary trees, extending the gene duplication problem studied in [Ma et al., From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729–752; M. Fellows et al., On the multiple gene duplication problem, in: Proc. Ninth Internat. Symp. on Algorithms and Computation (ISAAC98), 1998; R. Page, Maps between trees
Articolo in rivista - Articolo scientifico
gene trees, gene duplications
English
36
53
Bonizzoni, P., DELLA VEDOVA, G., & Dondi, R. (2005). Reconciling a Gene Tree to a Species Tree Under the Duplication Cost Model. THEORETICAL COMPUTER SCIENCE, 347(1-2), 36-53 [10.1016/j.tcs.2005.05.016].
Bonizzoni, P; DELLA VEDOVA, G; Dondi, R
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/12185
Citazioni
  • Scopus 67
  • ???jsp.display-item.citation.isi??? 60
Social impact