Reciprocal best match graphs
From MaRDI portal
Abstract: Reciprocal best matches play an important role in numerous applications in computational biology, in particular as the basis of many widely used tools for orthology assessment. Nevertheless, very little is known about their mathematical structure. Here, we investigate the structure of reciprocal best match graphs (RBMGs). In order to abstract from the details of measuring distances, we define reciprocal best matches here as pairwise most closely related leaves in a gene tree, arguing that conceptually this is the notion that is pragmatically approximated by distance- or similarity-based heuristics. We start by showing that a graph is an RBMG if and only if its quotient graph w.r.t. a certain thinness relation is an RBMG. Furthermore, it is necessary and sufficient that all connected components of are RBMGs. The main result of this contribution is a complete characterization of RBMGs with 3 colors/species that can be checked in polynomial time. For 3 colors, there are three distinct classes of trees that are related to the structure of the phylogenetic trees explaining them. We derive an approach to recognize RBMGs with an arbitrary number of colors; it remains open however, whether a polynomial-time for RBMG recognition exists. In addition, we show that RBMGs that at the same time are cographs (co-RBMGs) can be recognized in polynomial time. Co-RBMGs are characterized in terms of hierarchically colored cographs, a particular class of vertex colored cographs that is introduced here. The (least resolved) trees that explain co-RBMGs can be constructed in polynomial time.
Recommendations
Cites work
- A Linear Recognition Algorithm for Cographs
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- A simple linear time algorithm for cograph recognition
- Alternative characterizations of Fitch's xenology relation
- Best match graphs
- Cardinal multiplication of structures with a reflexive relation
- Combinatorial logarithm and point-determining cographs
- Complement reducible graphs
- Dacey Graphs
- Fully dynamic recognition algorithm and certificate for directed cographs
- Handbook of product graphs
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- On the Cartesian skeleton and the factorization of the strong product of digraphs
- Orthology relations, symbolic ultrametrics, and cographs
- Reconstructing gene trees from Fitch's xenology relation
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- The number of caterpillars
Cited in
(13)- Least resolved trees for two-colored best match graphs
- Cograph editing: Merging modules is equivalent to editing P₄s
- The structure of 2-colored best match graphs
- Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee
- Best match graphs and reconciliation of gene trees with species trees
- Best match graphs
- Complete characterization of incorrect orthology assignments in best match graphs
- Indirect identification of horizontal gene transfer
- Complexity of modification problems for reciprocal best match graphs
- Complexity of modification problems for best match graphs
- Automorphisms and quotients of 2-colored quasi best match graphs
- Hierarchical and modularly-minimal vertex colorings
- Quasi-best match graphs
This page was built for publication: Reciprocal best match graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2299268)
