| 1 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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 e#cient 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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||