In this paper we deal with the general problem of recombining the information from evolutionary trees representing the relationships between distinct gene families. First we solve a problem from [8] regarding the construction of a minimum reconciled tree by giving an efficient algorithm. Then we show that the exemplar problem, arising from the exemplar analysis of multigene genomes [2], 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 notion of the gene duplication problem studied in [8,11,9, 10,6], and we give an exact algorithm (via dynamic programming) for one of the formulations given. © Springer-Verlag Berlin Heidelberg 2003.

Bonizzoni, P., DELLA VEDOVA, G., & Dondi, R. (2003). Reconciling Gene Trees to a Species Tree. In Algorithms and Complexity, 5th Italian Conference, CIAC (pp.120-131) [10.1007/3-540-44849-7_18].

Reconciling Gene Trees to a Species Tree

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;
2003

Abstract

In this paper we deal with the general problem of recombining the information from evolutionary trees representing the relationships between distinct gene families. First we solve a problem from [8] regarding the construction of a minimum reconciled tree by giving an efficient algorithm. Then we show that the exemplar problem, arising from the exemplar analysis of multigene genomes [2], 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 notion of the gene duplication problem studied in [8,11,9, 10,6], and we give an exact algorithm (via dynamic programming) for one of the formulations given. © Springer-Verlag Berlin Heidelberg 2003.
paper
Scientifica
gene duplications, gene losses
English
Algorithms and Complexity, 5th Italian Conference
3-540-40176-8
http://dx.doi.org/10.1007/3-540-44849-7_18
Bonizzoni, P., DELLA VEDOVA, G., & Dondi, R. (2003). Reconciling Gene Trees to a Species Tree. In Algorithms and Complexity, 5th Italian Conference, CIAC (pp.120-131) [10.1007/3-540-44849-7_18].
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/34699
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
Social impact