Maximum Agreement Subtree Algorithm for Unrooted Evolutionary Trees

Title: Maximum Agreement Subtree Algorithm for Unrooted Evolutionary Trees

Abstract: This research presents an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.5logn) time for trees with unbounded degrees, matching the best known time complexity for the rooted case. The algorithm allows the input trees to be mixed trees, i.e., trees that may contain directed and undirected edges at the same time. The main technique used is label compression, which enables the algorithm to process overlapping subtrees iteratively while keeping the total tree size close to the original input size. This technique builds on an unexpectedly fast algorithm for the all-cavity maximum weight matching problem, which asks for the weight of a maximum weight matching in a bipartite graph for each node. If the graph has nnodes, medges, and maximum edge weight N, the algorithm takes O(√nmlog(nN)) time, matching the best known time bound for computing a single maximum weight matching.

Main Research Question: How can we efficiently compute a maximum agreement subtree of two unrooted evolutionary trees, even when they contain mixed edges (both directed and undirected)?

Methodology: The research uses a recursive strategy to compute the maximum agreement subtree. The key technique is label compression, which allows the algorithm to process overlapping subtrees while maintaining the total tree size. This technique is built on an all-cavity maximum weight matching algorithm, which is used to find the maximum weight matching in a bipartite graph for each node.

Results: The research presents an algorithm that takes O(n1.5logn) time to compute a maximum agreement subtree of two unrooted trees, even when they contain mixed edges. This matches the best known time complexity for the rooted case.

Implications: This research has important implications for computational biology. It provides a more efficient way to compare two unrooted evolutionary trees, which is useful for modeling the evolutionary relationship of species. The algorithm can handle mixed trees, which allows it to process a broader range of information. Additionally, the use of label compression and the all-cavity maximum weight matching algorithm could have applications in other areas of computer science and mathematics.

Link to Article: https://arxiv.org/abs/0101031v2 Authors: arXiv ID: 0101031v2