Finding a maximum compatible tree is NP-hard for sequences and trees
Degree GrantorUniversity of Canterbury
Degree NameResearch report
We show that the· following two related problems arising in phylogenetic analysis are NP-hard: (i) given a collection of aligned 2-state sequences, find a largest subset of sequences compatible with some tree, (ii) given six leaf-labelled trees, find the largest subset S' of the leaves so that the six subtrees induced by S' are compatible.
SubjectsField of Research::06 - Biological Sciences::0603 - Evolutionary Biology::060309 - Phylogeny and Comparative Analysis
- Engineering: Reports