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

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 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)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
144 View
628 Download

Altmetric

Share

More