Do Branch Lengths Help to Locate a Tree in a Phylogenetic Network?

Area of Science:

• Evolutionary biology
• Computational phylogenetics
• Bioinformatics

Background:

• Phylogenetic networks model complex evolutionary histories including reticulate events like gene transfer and hybridization.
• The tree containment problem asks if a given phylogenetic tree is embedded within a phylogenetic network.
• Previous studies primarily focused on network and tree topology, neglecting branch length information.

Purpose of the Study:

• To investigate the tree containment problem in phylogenetic networks incorporating branch length information.
• To assess the computational complexity of including evolutionary change (branch lengths) in tree containment.
• To develop efficient algorithms for tree containment in biologically relevant network scenarios.

Main Methods:

• Formulation of tree containment problem variants that explicitly include branch lengths.
• Computational complexity analysis of the length-aware tree containment problem.
• Development and application of specialized algorithms for specific network types.

Main Results:

• The general tree containment problem becomes computationally hard when branch lengths are considered.
• Efficient algorithms are provided for specific, biologically relevant cases of phylogenetic networks.
• For networks of limited complexity, algorithms can identify the closest tree (in terms of branch lengths) with the same topology.

Conclusions:

• Incorporating branch lengths into the tree containment problem significantly increases computational difficulty.
• Specialized algorithmic solutions are effective for certain classes of phylogenetic networks.
• This work advances the computational methods for inferring evolutionary history from complex phylogenetic data.