Which Phylogenetic Networks are Merely Trees with Additional Arcs?

Area of Science:

• Computational Biology
• Phylogenetics
• Graph Theory

Background:

• Phylogenetic networks model evolutionary histories, including reticulate events like hybridization.
• Determining if a network can be represented as a tree with added directed edges is a key problem.
• Existing methods may lack efficiency or clear criteria for this determination.

Purpose of the Study:

• To establish a precise and easily testable criterion for identifying tree-obtainable phylogenetic networks.
• To develop an efficient algorithm for constructing the base tree(s) of such networks.
• To explore the implications and consequences of this network characterization.

Main Methods:

• Utilized a 2-Satisfiability (2-SAT) formulation to derive the network's tree-obtainable property.
• Developed a polynomial-time algorithm based on the 2-SAT solution to reconstruct the underlying tree.
• Analyzed corollaries and derived properties from the main result.

Main Results:

• A precise and efficient 2-SAT based criterion is established for determining if a binary phylogenetic network is tree-obtainable.
• A polynomial-time algorithm is presented that successfully finds the base tree(s) when the network is tree-obtainable.
• Several corollaries and new insights into the structure of tree-obtainable networks are derived.

Conclusions:

• The 2-SAT approach provides a robust and computationally efficient solution to a fundamental problem in phylogenetic network analysis.
• The developed algorithm facilitates the reconstruction of evolutionary histories representable by tree-like structures with reticulations.
• Further research questions and observations arising from this work are highlighted for future investigation.