Skip to Main content Skip to Navigation
Book sections

Maximum Compatible Tree

Vincent Berry 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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...
Document type :
Book sections
Complete list of metadata
Contributor : Isabelle Gouat <>
Submitted on : Friday, January 29, 2016 - 1:31:34 PM
Last modification on : Friday, April 23, 2021 - 11:19:28 AM




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⟩



Record views