A $k$-matching $M$ of a graph $G=(V,E)$ is a subset $Msubseteq E$ such that each connected component in the subgraph $F = (V,M)$ of $G$ is either a single-vertex graph or $k$-regular, i.e., each vertex has degree $k$. In this contribution, we are int
erested in $k$-matchings within the four standard graph products: the Cartesian, strong, direct and lexicographic product. As we shall see, the problem of finding non-empty $k$-matchings ($kgeq 3$) in graph products is NP-complete. Due to the general intractability of this problem, we focus on distinct polynomial-time constructions of $k$-matchings in a graph product $Gstar H$ that are based on $k_G$-matchings $M_G$ and $k_H$-matchings $M_H$ of its factors $G$ and $H$, respectively. In particular, we are interested in properties of the factors that have to be satisfied such that these constructions yield a maximum $k$-matching in the respective products. Such constructions are also called well-behaved and we provide several characterizations for this type of $k$-matchings. Our specific constructions of $k$-matchings in graph products satisfy the property of being weak-homomorphism preserving, i.e., constructed matched edges in the product are never projected to unmatched edges in the factors. This leads to the concept of weak-homomorphism preserving $k$-matchings. Although the specific $k$-matchings constructed here are not always maximum $k$-matchings of the products, they have always maximum size among all weak-homomorphism preserving $k$-matchings. Not all weak-homomorphism preserving $k$-matchings, however, can be constructed in our manner. We will, therefore, determine the size of maximum-sized elements among all weak-homomorphims preserving $k$-matching within the respective graph products, provided that the matchings in the factors satisfy some general assumptions.
While atom tracking with isotope-labeled compounds is an essential and sophisticated wet-lab tool in order to, e.g., illuminate reaction mechanisms, there exists only a limited amount of formal methods to approach the problem. Specifically when large
(bio-)chemical networks are considered where reactions are stereo-specific, rigorous techniques are inevitable. We present an approach using the right Cayley graph of a monoid in order to track atoms concurrently through sequences of reactions and predict their potential location in product molecules. This can not only be used to systematically build hypothesis or reject reaction mechanisms (we will use the ANRORC mechanism Addition of the Nucleophile, Ring Opening, and Ring Closure as an example), but also to infer naturally occurring subsystems of (bio-)chemical systems. Our results include the analysis of the carbon traces within the TCA cycle and infer subsystems based on projections of the right Cayley graph onto a set of relevant atoms.
A rooted tree $T$ with vertex labels $t(v)$ and set-valued edge labels $lambda(e)$ defines maps $delta$ and $varepsilon$ on the pairs of leaves of $T$ by setting $delta(x,y)=q$ if the last common ancestor $text{lca}(x,y)$ of $x$ and $y$ is labeled $q
$, and $min varepsilon(x,y)$ if $minlambda(e)$ for at least one edge $e$ along the path from $text{lca}(x,y)$ to $y$. We show that a pair of maps $(delta,varepsilon)$ derives from a tree $(T,t,lambda)$ if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree $(T_{delta},t_{delta})$ that explains $delta$ and the (unique) least resolved edge labeled tree $(T_{varepsilon},lambda_{varepsilon})$ that explains $varepsilon$ (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.
The problem of finding a common refinement of a set of rooted trees with common leaf set $L$ appears naturally in mathematical phylogenetics whenever poorly resolved information on the same taxa from different sources is to be reconciled. This consti
tutes a special case of the well-studied supertree problem, where the leaf sets of the input trees may differ. Algorithms that solve the rooted tree compatibility problem are of course applicable to this special case. However, they require sophisticated auxiliary data structures and have a running time of at least $O(k|L|log^2(k|L|))$ for $k$ input trees. Here, we show that the problem can be solved in $O(k|L|)$ time using a simple bottom-up algorithm called LinCR. An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda.
The question whether a partition $mathcal{P}$ and a hierarchy $mathcal{H}$ or a tree-like split system $mathfrak{S}$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether th
e sets of $mathcal{P}$ coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $mathcal{H}$ or $mathfrak{S}$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $mathcal{P}$ are compatible. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (sets of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a set of partitions is considered instead of a single partition. We finally explore the close relationship of the concept of compatibility and so-called Fitch maps.
The modular decomposition of a symmetric map $deltacolon Xtimes X to Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $delta$ in
labeled trees. A map $delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $delta(x,y)=t(mathrm{lca}(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by extended hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $delta$. We argue that the resulting tree-like median graphs may be of use in phylogenetics as a model of evolutionary relationships.
Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved tr
ees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.
Best match graphs (BMGs) are a class of colored digraphs that naturally appear in mathematical phylogenetics and can be approximated with the help of similarity measures between gene sequences, albeit not without errors. The corresponding graph editi
ng problem can be used as a means of error correction. Since the arc set modification problems for BMGs are NP-complete, efficient heuristics are needed if BMGs are to be used for the practical analysis of biological sequence data. Since BMGs have a characterization in terms of consistency of a certain set of rooted triples, we consider heuristics that operate on triple sets. As an alternative, we show that there is a close connection to a set partitioning problem that leads to a class of top-down recursive algorithms that are similar to Ahos supertree algorithm and give rise to BMG editing algorithms that are consistent in the sense that they leave BMGs invariant. Extensive benchmarking shows that community detection algorithms for the partitioning steps perform best for BMG editing.
2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive graphs that appears in phylogenetic combinatorics. There, 2-BMGs describe evolutionarily most closely related genes between a pair of species. They are explained by a uni
que least resolved tree (LRT). Introducing the concept of support vertices we derive an $O(|V|+|E|log^2|V|)$-time algorithm to recognize 2-BMGs and to construct its LRT. The approach can be extended to also recognize binary-explainable 2-BMGs with the same complexity. An empirical comparison emphasizes the efficiency of the new algorithm.
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.
