Title of article
Finding a maximum compatible tree is NP-hard for sequences and trees Original Research Article
Author/Authors
A.M. Hamel، نويسنده , , M.A. Steel، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 1996
Pages
5
From page
55
To page
59
Abstract
We show that the following two related problems arising in phylogenetic analysis are NP-hard:
1.
(i) given a collection of aligned 2-state sequences, find the largest subset of sequences compatible with some tree,
2.
(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.
Keywords
NP-hard , Trees , Compatibility , Sequences
Journal title
Applied Mathematics Letters
Serial Year
1996
Journal title
Applied Mathematics Letters
Record number
896364
Link To Document