Fast computation of supertrees for compatible phylogenies with nested taxa

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Supertree methods typically combine source trees with only leaf-labeled taxa, assuming no nested taxa across trees.
• Nested taxa, where one taxon is a subset of another (e.g., species within a genus), pose a challenge for standard supertree construction.
• Page's AncestralBuild algorithm was the first to accommodate nested taxa by allowing interior nodes to be labeled.

Purpose of the Study:

• To modify and optimize the AncestralBuild algorithm for improved computational efficiency.
• To enable the construction of supertrees from collections of source trees that include nested taxa.
• To facilitate the analysis of large-scale phylogenetic data and the development of more general supertree methods.

Main Methods:

• Modification of the original AncestralBuild algorithm to enhance its running time.
• Comparison of the modified algorithm's performance against the existing fastest supertree compatibility algorithm (Build).
• Application of the optimized AncestralBuild to construct a phylogeny for strepsirrhine primates.

Main Results:

• The modified AncestralBuild algorithm achieves a running time comparable to the fastest Build algorithm.
• Demonstrated polynomial-time compatibility testing for source trees with interior node taxa.
• Successfully applied the method to generate a comprehensive phylogeny for strepsirrhines.

Conclusions:

• Optimized AncestralBuild provides a computationally efficient solution for supertree construction with nested taxa.
• This advancement is vital for leveraging large phylogenetic databases and integrating into broader supertree methodologies.
• The method's application to strepsirrhines highlights its utility in resolving complex evolutionary relationships.