2023/09/03 by Steven Chaplick, Martinez, Virginia Aardevol, Steven Kelk +8
Computer Science · #Bayesian Modeling and Causal Inference #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Populations and Evolution (q-bio.PE) #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2309.01110
openalex publication_date 2023/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
There are multiple factors which can cause the phylogenetic inference process to produce two or more conflicting hypotheses of the evolutionary history of a set X of biological entities. That is: phylogenetic trees with the same set of leaf labels X but with distinct topologies. This leads naturally to the goal of quantifying the difference between two such trees T1 and T2. Here we introduce the problem of computing a 'maximum relaxed agreement forest' (MRAF) and use this as a proxy for the dissimilarity of T1 and T2, which in this article we assume to be unrooted binary phylogenetic trees. MRAF asks for a partition of the leaf labels X into a minimum number of blocks S1, S2, ... Sk such that for each i, the subtrees induced in T1 and T2 by Si are isomorphic up to suppression of degree-2 nodes and taking the labels X into account. Unlike the earlier introduced maximum agreement forest (MAF) model, the subtrees induced by the Si are allowed to overlap. We prove that it is NP-hard to compute MRAF, by reducing from the problem of partitioning a permutation into a minimum number of monotonic subsequences (PIMS). Furthermore, we show that MRAF has a polynomial time O(log n)-approximation algorithm where n=|X| and permits exact algorithms with single-exponential running time. When at least one of the two input trees has a caterpillar topology, we prove that testing whether a MRAF has size at most k can be answered in polynomial time when k is fixed. We also note that on two caterpillars the approximability of MRAF is related to that of PIMS. Finally, we establish a number of bounds on MRAF, compare its behaviour to MAF both in theory and in an experimental setting and discuss a number of open problems.