Binary Phylogeny

Binary Phylogeny is the construction of phylogenies (phylogenetic trees) based on binary characters, that is, discrete characters that have just two states. These states are often indicated as 0 and 1.

One way of looking at the input would be as a bipartite graph of Species and Characters with links {s,c} meaning species s has character c. If this graph is given as adjacency lists, it is possible to decide whether the input admits a perfect phylogeny (and construct one if the answer is affirmative) in linear time.

Here is a paper on this topic:

• J. Meidanis, E. G. Munuera. A Simple Linear Time Algorithm for Binary Phylogeny. Proceedings of the Fifteenth International Conference of the Chilean Computing Society, p 275--283, 1995. Download draft