Indirect identification of horizontal gene transfer
From MaRDI portal
Abstract: Several implicit methods to infer Horizontal Gene Transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside. This situation defines the edge set of a graph, the later-divergence-time (LDT) graph, whose vertices correspond to genes colored by their species. We investigate these graphs in the setting of relaxed scenarios, i.e., evolutionary scenarios that encompass all commonly used variants of duplication-transfer-loss scenarios in the literature. We characterize LDT graphs as a subclass of properly vertex-colored cographs, and provide a polynomial-time recognition algorithm as well as an algorithm to construct a relaxed scenario that explains a given LDT. An edge in an LDT graph implies that the two corresponding genes are separated by at least one HGT event. The converse is not true, however. We show that the complete xenology relation is described by an rs-Fitch graph, i.e., a complete multipartite graph satisfying constraints on the vertex coloring. This class of vertex-colored graphs is also recognizable in polynomial time. We finally address the question "how much information about all HGT events is contained in LDT graphs" with the help of simulations of evolutionary scenarios with a wide range of duplication, loss, and HGT events. In particular, we show that a simple greedy graph editing scheme can be used to efficiently detect HGT events that are implicitly contained in LDT graphs.
Recommendations
Cites work
- A Linear Recognition Algorithm for Cographs
- A short note on undirected Fitch graphs
- Alternative characterizations of Fitch's xenology relation
- Best match graphs
- Best match graphs and reconciliation of gene trees with species trees
- Cluster graph modification problems
- Cograph editing: Merging modules is equivalent to editing P₄s
- Complement reducible graphs
- Complete characterization of incorrect orthology assignments in best match graphs
- Complexity of modification problems for best match graphs
- Complexity of modification problems for reciprocal best match graphs
- Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
- Corrigendum to: ``Best match graphs
- DLS-trees: a model of evolutionary scenarios
- Extension operations on sets of leaf-labelled trees
- Forbidden time travel: characterization of time-consistent tree reconciliation maps
- Gene tree reconciliation including transfers with replacement is NP-hard and FPT
- H-trees: a model of evolutionary scenarios with horizontal gene transfer
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Inferring evolutionary scenarios in the duplication, loss and horizontal gene transfer model
- Jungles: A new solution to the host/parasite phylogeny reconciliation problem
- Near-complete multipartite graphs and forbidden induced subgraphs
- NP-completeness results for edge modification problems
- ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
- On the complexity of inferring rooted evolutinary trees
- Orthology relations, symbolic ultrametrics, and cographs
- Reciprocal best match graphs
- Reconstructing gene trees from Fitch's xenology relation
- Rooted maximum agreement supertrees
- The cluster deletion problem for cographs
- The complexity of inferring a minimally resolved phylogenetic supertree
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
Cited in
(12)- 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
- On partial gene transfer and its impact on gene tree reconstruction
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Alternative characterizations of Fitch's xenology relation
- How to identify laterally transferred genes?
- Algorithms for detecting complete and partial horizontal gene transfers: theory and a practice
- Detecting locus acquisition events in gene trees
- Towards identifying lateral gene transfer events
- Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
- Predicting horizontal gene transfers with perfect transfer networks
- The path-label reconciliation (PLR) dissimilarity measure for gene trees
This page was built for publication: Indirect identification of horizontal gene transfer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040274)
