MASTtreedist

MASTtreedist computes Maximum Agreement SubTrees (MAST) to quantify similarity among phylogenetic trees by identifying shared leaf sets.

Key Features:

• Integration with Mesquite's Tree Set Viz module: Integrated with Mesquite's Tree Set Viz module to provide tree comparison distances for downstream analysis.
• Advanced Distance Metrics: Implements the Maximum Agreement Subtree (MAST) metric to detect common substructures and provides an alternative assessment to the Robinson-Foulds (RF) topological distance.
• Efficient Optimization Techniques: Computes MAST distances by formulating the problem as a maximum weight clique problem and employs efficient optimizations for this NP-hard task.
• Visualization of Tree Differences: Projects pairwise MAST-derived distances into two-dimensional space using multidimensional scaling (MDS) to represent topological differences as scatter plots.
• Statistical Evaluation: Performs statistical evaluations on experimental datasets to compare MAST-based performance with the Robinson-Foulds (RF) metric.

Scientific Applications:

• Evolutionary biology and systematics: Compares multiple phylogenetic trees to identify representations of evolutionary relationships by focusing on shared subtrees.
• Phylogenetic reconstruction assessment: Assesses divergences among candidate tree topologies and small subtree differences during phylogenetic tree reconstruction.

Methodology:

Calculates the number of leaves shared by Maximum Agreement SubTrees across phylogenetic trees; formulates MAST computation as a maximum weight clique problem and applies efficient optimizations; projects resulting distances with multidimensional scaling (MDS); and conducts statistical comparisons with Robinson-Foulds (RF) on experimental datasets.