Testing the Agreement of Trees with Internal Labels

2020/02/22 by Fernández-Baca, David, Liu, Lei
#Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #J.3

paper · doi:10.48550/arxiv.2002.09725

Abstract

The input to the agreement problem is a collection P = \T₁, T₂, … , T_k\ of phylogenetic trees, called input trees, over partially overlapping sets of taxa. The question is whether there exists a tree T, called an agreement tree, whose taxon set is the union of the taxon sets of the input trees, such that for each i ∈ \1, 2, … , k\, the restriction of T to the taxon set of T_i is isomorphic to T_i. We give a O(n k (∑_{i ∈ [k]} d_i + log²(nk))) algorithm for a generalization of the agreement problem in which the input trees may have internal labels, where n is the total number of distinct taxa in P, k is the number of trees in P, and d_i is the maximum number of children of a node in T_i.

Related

• Relaxed Agreement Forests
• On Agreement Subtrees in Multiple Phylogenetic Trees
• Algorithms for Maximum Agreement Forest of Multiple General Trees
• Approximation algorithms for nonbinary agreement forests
• On the Extremal Maximum Agreement Subtree Problem