Gentrius: Generating Trees Compatible With a Set of Unrooted Subtrees and its Application to Phylogenetic Terraces

Area of Science:

• Phylogenetics
• Computational Biology
• Bioinformatics

Background:

• Generating all compatible binary unrooted trees (stands) from a set of subtrees is a classical, computationally challenging problem in phylogenetics.
• Missing data in biological datasets often leads to multiple, equally optimal phylogenetic trees, complicating accurate inference.

Purpose of the Study:

• Introduce Gentrius, an efficient algorithm for generating phylogenetic stands.
• Demonstrate Gentrius's capability to generate large stands of equally scoring trees (phylogenetic terraces) in feasible time.
• Provide a systematic assessment of phylogenetic trees inferred from incomplete data.

Main Methods:

• Developed Gentrius, an efficient algorithm for stand generation.
• Applied Gentrius to simulated and biological datasets with missing data.
• Analyzed the variation in the number of equally optimal trees based on data distribution and phylogeny.

Main Results:

• Gentrius successfully generates stands containing millions of trees in feasible time, overcoming the computational intractability of stand generation.
• The number of equally optimal phylogenetic trees (terraces) varies significantly depending on missing data patterns and inferred phylogeny.
• The strict consensus tree derived from these stands highlights branches robust to missing data.

Conclusions:

• Gentrius offers a practical solution for generating phylogenetic stands, enabling systematic assessment of trees from incomplete data.
• The algorithm provides insights into the structure of tree space influenced by missing data, aiding both applied and theoretical research.