Hunting for binary trees in binary character sets : efficient algorithms for extraction, enumeration and optimization (1995)
We describe an efficient solution to a useful variant of the NP-hard Maximum Compatible Subset problem. Let S be a collection of binary characters. We first wish to determine whether there exists a subcollection S' ⊆ S such that S' equals the set of splits of a binary tree. We provide a polynomial time algorithm that solves this problem and also counts how many such subcollections there are. Furthermore, if each of the given characters is weighted, we can efficiently find the subcollection of characters that corresponds to a binary tree and has maximum or minimum summed weight. The algorithm can be extended to deal with subcollections S'⊂ S that correspond to trees with bounded vertex degree, and still have polynomial time efficiency.
KeywordsCharacter compatibility; binary tree; phylogenetic trees; phylogenetic inference
ANZSRC Fields of Research01 - Mathematical Sciences
RightsCopyright David James Bryant
Showing items related by title, author, creator and subject.
Huber, Katharina T.; Moulton, Vincent; Steel, Mike (University of Canterbury, 2002)It was recently shown that just five characters (functions on a finite set X) suffice to convexly define a trivalent tree with leaf set X. Here we show that four characters suffice which, since three characters is not ...
Grünewald, S.; Humphries, P. J.; Semple, C. (University of Canterbury. Dept. of Mathematics and Statistics, 2005)A collection P of leaf-labelled trees is compatible if there exists a single leaf-labelled tree that displays each of the trees in P. Despite its difficulty, determining the compatibility of P is a fundamental task in ...
Ng, Meei Pyng; Steel, M.; Wormald, N. (University of Canterbury, 1995)Given a set of trees with leaves labelled from a set L, is there a tree T with leaves labelled by L such that each of the given trees is homeomorphic to a subtree of T? This question is known to be NPcomplete in general, ...