FINDING A MAXIMUM COMPATIBLE TREE IS NP-HARD FOR SEQUENCES AND TREES

Authors
HAMEL AM STEEL MA
Citation
Am. Hamel et Ma. Steel, FINDING A MAXIMUM COMPATIBLE TREE IS NP-HARD FOR SEQUENCES AND TREES, Applied mathematics letters, 9(2), 1996, pp. 55-59
Citations number
8
Categorie Soggetti
Mathematics,Mathematics
Journal title
Applied mathematics letters → ACNP
ISSN journal
08939659
Volume
9
Issue
2
Year of publication
1996
Pages
55 - 59
Database
ISI
SICI code
0893-9659(1996)9:2<55:FAMCTI>2.0.ZU;2-1
Abstract
We show that the following two related problems arising in phylogeneti c analysis are NP-hard: (i) given a collection of aligned P-state sequ ences, find the largest subset of sequences compatible with some tree, (ii) given six trees, leaf-labelled by S, find the largest subset S' of S so that the six subtrees induced by S' are compatible.