tripVote

tripVote completes partially represented gene trees without requiring a species tree by optimizing quartet distance to a given set of gene trees.

Key Features:

• Species-tree-free completion: Completes gene trees without relying on a reference species tree.
• Quartet-distance optimization: Formulates completion as an optimization problem minimizing quartet distance relative to a given set of gene trees.
• Algorithmic extension: Extends the algorithm of Brodal et al. to address the gene-tree completion problem.
• Quasi-linear time complexity: Solves the completion problem in quasi-linear time.
• Reference-based inference: Uses other gene trees as references to place missing taxa.
• Validation on data: Demonstrated accuracy on simulated studies and empirical data analyses.
• Missing-data focus: Targets missing taxa common in genome-wide phylogenomic datasets.

Scientific Applications:

• Gene tree completion for downstream analyses: Enables completion of gene trees required by downstream phylogenomic methods.
• Phylogenetic inference without a species tree: Permits reconstruction of gene-level phylogenies when a comprehensive species tree is unavailable.
• Comparative genomics and evolutionary history: Supports investigations of genetic relationships and evolutionary histories using completed gene trees.

Methodology:

Formulates gene-tree completion as an optimization minimizing quartet distance to a set of gene trees, extends the Brodal et al. algorithm to solve this problem, and implements a solution with quasi-linear time complexity using other gene trees as references.