Maximum agreement subtree problem explained

T _{1,\ldots,} T _{m} each containing n leaves. The leaves of these trees are given labels from some set L with |L| = n so that no pair of leaves in the same tree sharing the same label, within the same tree the labelling for each leaf is distinct. In this problem one would like to find the largest subset L'\subset L such that the minimal spanning subtrees containing the leaves in L' , of T _{1\mid} S,\ldots, T _{m\mid} S are the "same" while preserving the labelling.

Formulations

Maximum homeomorphic agreement subtree^[1]

This version requires that the subtrees

T _{1\mid} S,\ldots, T _{m\mid} S are homeomorphic to one another.

Rooted maximum homeomorphic agreement subtree

This version is the same as the maximum homeomorphic agreement subtree, but we further assume that

T _{1,\ldots,T} _{m} are rooted and that the subtrees T _{1\mid} S,\ldots, T _{m\mid} S contain the root node. This version of the maximum agreement subtree problem is used for the study of phylogenetic trees. Because of its close ties with phylogeny this formulation is often what is mean when one refers to the "maximum agreement subtree" problem.

Other variants

There exits other formulations for example the (rooted) maximum isomorphic agreement subtree where we require the subtrees to be isomorphic to one another.

See also

• Frequent subtree mining

References

• Kao. Ming-Yang. Lam. Tak-Wah. Sung. Wing-Kin. Ting. Hing-Fung. An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings. Journal of Algorithms. August 2001. 40. 2. 212–233. 10.1006/jagm.2001.1163. cs/0101010.

Notes and References

1. Amir. A.. Keselman. D.. 1997-12-01. Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms. SIAM Journal on Computing. 26. 6. 1656–1669. 10.1137/S0097539794269461. 0097-5397. 10.1.1.133.6891.