Instance: A phylogenetic tree P on a set of n genomes, a number k and a reconstruction method M.
Question: Find k genomes in P that allows the ancestral character states at the root of P to be reconstructed with the maximum accuracy, using method M.
Since the reconstruction accuracy depends on both the topology of the given phylogeny and the conservation probability of each branch, the genome selection for reconstruction problem is unlikely polynomial-time solvable although its NP-hardness is not proved yet. In the rest of this section, we present two greedy algorithms for it.
Was this article helpful?