Reconstructing gene trees from Fitch's xenology relation

DOI10.1007/S00285-018-1260-8MaRDI QIDQ1789081zbMATH OpenOpenAlexWikidataFDO

Authors Manuela Geiß, John Anders, Peter F. Stadler, Nicolas Wieseke, Marc Hellmuth

Publication date 9 October 2018

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

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

zbMATH Keywords

di-cographFitch xenologyfixed parameter tractableforbidden induced subgraphsheritable graph propertyinformative triple setsleast-resolved treephylogenetic treerecognition algorithmrooted triples

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: $y$ is xenologous to $x$ if $y$ has been horizontally transferred at least once since it diverged from the least common ancestor of $x$ and $y$. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations.

Recommendations

• Alternative characterizations of Fitch's xenology relation
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Indirect identification of horizontal gene transfer
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees

Cites work

• A short note on undirected Fitch graphs
• Closure operations in phylogenetics
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
• Extension operations on sets of leaf-labelled trees
• Fast compatibility testing for rooted phylogenetic trees
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Forbidden time travel: characterization of time-consistent tree reconciliation maps
• Fully dynamic recognition algorithm and certificate for directed cographs
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Introduction to algorithms.
• Linear-time modular decomposition of directed graphs
• Node-and edge-deletion NP-complete problems
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Orthology relation and gene tree correction: complexity results
• Orthology relations, symbolic ultrametrics, and cographs
• Partial homology relations -- satisfiability in terms of di-cographs
• Phylogeny. Discrete and random processes in evolution
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Primitivity is hereditary for 2-structures
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Rooted maximum agreement supertrees
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• The matroid structure of representative triple sets and triple-closure computation
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(21)

• The matroid structure of representative triple sets and triple-closure computation
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Indirect identification of horizontal gene transfer
• Best match graphs with binary trees
• From modular decomposition trees to rooted median graphs
• Compatibility of partitions with trees, hierarchies, and split systems
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Exact-2-relation graphs
• Reciprocal best match graphs
• Best match graphs and reconciliation of gene trees with species trees
• Alternative characterizations of Fitch's xenology relation
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
• Best match graphs
• Generalized Fitch graphs. III: Symmetrized Fitch maps and sets of symmetric binary relations that are explained by unrooted edge-labeled trees
• Cograph editing: Merging modules is equivalent to editing P₄s
• A short note on undirected Fitch graphs
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Fitch graph completion
• Partial Fitch graphs: characterization, satisfiability and complexity

This page was built for publication: Reconstructing gene trees from Fitch's xenology relation

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