Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable.

Area of Science:

• Evolutionary biology
• Phylogenetics
• Computational biology

Background:

• Reticulation processes, including hybridization, lateral gene transfer, and recombination, result in non-tree-like ancestral histories for species.
• Reconstructing evolutionary history often involves analyzing multiple phylogenetic trees representing different genomic regions.
• A key challenge is to determine the minimum number of reticulation events required to explain these multiple trees within a single evolutionary network.

Purpose of the Study:

• To investigate the computational complexity of inferring evolutionary networks from multiple phylogenetic trees.
• Specifically, to determine if the problem of finding the minimum number of reticulation vertices is tractable for a small number of input trees.

Main Methods:

• The study focuses on the problem of finding the minimum number of reticulation vertices needed to explain a collection of rooted binary phylogenetic trees.
• It analyzes the computational complexity of this problem, particularly in the case of two input trees.
• The research employs parameterized complexity theory to assess tractability.

Main Results:

• The problem of finding the minimum number of reticulation vertices is known to be NP-hard even for two phylogenetic trees.
• This paper demonstrates that the problem becomes fixed-parameter tractable when parameterized by the number of reticulation vertices for the two-tree instance.

Conclusions:

• Despite the general NP-hardness, efficient algorithms can be developed for specific cases of phylogenetic network inference.
• The fixed-parameter tractability result offers a more optimistic outlook for reconstructing evolutionary histories with limited reticulation.