FastME

FastME infers phylogenetic trees using distance-based algorithms implementing the balanced minimum evolution (BME) criterion to provide statistically consistent and topologically accurate tree estimates.

Key Features:

• Balanced Minimum Evolution (BME): Implements the BME principle with ordinary least-squares (OLS) fitting of a metric to tree structures to achieve statistical consistency and improved topological accuracy relative to Neighbor Joining (NJ).
• Topological Moves: Employs Nearest Neighbor Interchange (NNI) to optimize topology (starting topology in O(n^2) time and refinement cost O(n^2 + pn), where p is the number of swaps) and includes Subtree Pruning and Regrafting (SPR) to expand topology exploration.
• Efficiency: Uses a greedy approach to produce starting topologies and performs operations that scale as O(n^2 * diam(T)) for building and refining trees, where diam(T) is the tree topological diameter.
• Distance Estimation: Supports distance estimation for DNA and proteins with various models and options and integrates OLS fitting to metrics on tree structures.
• Bootstrapping and Parallel Computations: Provides bootstrapping facilities and parallel computation support for resampling-based support assessment.

Scientific Applications:

• Evolutionary inference: Construction of phylogenetic trees for studies in evolutionary biology and related fields.
• Large-scale phylogenetic analyses: Reconstruction and refinement of phylogenies for large or complex datasets where computational scaling is critical.
• Topology-sensitive comparative studies: Analyses requiring improved topological accuracy compared to Neighbor Joining.

Methodology:

Computational methods explicitly include the balanced minimum evolution (BME) criterion with ordinary least-squares (OLS) fitting, a greedy algorithm to produce starting topologies, optimization via Nearest Neighbor Interchange (NNI) with stated complexities (starting O(n^2); refinement O(n^2 + pn)), inclusion of Subtree Pruning and Regrafting (SPR), operations scaling as O(n^2 * diam(T)), distance estimation for DNA and proteins, and bootstrapping with parallel computations.