Maximum Agreement Subtrees in Unrooted Evolutionary Trees

Title: Maximum Agreement Subtrees in Unrooted Evolutionary Trees

Abstract: This article discusses an algorithm for finding the maximum agreement subtree of two unrooted evolutionary trees. This is a significant problem in computational biology, as it helps determine how much two models of evolutionary relationship have in common. The algorithm takes O(n1.5logn) time, matching the best known time complexity for rooted trees. It allows mixed trees, which can contain both directed and undirected edges, and uses a technique called label compression. This technique enables the algorithm to process overlapping subtrees iteratively while keeping the total tree size close to the original input size. The algorithm also uses an unexpectedly fast method for solving the all-cavity maximum weight matching problem, which is a fundamental problem in graph theory.

Main Research Question: How can we efficiently compute the maximum agreement subtree of two unrooted evolutionary trees?

Methodology: The algorithm starts by converting the input trees into mixed trees, which can contain both directed and undirected edges. It then uses a technique called label compression to process the trees recursively. Label compression involves creating a new tree where each node represents a subset of the original nodes. This allows the algorithm to process overlapping subtrees iteratively, which helps speed up the computation. The algorithm also uses an unexpectedly fast method for solving the all-cavity maximum weight matching problem, which is a fundamental problem in graph theory. This allows the algorithm to compute the maximum agreement subtree more efficiently.

Results: The algorithm takes O(n1.5logn) time to compute the maximum agreement subtree of two unrooted trees, matching the best known time complexity for rooted trees. This means that the algorithm can handle trees with unbounded degrees, which is a significant improvement over previous algorithms.

Implications: The algorithm provides a more efficient way to compute the maximum agreement subtree of two unrooted evolutionary trees. This can help researchers in computational biology better understand the evolutionary relationship between species and improve the accuracy of their models. Additionally, the technique of label compression used in the algorithm could have applications in other areas of computer science and mathematics where it is necessary to efficiently process overlapping substructures of a larger structure.

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