Maximum Compatible Tree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Book Sections Year : 2016

Maximum Compatible Tree


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...
No file

Dates and versions

lirmm-01264556 , version 1 (29-01-2016)



Vincent Berry. Maximum Compatible Tree. Ming-Yang Kao. Encyclopedia of Algorithms, Springer, 2016, Foundations of Computing, 978-1-4939-2863-7. ⟨10.1007/978-1-4939-2864-4⟩. ⟨lirmm-01264556⟩
95 View
0 Download



Gmail Facebook X LinkedIn More