Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks.

Area of Science:

• Evolutionary biology
• Computational phylogenetics
• Bioinformatics

Background:

• Phylogenetic networks model evolutionary histories with reticulate events like hybridization.
• Network level k quantifies non-treelike evolutionary complexity, with level-0 networks being trees.
• Constructing these networks from smaller evolutionary trees (triplets) is crucial for understanding complex evolutionary processes.

Purpose of the Study:

• To investigate the computational complexity of constructing level-k phylogenetic networks from triplets.
• To determine if unique level-k networks can be defined by their constituent triplets.
• To develop algorithms for constructing phylogenetic networks, especially in computationally intractable scenarios.

Main Methods:

• Theoretical analysis of phylogenetic network construction from triplets.
• Proof of NP-hardness for constructing level-k networks consistent with all or a maximum number of input triplets.
• Development of an exact algorithm for constructing maximum-consistent level-1 phylogenetic networks.

Main Results:

• A level-k phylogenetic network is uniquely defined by its triplets for any k.
• Constructing level-k phylogenetic networks from triplets is NP-hard for k >= 1.
• Constructing level-k phylogenetic networks consistent with a maximum number of triplets is NP-hard for k >= 0, even with dense input.
• An exact algorithm for constructing maximum-consistent level-1 networks was developed.

Conclusions:

• The unique definition of level-k networks by triplets provides a theoretical foundation.
• The NP-hardness results highlight the computational challenges in phylogenetic network inference.
• The developed algorithm offers a practical solution for constructing level-1 networks in challenging cases, aiding evolutionary history reconstruction.