CONSTRUCTING PHYLOGENETIC TREES EFFICIENTLY USING COMPATIBILITY CRITERIA

The Character Compatibility Problem is a classical problem in computat ional biology concerned with constructing phylogenetic trees of minimu m possible evolution from qualitative character sets. This problem aro se in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two-state) characters and for two characters at a time, while the complexity of the general pro blem remained open. In this paper we will discuss the remarkable progr ess on this problem since 1990.