An efficient algorithm for testing the compatibility of phylogenies with nested taxa.

Area of Science:

• Phylogenetics
• Computational Biology
• Taxonomy

Background:

• Semi-labeled trees generalize phylogenetic trees by allowing internal nodes to represent higher-order taxa.
• Taxonomies are a common example of semi-labeled trees used in biological classification.
• The ancestral compatibility problem determines if a set of semi-labeled trees can be represented by a single overarching tree.

Purpose of the Study:

• To develop a novel algorithm for testing ancestral compatibility in collections of semi-labeled trees.
• To improve the efficiency and scalability of ancestral compatibility testing, particularly for high-degree nodes found in taxonomies.

Main Methods:

• An algorithm was developed to solve the ancestral compatibility problem for semi-labeled trees.
• The algorithm's performance was analyzed in terms of time and space complexity.

Main Results:

• A new algorithm achieves a running time of O(N) and space complexity of O(N), where N is the total number of nodes and edges in the input trees.
• The algorithm's efficiency is independent of the degrees of the nodes within the input semi-labeled trees.

Conclusions:

• The developed algorithm provides a significant improvement for ancestral compatibility testing, especially when dealing with taxonomies.
• This method enhances the ability of researchers to incorporate broader taxonomic data into phylogenetic analyses efficiently.