Maximum Compatible Tree

Abstract : This problem is a pattern matching problem on leaf-labeled trees. Each input tree is considered as a branching pattern inducing specific groups of leaves. Given a set of input trees with identical leaf sets, the goal is to find the largest subset of leaves on the branching pattern of which the input trees do not disagree. A maximum compatible tree is a tree on such a leaf set and with a branching pattern respecting that of each input tree (see below for a formal definition). The maximum compatible tree problem (mct) is to find such a tree or, equivalently, its leaf set. The main motivation for this problem is in phylogenetics, to measure the similarity between evolutionary trees or to represent a consensus of a set of trees. The problem was introduced in [10] and [11, under the MRST acronym]. Previous related works concern the well-known maximum agreement subtree problem (mast). Solving mastis...