The maximum agreement subtree problem

DOI10.1016/J.DAM.2013.02.037MaRDI QIDQ2446824zbMATH OpenOpenAlexFDO

Authors Daniel Martin, Bhalchandra D. Thatte

Publication date 22 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5168

zbMATH Keywords

maximum agreement subtreephylogenetics

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Problems related to evolution (92D15)

Abstract: In this paper we investigate an extremal problem on binary phylogenetic trees. Given two such trees $T_1$ and $T_2$, both with leaf-set $1,2,\mathrm{...},n$, we are interested in the size of the largest subset $Ssubseteq1,2,\mathrm{...},n$ of leaves in a common subtree of $T_1$ and $T_2$. We show that any two binary phylogenetic trees have a common subtree on $Omega(sqrtlogn)$ leaves, thus improving on the previously known bound of $Omega(loglogn)$ due to M. Steel and L. Szekely. To achieve this improved bound, we first consider two special cases of the problem: when one of the trees is balanced or a caterpillar, we show that the largest common subtree has $Omega(logn)$ leaves. We then handle the general case by proving and applying a Ramsey-type result: that every binary tree contains either a large balanced subtree or a large caterpillar. We also show that there are constants $c,alpha>0$ such that, when both trees are balanced, they have a common subtree on $c{n}^{a}lpha$ leaves. We conjecture that it is possible to take $alpha=1/2$ in the unrooted case, and both $c=1$ and $alpha=1/2$ in the rooted case.

Recommendations

• On the extremal maximum agreement subtree problem
• An improved bound on the maximum agreement subtree problem
• On the largest common subtree of random leaf-labeled binary trees
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• scientific article; zbMATH DE number 871929

Cites work

• An improved bound on the maximum agreement subtree problem
• scientific article; zbMATH DE number 434699 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Kaikoura tree theorems: Computing the maximum agreement subtree

Cited in

(19)

• An improved bound on the maximum agreement subtree problem
• On the extremal maximum agreement subtree problem
• Extremal distances for subtree transfer operations in binary trees
• Maximum agreement and compatible supertrees
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Bounds on the expected size of the maximum agreement subtree
• scientific article; zbMATH DE number 1974592 (Why is no real title available?)
• scientific article; zbMATH DE number 1746436 (Why is no real title available?)
• On the maximum quartet distance between phylogenetic trees
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Largest Weight Common Subtree Embeddings with Distance Penalties
• On the largest common subtree of random leaf-labeled binary trees
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• Inducibility in binary trees and crossings in random tanglegrams
• Trees with large numbers of subtrees
• Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees
• An improved lower bound on the largest common subtree of random leaf-labeled binary trees
• Split sizes and extremal tree shapes
• Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees

This page was built for publication: The maximum agreement subtree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446824)