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

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 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 ...
Fichier principal
Vignette du fichier
mct.pdf (92.52 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00324061 , version 1 (23-09-2008)



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⟩
130 View
610 Download



Gmail Mastodon Facebook X LinkedIn More