Corrigendum to "Best match graphs".

Two errors in the article Best Match Graphs (Geiß et al. in JMB 78: 2015-2057, 2019) are corrected. One concerns the tacit assumption that digraphs are sink-free, which has to be added as an additional precondition in Lemma 9, Lemma 11, Theorem 4. Correspondingly, Algorithm 2 requires that its input is sink-free. The second correction concerns an additional necessary condition in Theorem 9 required to characterize best match graphs. The amended results simplify the construction of least resolved trees for n-cBMGs, i.e., Algorithm 1. All other results remain unchanged and are correct as stated.

From pairs of most similar sequences to phylogenetic best matches.

BACKGROUND: Many of the commonly used methods for orthology detection start from mutually most similar pairs of genes (reciprocal best hits) as an approximation for evolutionary most closely related pairs of genes (reciprocal best matches). This approximation of best matches by best hits becomes exact for ultrametric dissimilarities, i.e., under the Molecular Clock Hypothesis. It fails, however, whenever there are large lineage specific rate variations among paralogous genes. In practice, this introduces a high level of noise into the input data for best-hit-based orthology detection methods. RESULTS: If additive distances between genes are known, then evolutionary most closely related pairs can be identified by considering certain quartets of genes provided that in each quartet the outgroup relative to the remaining three genes is known. A priori knowledge of underlying species phylogeny greatly facilitates the identification of the required outgroup. Although the workflow remains a heuristic since the correct outgroup cannot be determined reliably in all cases, simulations with lineage specific biases and rate asymmetries show that nearly perfect results can be achieved. In a realistic setting, where distances data have to be estimated from sequence data and hence are noisy, it is still possible to obtain highly accurate sets of best matches. CONCLUSION: Improvements of tree-free orthology assessment methods can be expected from a combination of the accurate inference of best matches reported here and recent mathematical advances in the understanding of (reciprocal) best match graphs and orthology relations. AVAILABILITY: Accompanying software is available at https://github.com/david-schaller/AsymmeTree.

Best match graphs.

Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and [Formula: see text] an assignment of leaves of T to species. The best match graph [Formula: see text] is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species [Formula: see text]. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether [Formula: see text] derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains [Formula: see text], which can also be constructed in cubic time.

Understanding the Mechanisms Behind the Response to Environmental Perturbation in Microbial Mats: A Metagenomic-Network Based Approach.

To date, it remains unclear how anthropogenic perturbations influence the dynamics of microbial communities, what general patterns arise in response to disturbance, and whether it is possible to predict them. Here, we suggest the use of microbial mats as a model of study to reveal patterns that can illuminate the ecological processes underlying microbial dynamics in response to stress. We traced the responses to anthropogenic perturbation caused by water depletion in microbial mats from Cuatro Cienegas Basin (CCB), Mexico, by using a time-series spatially resolved analysis in a novel combination of three computational approaches. First, we implemented MEBS (Multi-genomic Entropy-Based Score) to evaluate the dynamics of major biogeochemical cycles across spatio-temporal scales with a single informative value. Second, we used robust Time Series-Ecological Networks (TS-ENs) to evaluate the total percentage of interactions at different taxonomic levels. Lastly, we utilized network motifs to characterize specific interaction patterns. Our results indicate that microbial mats from CCB contain an enormous taxonomic diversity with at least 100 phyla, mainly represented by members of the rare biosphere (RB). Statistical ecological analyses point out a clear involvement of anaerobic guilds related to sulfur and methane cycles during wet versus dry conditions, where we find an increase in fungi, photosynthetic, and halotolerant taxa. TS-ENs indicate that in wet conditions, there was an equilibrium between cooperation and competition (positive and negative relationships, respectively), while under dry conditions there is an over-representation of negative relationships. Furthermore, most of the keystone taxa of the TS-ENs at family level are members of the RB and the microbial mat core highlighting their crucial role within the community. Our results indicate that microbial mats are more robust to perturbation due to redundant functions that are likely shared among community members in the highly connected TS-ENs with density values close to one (≈0.9). Finally, we provide evidence that suggests that a large taxonomic diversity where all community members interact with each other (low modularity), the presence of permanent of low-abundant taxa, and an increase in competition can be potential buffers against environmental disturbance in microbial mats.