From Constrained to Unconstrained Maximum Agreement Subtree in Linear Time

We propose and study the Maximum Constrained Agreement Subtree (MCAST) problem, which is a variant of the classical Maximum Agreement Subtree (MAST) problem. Our problem allows users to apply their domain knowledge to control the construction of the agreement subtrees in order to get better results. We show that the MCAST problem can be reduced to the MAST problem in linear time and thus we have algorithms for MCAST with running times matching the fastest known algorithms for MAST. A preliminary version of this paper appears in the Proceedings of the Fifth Workshop on Algorithms in Bioinformatics (WABI 2005). Research of H.F. Ting is supported in part by Hong Kong RGC Grant HKU-7172/06E.