Maximal acyclic agreement forests.

Finding the hybridization number of a pair or set of trees, [Formula: see text], is a well-studied problem in phylogenetics and is equivalent to finding a maximum acyclic agreement forest (MAAF) for [Formula: see text]. This article defines a new type of acyclic agreement forest called a maximal acyclic agreement forest (mAAF). The property for which mAAFs are "simplest" is more general and could be considered more biologically relevant than the corresponding property for MAAFs, and the set of MAAFs for any [Formula: see text] is a subset of the set of mAAFs for [Formula: see text]. This article also presents two new algorithms; one finds a mAAF for any [Formula: see text] in polynomial time and the other is an exhaustive search that finds all mAAFs for some [Formula: see text], which is also a new approach to finding the hybridization number when applied to a pair of trees. The exhaustive search algorithm is applied to a real world data set, and the findings are compared to previous results.