FAST COMPARISON OF EVOLUTIONARY TREES

Constructing evolutionary trees for species sets is a fundamental prob lem in biology. Unfortunately, there is no single agreed upon method f or this task, and many methods are in use. Current practice dictates t hat trees be constructed using different methods and that the resultin g trees then be compared for consensus. It has become necessary to aut omate this process as the number of species under consideration has gr own. We study the Unrooted Maximum Agreement Subtree Problem (UMAST) a nd its rooted variant (RMAST). The UMAST problem is as follows: given a set A and two trees T-0 and T-1 leaf-labeled by the elements of A, f ind a maximum cardinality subset B of A such that the restrictions of T-0 and T-1 to B are topologically isomorphic. Our main result is an O (n(2+o(1))) time algorithm for the UMAST problem. We also derive an O( n(2)) time algorithm for the RMAST problem. The previous best algorith m for both these problems has running time O(n(4.5+o(1))). (C) 1995 Ac ademic Press, Inc.