Complete characterization of incorrect orthology assignments in best match graphs

DOI10.1007/S00285-021-01564-8MaRDI QIDQ2659043zbMATH OpenOpenAlexWikidataFDO

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

Publication date 25 March 2021

Published in Journal of Mathematical Biology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

best matchescographcolored graphsorthology detectionpolynomial-time algorithmtree reconciliationunambiguous orthologs

Mathematics Subject Classification ID

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

Abstract: Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify all u-fp orthology assignments in a BMG. Simulations show that at least $75\mathrm{\%}$ of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs and not on any a priori knowledge about underlying gene or species trees.

Recommendations

• Best match graphs and reconciliation of gene trees with species trees
• Best match graphs
• Reciprocal best match graphs
• Best match graphs with binary trees
• OMG! Orthologs in multiple genomes -- competing graph-theoretical formulations

Cites work

• Best match graphs
• Best match graphs and reconciliation of gene trees with species trees
• Cograph editing: Merging modules is equivalent to editing P₄s
• Complement reducible graphs
• Complexity and parameterized algorithms for cograph editing
• Complexity of modification problems for reciprocal best match graphs
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
• DLS-trees: a model of evolutionary scenarios
• Extension operations on sets of leaf-labelled trees
• Faster algorithms for cograph edge modification problems
• Forbidden time travel: characterization of time-consistent tree reconciliation maps
• scientific article; zbMATH DE number 1113970 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• On the Generalized "Birth-and-Death" Process
• Orthology relations, symbolic ultrametrics, and cographs
• Reciprocal best match graphs
• Reconciling Gene Trees with Apparent Polytomies
• Reconstructing minimal rooted trees.
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Topics in Intersection Graph Theory

Cited in

(10)

• Corrigendum to: ``Best match graphs
• Indirect identification of horizontal gene transfer
• Best match graphs with binary trees
• The structure of 2-colored best match graphs
• Complexity of modification problems for best match graphs
• Quasi-best match graphs
• A Parsimony Approach to Genome-Wide Ortholog Assignment
• Least resolved trees for two-colored best match graphs
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
• Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints

Describes a project that uses

Uses Software

• OMA
• eggNOG
• Proteinortho

This page was built for publication: Complete characterization of incorrect orthology assignments in best match graphs

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