Optimal Agreement Supertrees

An agreement supertree of a collection of unrooted phylogenetic trees {T1 , T2 , . . . , Tk} with leaf sets ), L(T2), . . . , L(Tk ) is an unrooted tree T with leaf set ) # # L(Tk ) such that each tree T i is an induced subtree of T . In some cases, there may be no possible agreement supertrees of a set of trees, in other cases there may be exponentially many. We present polynomial time algorithms for computing an optimal agreement supertree, if one exists, of a bounded number of binary trees. The criteria of optimality can be one of four standard phylogenetic criteria: binary character compatibility; maximum summed quartet weight; ordinary least squares; and minimum evolution. The techniques can be used to search an exponentially large number of trees in polynomial time