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 tree collection with identical leaf sets, the goal is to find a largest subset of leaves on the branching pattern of which the input trees do not disagree. A maximum compatible tree is a tree with such a leaf-set and with the branching patterns of the input trees for these leaves. 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 evoluti ...
Document type :
Book sections
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Vincent Berry <>
Submitted on : Tuesday, September 23, 2008 - 6:54:48 PM
Last modification on : Friday, April 23, 2021 - 11:24:26 AM
Long-term archiving on: : Friday, June 4, 2010 - 11:44:14 AM


Files produced by the author(s)




Vincent Berry. Maximum Compatible Tree. Ming-Yang Kao. Encyclopedia of Algorithms, Springer, pp.499-502, 2008, Foundations of Computing, 978-0-387-30770-1. ⟨10.1007/978-0-387-30162-4_223⟩. ⟨lirmm-00324061⟩



Record views


Files downloads