Best match graphs with binary trees

DOI10.1007/978-3-030-74432-8_6MaRDI QIDQ2062000zbMATH OpenOpenAlexFDO

Authors David Schaller, Manuela Geiß, Marc Hellmuth, Peter F. Stadler

Publication date 21 December 2021

Full work available at URL https://arxiv.org/abs/2011.00511

zbMATH Keywords

best match graphsbinary treespolynomial-time algorithmrooted triple consistency

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-resolvable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.

Recommendations

• Best match graphs
• Best match graphs and reconciliation of gene trees with species trees
• Quasi-best match graphs
• Complexity of modification problems for best match graphs
• Least resolved trees for two-colored best match graphs

Cites work

• Best match graphs
• Best match graphs and reconciliation of gene trees with species trees
• Closure operations in phylogenetics
• Complete characterization of incorrect orthology assignments in best match graphs
• Complexity of modification problems for best match graphs
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• Corrigendum to: ``Best match graphs
• Extension operations on sets of leaf-labelled trees
• Fast compatibility testing for rooted phylogenetic trees
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Reconstructing gene trees from Fitch's xenology relation
• Reconstructing minimal rooted trees.
• The matroid structure of representative triple sets and triple-closure computation

Cited in

(9)

• Corrigendum to: ``Best match graphs
• Compatibility of partitions with trees, hierarchies, and split systems
• The structure of 2-colored best match graphs
• Best match graphs
• Complete characterization of incorrect orthology assignments in best match graphs
• Complexity of modification problems for best match graphs
• Quasi-best match graphs
• Least resolved trees for two-colored best match graphs
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees

This page was built for publication: Best match graphs with binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2062000)