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). Springer Verlag [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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
