Testing the agreement of trees with internal labels.

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Semi-labeled trees, including phylogenetic trees and taxonomies, represent evolutionary relationships.
• The agreement problem seeks a consensus tree from multiple semi-labeled trees with overlapping taxa.
• Limited taxonomic overlap hinders the construction of large phylogenetic supertrees.

Purpose of the Study:

• To develop an efficient algorithm for solving the agreement problem.
• To facilitate the integration of taxonomies into phylogenetic supertree analyses.
• To address the challenge of limited taxonomic overlap in synthesizing evolutionary data.

Main Methods:

• Developed a novel algorithm to solve the agreement problem.
• The algorithm's time complexity is O(n^k * Delta), where n is the number of taxa, k is the number of trees, and Delta is the maximum node degree.
• The algorithm is designed for synthesizing semi-labeled trees.

Main Results:

• A polynomial-time algorithm for the agreement problem was developed.
• The algorithm efficiently determines the existence of an agreement tree.
• Computational experiments show practical performance exceeding worst-case bounds.

Conclusions:

• The new algorithm aids in integrating taxonomies into supertree analyses.
• This approach can help overcome limitations posed by sparse taxonomic overlap.
• The findings contribute to more robust phylogenetic synthesis.