Editing Evolutionary Tree Algorithms: Maximizing Agreement Subtrees

Title: Evolutionary Tree Algorithms: Maximizing Agreement Subtrees

Abstract: This research focuses on the problem of determining the largest possible number of leaves in any agreement subtree of two given evolutionary trees. The study presents an algorithm that can compute this maximum agreement subtree in optimal or near-optimal time depending on the maximum degree of the trees. The algorithm employs new tree contraction techniques and dynamic programming strategies, which result in highly regular structural properties and efficient time bounds.

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

Methodology: The research uses tree contraction techniques and dynamic programming to solve the problem. The tree contraction techniques allow for the reduction of the time complexity, while the dynamic programming approach enables the recursive solution of the problem for smaller subtrees.

Results: The study presents an algorithm that can compute a maximum agreement subtree of two given evolutionary trees in optimal or near-optimal time. The time complexity of the algorithm is O(nlog2n) for trees with a bounded maximum degree, and O(nd2logdlog2n) or O(nd√
dlog3n) for general trees.

Implications: The results of this research have significant implications for computational biology. The algorithm can help determine how much two theories about the evolutionary history of the same species have in common by computing a maximum agreement subtree. This can aid in the reconciliation of different evolutionary trees and contribute to a better understanding of the evolutionary relationships between species.

Open Problem: The research presents an open problem related to the time complexity of the algorithm. Further research is needed to find more efficient ways to compute maxima of multiple sets of sequences in a compressed format.

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

[[Category:Computer Science]]
[[Category:Evolutionary]]
[[Category:Trees]]
[[Category:Agreement]]
[[Category:Research]]
[[Category:Algorithm]]