Fasturec

Fasturec is a phylogenomic inference tool for constructing species supertrees from large collections of gene trees under gene tree parsimony (GTP) criteria, while avoiding the requirement that input gene trees be rooted. Traditional GTP formulations account for discordance between gene and species histories caused by events such as gene duplication and loss and deep coalescence, but are NP-complete and typically rely on local-search heuristics guided by exact solutions to local subproblems; moreover, they assume rooted gene trees, even though most phylogenetic pipelines output unrooted trees and correct rooting can be difficult.

Fasturec addresses this by introducing the first nearest-neighbor interchange (NNI)–based local search problems for unrooted GTP formulations and providing linear-time algorithms to solve these local subproblems, enabling efficient stepwise exploration of species-tree space. Implementing these NNI-based heuristics allows practical analyses at the scale of thousands of genes, and application to a large flowering-plant dataset yielded results consistent with an alternative hypothesis about relationships among major angiosperm lineages.