Best Match Graphs
Preprint
Abstract
THIS IS A CORRECTED VERSION INCLUDING AN APPENDED CORRIGENDUM. Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let $T$ be a phylogenetic (gene) tree $T$ and $\sigma$ an assignment of leaves of $T$ to species. The best match graph $(G,\sigma)$ is a digraph that contains an arc from $x$ to $y$ if the genes $x$ and $y$ reside in different species and $y$ is one of possibly many (evolutionary) closest relatives of $x$ compared to all other genes contained in the species $\sigma(y)$. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether $(G,\sigma)$ derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains $(G,\sigma)$, which can also be constructed in cubic time.
Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- Complete Characterization of Incorrect Orthology Assignments in Best Match GraphsJournal of Mathematical Biology, 2021
- Reconstructing gene trees from Fitch’s xenology relationJournal of Mathematical Biology, 2018
- Fast Compatibility Testing for Rooted Phylogenetic TreesAlgorithmica, 2017
- On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositionsJournal of Combinatorial Optimization, 2017
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relationsJournal of Mathematical Biology, 2016
- Orthology relations, symbolic ultrametrics, and cographsJournal of Mathematical Biology, 2012
- Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary BiologyAlgorithmica, 1999
- A simple sub-quadratic algorithm for computing the subset partial orderInformation Processing Letters, 1995
- Extension Operations on Sets of Leaf-Labeled TreesAdvances in Applied Mathematics, 1995
- Point determination in graphsDiscrete Mathematics, 1973