Hunting for binary trees in binary character sets : efficient algorithms for extraction, enumeration and optimization (1995)
View/Open
Type of Content
Discussion / Working PapersDegree Name
Research reportPublisher
University of Canterbury. Dept. of MathematicsCollections
 Engineering: Reports [723]
Abstract
We describe an efficient solution to a useful variant of the NPhard 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.
Keywords
Character compatibility; binary tree; phylogenetic trees; phylogenetic inferenceANZSRC Fields of Research
01  Mathematical SciencesRights
Copyright David James BryantRelated items
Showing items related by title, author, creator and subject.

Four characters suffice to convexly define a phylogenetic tree
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 ... 
Quartet compatibility and the quartet graph
Grünewald, S.; Humphries, P. J.; Semple, C. (University of Canterbury. Dept. of Mathematics and Statistics, 2005)A collection P of leaflabelled trees is compatible if there exists a single leaflabelled tree that displays each of the trees in P. Despite its difficulty, determining the compatibility of P is a fundamental task in ... 
The difficulty of constructing a leaflabelled tree including or avoiding given subtrees
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, ...