Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
423557 | Electronic Notes in Theoretical Computer Science | 2016 | 16 Pages |
Abstract
Gene tree correction has recently gained interest in phylogenomics, as it gives insights in understanding the evolution of gene families. Following some recent approaches based on leaf edit operations, we consider a variant of the problem where a gene tree is corrected by inserting leaves with labels in a multiset M. We show that the problem of deciding whether a gene tree can be corrected by inserting leaves with labels in M is NP-complete. Then, we consider an optimization variant of the problem that asks for the correction of a gene tree with leaves labeled by a multiset M′, with M′⊇M, having minimum size. For this optimization variant of the problem, we present a factor 2 approximation algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics