Best Match Graphs With Binary Trees

Area of Science:

• Computational Biology
• Bioinformatics
• Graph Theory

Background:

• Best match graphs (BMGs) are crucial in graph-based orthology detection, holding significant gene tree information.
• Understanding the structure and properties of BMGs is essential for accurate phylogenetic inference.

Purpose of the Study:

• To develop an algorithm for determining if a BMG is binary-explainable.
• To construct the corresponding binary gene tree if the BMG is binary-explainable.
• To analyze the relationship between different types of trees derived from BMGs and the complexity of graph editing.

Main Methods:

• A near-cubic time algorithm is introduced to test for binary-explainability of BMGs.
• The algorithm constructs a fully resolved gene tree from a binary-explainable BMG.
• The study analyzes the unique binary-refinable tree (BRT) and the least resolved tree of a BMG.
• NP-completeness is shown for editing arbitrary graphs to binary-explainable BMGs, with an integer linear program formulation provided.

Main Results:

• A near-cubic algorithm successfully determines BMG binary-explainability and constructs the associated gene tree.
• All binary trees explaining a BMG are refinements of the unique BRT.
• The BRT generally refines the unique least resolved tree of a BMG.
• Editing arbitrary graphs to binary-explainable BMGs is NP-complete.

Conclusions:

• The developed algorithm provides an efficient method for analyzing BMGs in the context of gene tree reconstruction.
• The findings clarify the hierarchical relationships between different tree representations of BMGs.
• The NP-completeness result highlights the computational challenges in graph-based orthology detection and phylogenetic analysis.