| 1. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Clustering systems of phylogenetic networks
- 2023
-
Ingår i: Theory in biosciences. - 1431-7613 .- 1611-7530. ; :142, s. 301-358
-
Tidskriftsartikel (refereegranskat)abstract
- Rooted acyclic graphs appear naturally when the phylogenetic relationship of a set X of taxa involves not only speciations but also recombination, horizontal transfer, or hybridization that cannot be captured by trees. A variety of classes of such networks have been discussed in the literature, including phylogenetic, level-1, tree-child, tree-based, galled tree, regular, or normal networks as models of different types of evolutionary processes. Clusters arise in models of phylogeny as the sets C(v) of descendant taxa of a vertex v. The clustering system CN comprising the clusters of a network N conveys key information on N itself. In the special case of rooted phylogenetic trees, T is uniquely determined by its clustering system CT. Although this is no longer true for networks in general, it is of interest to relate properties of N and CN. Here, we systematically investigate the relationships of several well-studied classes of networks and their clustering systems. The main results are correspondences of classes of networks and clustering systems of the following form: If N is a network of type X, then CN satisfies Y, and conversely if C is a clustering system satisfying Y, then there is network N of type X such that C⊆CN.This, in turn, allows us to investigate the mutual dependencies between the distinct types of networks in much detail.
|
|
| 2. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Injective Split Systems
- 2023
-
Ingår i: Graphs and Combinatorics. - 0911-0119 .- 1435-5914. ; 39:4
-
Tidskriftsartikel (refereegranskat)abstract
- A split system S on a finite set X, |X|≥3, is a set of bipartitions or splits of X which contains all splits of the form {x,X−{x}}, x∈X. To any such split system S we can associate the Buneman graph B(S) which is essentially a median graph with leaf-set X that displays the splits in S. In this paper, we consider properties of injective split systems, that is, split systems S with the property that medB(S)(Y)≠medB(S)(Y′) for any 3-subsets Y,Y′ in X, where medB(S)(Y)med denotes the median in B(S) of the three elements in Y considered as leaves in B(S). In particular, we show that for any set X there always exists an injective split system on X, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph B(S) needs to become in order for a split system S on X to be injective. We do this by introducing a quantity for |X| which we call the injective dimension for |X|, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on X can be represented using Buneman graphs.
|
|
| 3. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Resolving prime modules : The structure of pseudo-cographs and galled-tree explainable graphs
- 2024
-
Ingår i: Discrete Applied Mathematics. - 0166-218X .- 1872-6771. ; 343, s. 25-43
-
Tidskriftsartikel (refereegranskat)abstract
- The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T,t) whose vertices are labeled as “series” (1), “parallel” (0) or “prime”. However, full information of G is provided by its modular decomposition tree (T,t) only, if G is a cograph, i.e., G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y}∈E(G) if and only if the lowest common ancestor lcaT(x,y) of x and y has label “1”. Pseudo-cographs, or, more generally, GaTEx graphs G are graphs that can be explained by labeled galled-trees, i.e., labeled networks (N,t) that are obtained from the modular decomposition tree (T,t) of G by replacing the prime vertices in T by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time.In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set FGT of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GATEX graphs are closely related to many other well-known graph classes such as P4-sparse and P4-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GATEX graph as twin-width at most 1.
|
|
| 4. |
- Schaller, David, et al.
(författare)
-
Best Match Graphs With Binary Trees
- 2023
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1545-5963 .- 1557-9964. ; 20:3, s. 1679-1690
-
Tidskriftsartikel (refereegranskat)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-refinable 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.
|
|
| 5. |
- Schaller, David, et al.
(författare)
-
Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
- 2023
-
Ingår i: SIAM Journal on Discrete Mathematics. - 0895-4801 .- 1095-7146. ; 37:3, s. 2172-2207
-
Tidskriftsartikel (refereegranskat)abstract
- Horizontal gene transfer (HGT) events partition a gene tree T, and thus its leaf set X, into subsets of genes whose evolutionary history is described by speciation and duplication events alone. Two genes thus are xenologs if and only if they belong to two different sets of this partition P. Indirect phylogenetic methods can be used to infer the partition P of X from sequence similarity or evolutionary distances without any a priori knowledge about the underlying tree T. In this contribution, we assume that a partition P of the gene set X and a usually incompletely resolved estimate T of the original gene tree on X are known. We then ask to what extent T and P can be combined to determine the horizontal transfer edges in T and thus the orientation of the HGT events that separate the sets of P. If T and P are compatible, it can be decided for each pair of genes x and y whether there always exists or never exists a horizontal gene transfer in T along the path connecting y and the most recent common ancestor of x and y, and thus a directed edge (x, y) in the so-called Fitch graph of the gene family. We generalize this result to insufficiently resolved gene trees. We show that the classification of a gene pair (x, y) can be computed in constant time after linear-time preprocessing. Using simulated gene family histories, we observe empirically that the vast majority of horizontal transfer edges in the gene tree T can be recovered unambiguously from the knowledge of the partition P. All algorithms developed here are implemented and freely available within the Python package AsymmeTree hosted at https://github.com/david-schaller/AsymmeTree.
|
|
| 6. |
- Schaller, David, et al.
(författare)
-
Relative timing information and orthology in evolutionary scenarios
- 2023
-
Ingår i: Algorithms for Molecular Biology. - 1748-7188. ; 18:1
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph.ResultsHere we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs.
|
|
