Search

In comparison to phylogenetic trees, phylogenetic networks are more suitable to represent complex evolutionary histories of species whose past includes reticulation such as hybridisation or lateral gene transfer. However, the reconstruction of phylogenetic networks remains challenging and computationally expensive due to their intricate structural properties. For example, the small parsimony problem that is solvable in polynomial time for phylogenetic trees, becomes NP-hard on phylogenetic networks under softwired and parental parsimony, even for a single binary character and structurally constrained networks. To calculate the parsimony score of a phylogenetic network N, these two parsimony notions consider different exponential-size sets of phylogenetic trees that can be extracted from N and infer the minimum parsimony score over all trees in the set. In this paper, we ask: What is the maximum difference between the parsimony score of any phylogenetic tree that is contained in the set of considered trees and a phylogenetic tree whose parsimony score equates to the parsimony score of N? Given a gap-free sequence alignment of multi-state characters and a rooted binary level-k phylogenetic network, we use the novel concept of an informative blob to show that this difference is bounded by k + 1 times the softwired parsimony score of N. In particular, the difference is independent of the alignment length and the number of character states. We show that an analogous bound can be obtained for the softwired parsimony score of semi-directed networks, while under parental parsimony on the other hand, such a bound does not hold. [ABSTRACT FROM AUTHOR]

Phylogenetic networks represent evolutionary histories of sets of taxa where horizontal evolution or hybridization has occurred. Placing a Markov model of evolution on a phylogenetic network gives a model that is particularly amenable to algebraic study by representing it as an algebraic variety. In this paper, we give a formula for the dimension of the variety corresponding to a triangle-free level-1 phylogenetic network under a group-based evolutionary model. On our way to this, we give a dimension formula for codimension zero toric fiber products. We conclude by illustrating applications to identifiability. [ABSTRACT FROM AUTHOR]

Accurately reconstructing the reticulate histories of polyploids remains a central challenge for understanding plant evolution. Although phylogenetic networks can provide insights into relationships among polyploid lineages, inferring networks may be hindered by the complexities of homology determination in polyploid taxa. We use simulations to show that phasing alleles from allopolyploid individuals can improve phylogenetic network inference under the multispecies coalescent by obtaining the true network with fewer loci compared with haplotype consensus sequences or sequences with heterozygous bases represented as ambiguity codes. Phased allelic data can also improve divergence time estimates for networks, which is helpful for evaluating allopolyploid speciation hypotheses and proposing mechanisms of speciation. To achieve these outcomes in empirical data, we present a novel pipeline that leverages a recently developed phasing algorithm to reliably phase alleles from polyploids. This pipeline is especially appropriate for target enrichment data, where the depth of coverage is typically high enough to phase entire loci. We provide an empirical example in the North American Dryopteris fern complex that demonstrates insights from phased data as well as the challenges of network inference. We establish that our pipeline (PATÉ: Phased Alleles from Target Enrichment data) is capable of recovering a high proportion of phased loci from both diploids and polyploids. These data may improve network estimates compared with using haplotype consensus assemblies by accurately inferring the direction of gene flow, but statistical nonidentifiability of phylogenetic networks poses a barrier to inferring the evolutionary history of reticulate complexes. [ABSTRACT FROM AUTHOR]

SUMMARY: Specific ecological conditions in the high mountain environment exert a selective pressure that often leads to convergent trait evolution. Reticulations induced by incomplete lineage sorting and introgression can lead to discordant trait patterns among gene and species trees (hemiplasy/xenoplasy), providing a false illusion that the traits under study are homoplastic. Using phylogenetic species networks, we explored the effect of gene exchange on trait evolution in Soldanella, a genus profoundly influenced by historical introgression. At least three features evolved independently multiple times: the single‐flowered dwarf phenotype, dysploid cytotype, and ecological generalism. The present analyses also indicated that the recurring occurrence of stoloniferous growth might have been prompted by an introgression event between an ancestral lineage and a still extant species, although its emergence via convergent evolution cannot be completely ruled out. Phylogenetic regression suggested that the independent evolution of larger genomes in snowbells is most likely a result of the interplay between hybridization events of dysploid and euploid taxa and hostile environments at the range margins of the genus. The emergence of key intrinsic and extrinsic traits in snowbells has been significantly impacted not only by convergent evolution but also by historical and recent introgression events. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are increasingly being considered better suited to represent the complexity of the evolutionary relationships between species. One class of phylogenetic networks that have received a lot of attention recently is the class of orchard networks, which is composed of networks that can be reduced to a single leaf using cherry reductions. Cherry reductions, also called cherry-picking operations, remove either a leaf of a simple cherry (sibling leaves sharing a parent) or a reticulate edge of a reticulate cherry (two leaves whose parents are connected by a reticulate edge). In this article, we present a fixed-parameter tractable algorithm to solve the problem of finding a maximum agreement cherry-reduced subnetwork (MACRS) between two rooted binary level-1 networks. This is the first exact algorithm proposed to solve the MACRS problem. As proven in an earlier work, there is a direct relationship between finding an MACRS and calculating a distance based on cherry operations. As a result, the proposed algorithm also provides a distance that can be used for the comparison of level-1 networks. [ABSTRACT FROM AUTHOR]

Decades of empirical research have revealed how the geological history of our planet shaped plant evolution by establishing well‐known patterns (e.g., how mountain uplift resulted in high rates of diversification and replicate radiations in montane plant taxa). This follows a traditional approach where botanical data are interpreted in light of geological events. In this synthesis, I instead describe how by integrating natural history, phylogenetics, and population genetics, botanical research can be applied alongside geology and paleontology to inform our understanding of past geological and climatic processes. This conceptual shift aligns with the goals of the emerging field of geogenomics. In the neotropics, plant geogenomics is a powerful tool for the reciprocal exploration of two long standing questions in biology and geology: how the dynamic landscape of the region came to be and how it shaped the evolution of the richest flora. Current challenges that are specific to analytical approaches for plant geogenomics are discussed. I describe the scale at which various geological questions can be addressed from biological data and what makes some groups of plants excellent model systems for geogenomics research. Although plant geogenomics is discussed with reference to the neotropics, the recommendations given here for approaches to plant geogenomics can and should be expanded to exploring long‐standing questions on how the earth evolved with the use of plant DNA. [ABSTRACT FROM AUTHOR]

Semi-directed phylogenetic networks have recently emerged as a class of phylogenetic networks sitting between rooted (directed) and unrooted (undirected) phylogenetic networks as they contain both directed as well as undirected edges. While various spaces of rooted phylogenetic networks and unrooted phylogenetic networks have been analyzed in recent years and several rearrangement moves to traverse these spaces have been introduced, little is known about spaces of semi-directed phylogenetic networks. Here, we propose a simple rearrangement move for semi-directed phylogenetic networks, called cut edge transfer (CET), and show that the space of semi-directed level-1 networks with precisely k reticulations is connected under CET. This level-1 space is currently the predominantly used search space for most algorithms that reconstruct semi-directed phylogenetic networks. Our results imply that every semi-directed level-1 network with a fixed number of reticulations and leaf set can be reached from any other such network by a sequence of CETs. By introducing two additional moves, R + and R - , that allow for the addition and deletion, respectively, of a reticulation, we then establish connectedness for the space of all semi-directed level-1 networks on a fixed leaf set. As a byproduct of our results for semi-directed phylogenetic networks, we also show that the space of rooted level-1 networks with a fixed number of reticulations and leaf set is connected under CET, when translated into the rooted setting. [ABSTRACT FROM AUTHOR]

Abstract Gene flow is increasingly recognized as an important macroevolutionary process. The many mechanisms that contribute to gene flow (e.g. introgression, hybridization, lateral gene transfer) uniquely affect the diversification of dynamics of species, making it important to be able to account for these idiosyncrasies when constructing phylogenetic models. Existing phylogenetic‐network simulators for macroevolution are limited in the ways they model gene flow. We present SiPhyNetwork, an R package for simulating phylogenetic networks under a birth–death‐hybridization process. Our package unifies the existing birth–death‐hybridization models while also extending the toolkit for modelling gene flow. This tool can create patterns of reticulation such as hybridization, lateral gene transfer, and introgression. Specifically, we model different reticulate events by allowing events to either add, remove or keep constant the number of lineages. Additionally, we allow reticulation events to be trait dependent, creating the ability to model the expanse of isolating mechanisms that prevent gene flow. This tool makes it possible for researchers to model many of the complex biological factors associated with gene flow in a phylogenetic context.

Abstract Neighbor‐net is a widely used network reconstructing method that approximates pairwise distances between taxa by a circular phylogenetic network. We present Lpnet, a variant of Neighbor‐net. We first apply standard methods to construct a binary phylogenetic tree and then use integer linear programming to compute an optimal circular ordering that agrees with all tree splits. This approach achieves an improved approximation of the input distance for the clear majority of experiments that we have run for simulated and real data. We release an implementation in R that can handle up to 94 taxa and usually needs about 1 min on a standard computer for 80 taxa. For larger taxa sets, we include a top‐down heuristic which also tends to perform better than Neighbor‐net. Our Lpnet provides an alternative to Neighbor‐net and performs better in most cases. We anticipate Lpent will be useful to generate phylogenetic hypotheses.

Abstract Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees. Results Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it. Conclusion The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks.

NeighborNet constructs phylogenetic networks to visualize distance data. It is a popular method used in a wide range of applications. While several studies have investigated its mathematical features, here we focus on computational aspects. The algorithm operates in three steps. We present a new simplified formulation of the first step, which aims at computing a circular ordering. We provide the first technical description of the second step, the estimation of split weights. We review the third step by constructing and drawing the network. Finally, we discuss how the networks might best be interpreted, review related approaches, and present some open questions.

Gene flow is increasingly recognized as an important macroevolutionary process. The many mechanisms that contribute to gene flow (e.g. introgression, hybridization, lateral gene transfer) uniquely affect the diversification of dynamics of species, making it important to be able to account for these idiosyncrasies when constructing phylogenetic models. Existing phylogenetic‐network simulators for macroevolution are limited in the ways they model gene flow.We present SiPhyNetwork, an R package for simulating phylogenetic networks under a birth–death‐hybridization process.Our package unifies the existing birth–death‐hybridization models while also extending the toolkit for modelling gene flow. This tool can create patterns of reticulation such as hybridization, lateral gene transfer, and introgression.Specifically, we model different reticulate events by allowing events to either add, remove or keep constant the number of lineages. Additionally, we allow reticulation events to be trait dependent, creating the ability to model the expanse of isolating mechanisms that prevent gene flow. This tool makes it possible for researchers to model many of the complex biological factors associated with gene flow in a phylogenetic context. [ABSTRACT FROM AUTHOR]

Likelihood-based tests of phylogenetic trees are a foundation of modern systematics. Over the past decade, an enormous wealth and diversity of model-based approaches have been developed for phylogenetic inference of both gene trees and species trees. However, while many techniques exist for conducting formal likelihood-based tests of gene trees, such frameworks are comparatively underdeveloped and underutilized for testing species tree hypotheses. To date, widely used tests of tree topology are designed to assess the fit of classical models of molecular sequence data and individual gene trees and thus are not readily applicable to the problem of species tree inference. To address this issue, we derive several analogous likelihood-based approaches for testing topologies using modern species tree models and heuristic algorithms that use gene tree topologies as input for maximum likelihood estimation under the multispecies coalescent. For the purpose of comparing support for species trees, these tests leverage the statistical procedures of their original gene tree-based counterparts that have an extended history for testing phylogenetic hypotheses at a single locus. We discuss and demonstrate a number of applications, limitations, and important considerations of these tests using simulated and empirical phylogenomic data sets that include both bifurcating topologies and reticulate network models of species relationships. Finally, we introduce the open-source R package SpeciesTopoTestR (Species Topo logy Test s in R) that includes a suite of functions for conducting formal likelihood-based tests of species topologies given a set of input gene tree topologies. [ABSTRACT FROM AUTHOR]

Neighbor‐net is a widely used network reconstructing method that approximates pairwise distances between taxa by a circular phylogenetic network.We present Lpnet, a variant of Neighbor‐net. We first apply standard methods to construct a binary phylogenetic tree and then use integer linear programming to compute an optimal circular ordering that agrees with all tree splits.This approach achieves an improved approximation of the input distance for the clear majority of experiments that we have run for simulated and real data. We release an implementation in R that can handle up to 94 taxa and usually needs about 1 min on a standard computer for 80 taxa. For larger taxa sets, we include a top‐down heuristic which also tends to perform better than Neighbor‐net.Our Lpnet provides an alternative to Neighbor‐net and performs better in most cases. We anticipate Lpent will be useful to generate phylogenetic hypotheses. [ABSTRACT FROM AUTHOR]

Abstract Background Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the Small Parsimony problem: given a tree T and an assignment of character-states to its leaves, assign states to the internal nodes of T such as to minimize the parsimony score, that is, the number of edges of T connecting nodes with different states. While this problem is polynomial-time solvable on trees, the matter is more complicated if T contains reticulate events such as hybridizations or recombinations, i.e. when T is a network. Indeed, three different versions of the parsimony score on networks have been proposed and each of them is NP-hard to decide. Existing parameterized algorithms focus on combining the number c of possible character-states with the number of reticulate events (per biconnected component). Results We consider the parameter treewidth t of the underlying undirected graph of the input network, presenting dynamic programming algorithms for (slight generalizations of) all three versions of the parsimony problem on size-n networks running in times $$c^t {n^{O(1)}}$$ c t n O ( 1 ) , $$(3c)^t {n^{O(1)}}$$ ( 3 c ) t n O ( 1 ) , and $$6^{tc}n^{O(1)}$$ 6 tc n O ( 1 ) , respectively. Our algorithms use a formulation of the treewidth that may facilitate formalizing treewidth-based dynamic programming algorithms on phylogenetic networks for other problems. Conclusions Our algorithms allow the computation of the three popular parsimony scores, modeling the evolutionary development of a (multistate) character on a given phylogenetic network of low treewidth. Our results subsume and improve previously known algorithm for all three variants. While our results rely on being given a “good” tree-decomposition of the input, encouraging theoretical results as well as practical implementations producing them are publicly available. We present a reformulation of tree decompositions in terms of “agreeing trees” on the same set of nodes. As this formulation may come more natural to researchers and engineers developing algorithms for phylogenetic networks, we hope to render exploiting the input network’s treewidth as parameter more accessible to this audience.

Objective: In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees. Results: Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it. Conclusion: The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks. [ABSTRACT FROM AUTHOR]

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 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 lca T (x , y) of x and y has label "1". This information, however, gets lost whenever (T , t) contains vertices with label "prime". In this contribution, we aim at replacing "prime" vertices in (T , t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N , t). We characterize graphs that can be explained by such level-1 networks (N , t) , which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules "induce" polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes. In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N , t) , i.e., (N , t) contains exactly one cycle C that is rooted at the root ρ N of N and where ρ N has exactly two children while every vertex distinct from ρ N has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N , t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that can be explained by labeled level-1 networks, namely prime polar-cats. Moreover, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph. In addition, we provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them. [ABSTRACT FROM AUTHOR]

The Arthrodermataceae, or dermatophytes, are a major family in the Onygenales and important from a public health safety perspective. Here, based on sequenced and downloaded from GenBank sequences, the evolutionary relationships of Arthrodermataceae were comprehensively studied via phylogenetic reconstruction, divergence time estimation, phylogenetic split network, and phylogeography analysis. These results showed the clades Ctenomyces, Epidermophyton, Guarromyces, Lophophyton, Microsporum, Paraphyton, and Trichophyton were all monophyletic groups, whereas Arthroderma and Nannizzia were polyphyletic. Among them, Arthroderma includes at least four different clades, Arthroderma I, III and IV are new clades in Arthrodermataceae. Nannizzia contains at least two different clades, Nannizzia I and Nannizzia II, but Nannizzia II was a new clade in Arthrodermataceae. The unclassified group, distributed in Japan and India, was incorrectly identified; it should be a new clade in Arthrodermataceae. The phylogenetic split network based on the ITS sequences provided strong support for the true relationships among the lineages in the reconstructed phylogenetic tree. A haplotype phylogenetic network based on the ITS sequences was used to visualize species evolution and geographic lineages relationships in all genera except Trichophyton. The new framework provided here for the phylogeny and taxonomy of Arthrodermataceae will facilitate the rapid identification of species in the family, which should useful for evaluating the results of preventive measures and interventions, as well as for conducting epidemiological studies. [ABSTRACT FROM AUTHOR]

[Display omitted] • Sympatric yellowish and blackish morphs of Zodarion nitidum are non-sister species. • They display strong genomic but little mitochondrial differentiation. • Ancient and modest hybridization led to complete mitochondrial replacement. • Nuclear and mitochondrial molecular clocks dated the event at ∼320,000 years ago. • Phylogenetic networks, key to determine the direction and magnitude of gene flow. Disentangling the genomic intricacies underlying speciation and the causes of discordance between sources of evidence can offer remarkable insights into evolutionary dynamics. The ant-eating spider Zodarion nitidum , found across the Middle East and Egypt, displays yellowish and blackish morphs that co-occur sympatrically. These morphs additionally differ in behavioral and physiological features and show complete pre-mating reproductive isolation. In contrast, they possess similar sexual features and lack distinct differences in their mitochondrial DNA. We analyzed both Z. nitidum morphs and outgroups using genome-wide and additional mitochondrial DNA data. The genomic evidence indicated that Yellow and Black are reciprocally independent lineages without signs of recent admixture. Interestingly, the sister group of Yellow is not Black but Z. luctuosum , a morphologically distinct species. Genomic gene flow analyses pinpointed an asymmetric nuclear introgression event, with Yellow contributing nearly 5 % of its genome to Black roughly 320,000 years ago, intriguingly aligning with the independently estimated origin of the mitochondrial DNA of Black. We conclude that the blackish and yellowish morphs of Z. nitidum are long-diverged distinct species, and that the ancient and modest genomic introgression event registered resulted in a complete mitochondrial takeover of Black by Yellow. This investigation underscores the profound long-term effects that even modest hybridization events can have on the genome of organisms. It also exemplifies the utility of phylogenetic networks for estimating historical events and how integrating independent lines of evidence can increase the reliability of such estimations. [ABSTRACT FROM AUTHOR]

[Display omitted] • Gadopsis spp. are distributed in SE Australia and are of conservation concern. • Previous molecular studies with different data types support up to seven species. • We generate a geographically and phylogenetically representative SNP dataset. • We identify seven species of Blackfishes and the ancient hybrid origin of 'SBA' • Range-wide population genetic structure of 'NMD' and 'SBA' is characterized. Gadopsis (Percichthyidae) is a freshwater genus distributed in south-eastern Australia, including Tasmania, and comprises two recognized species. Previous molecular phylogenetic investigations of the genus, mostly conducted in the pre-genomics era and reflecting a range of geographic and molecular sampling intensities, have supported the recognition of up to seven candidate species. Here we analyze a genome-wide SNP dataset that provides comprehensive geographic and genomic coverage of Gadopsis to produce a robust hypothesis of species boundaries and evolutionary relationships. We then leverage the SNP dataset to characterize relationships within candidate species that lack clear intraspecific phylogenetic relationships. We find further support for the seven previously identified candidate species of Gadopsis and evidence that the Bass Strait centered candidate species (SBA) originated from ancient hybridization. The SNP dataset permits a high degree of intraspecific resolution, providing improvements over previous studies, with numerous candidate species showing intraspecific divisions in phylogenetic analysis. Further population genetic analysis of the Murray-Darling candidate species (NMD) and SBA finds support for K = 6 and K = 7 genetic clusters, respectively. The SNP data generated for this study have diverse applications in natural resource management for these fishes of conservation concern. [ABSTRACT FROM AUTHOR]

Tree-child networks, one of the prominent network classes in phylogenetics, have been introduced for the purpose of modeling reticulate evolution. Recently, the first author together with Gittenberger and Mansouri (2019) showed that the number TC ℓ , k of tree-child networks with ℓ leaves and k reticulation vertices has the first-order asymptotics TC ℓ , k ∼ c k 2 e ℓ ℓ ℓ + 2 k − 1 , (ℓ → ∞). Moreover, they also computed c k for k = 1 , 2 , and 3. In this short note, we give a second approach to the above result which is based on a recent (algorithmic) approach for the counting of tree-child networks due to Cardona and Zhang (2020). This second approach is also capable of giving a simple, closed-form expression for c k , namely, c k = 2 k − 1 2 / k ! for all k ≥ 0. [ABSTRACT FROM AUTHOR]

The mathematical analysis of random phylogenetic networks via analytic and algorithmic methods has received increasing attention in the past years. In the present work we introduce branching process methods to their study. This approach appears to be new in this context. Our main results focus on random level‐k networks with n labeled leaves. Although the number of reticulation vertices in such networks is typically linear in n, we prove that their asymptotic global and local shape is tree‐like in a well‐defined sense. We show that the depth process of vertices in a large network converges towards a Brownian excursion after rescaling by n−1/2. We also establish Benjamini–Schramm convergence of large random level‐k networks towards a novel random infinite network. [ABSTRACT FROM AUTHOR]

Background: Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the Small Parsimony problem: given a tree T and an assignment of character-states to its leaves, assign states to the internal nodes of T such as to minimize the parsimony score, that is, the number of edges of T connecting nodes with different states. While this problem is polynomial-time solvable on trees, the matter is more complicated if T contains reticulate events such as hybridizations or recombinations, i.e. when T is a network. Indeed, three different versions of the parsimony score on networks have been proposed and each of them is NP-hard to decide. Existing parameterized algorithms focus on combining the number c of possible character-states with the number of reticulate events (per biconnected component). Results: We consider the parameter treewidth t of the underlying undirected graph of the input network, presenting dynamic programming algorithms for (slight generalizations of) all three versions of the parsimony problem on size-n networks running in times c t n O (1) , (3 c) t n O (1) , and 6 tc n O (1) , respectively. Our algorithms use a formulation of the treewidth that may facilitate formalizing treewidth-based dynamic programming algorithms on phylogenetic networks for other problems. Conclusions: Our algorithms allow the computation of the three popular parsimony scores, modeling the evolutionary development of a (multistate) character on a given phylogenetic network of low treewidth. Our results subsume and improve previously known algorithm for all three variants. While our results rely on being given a "good" tree-decomposition of the input, encouraging theoretical results as well as practical implementations producing them are publicly available. We present a reformulation of tree decompositions in terms of "agreeing trees" on the same set of nodes. As this formulation may come more natural to researchers and engineers developing algorithms for phylogenetic networks, we hope to render exploiting the input network's treewidth as parameter more accessible to this audience. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are used in biology to represent evolutionary histories. The class of orchard phylogenetic networks was recently introduced for their computational benefits, without any biological justification. Here, we show that orchard networks can be interpreted as trees with additional horizontal arcs. Therefore, they are closely related to tree-based networks, where the difference is that in tree-based networks the additional arcs do not need to be horizontal. Then, we use this new characterization to show that the space of orchard networks on n leaves with k reticulations is connected under the rNNI rearrangement move with diameter O (k n + n log (n)) . [ABSTRACT FROM AUTHOR]

Reticulation between incipient lineages is a common feature of diversification. We examine these phenomena in the Pisgah clade of Desmognathus salamanders from the southern Appalachian Mountains of the eastern United States. The group contains four to seven species exhibiting two discrete phenotypes, aquatic "shovel-nosed" and semi-aquatic "black-bellied" forms. These ecomorphologies are ancient and have apparently been transmitted repeatedly between lineages through introgression. Geographically proximate populations of both phenotypes exhibit admixture, and at least two black-bellied lineages have been produced via reticulations between shovel-nosed parentals, suggesting potential hybrid speciation dynamics. However, computational constraints currently limit our ability to reconstruct network radiations from gene-tree data. Available methods are limited to level-1 networks wherein reticulations do not share edges, and higher-level networks may be non-identifiable in many cases. We present a heuristic approach to recover information from higher-level networks across a range of potentially identifiable empirical scenarios, supported by theory and simulation. When extrinsic information indicates the location and direction of reticulations, our method can successfully estimate a reduced possible set of non-level-1 networks. Phylogenomic data support a single backbone topology with up to five overlapping hybrid edges in the Pisgah clade. These results suggest an unusual mechanism of ecomorphological hybrid speciation, wherein a binary threshold trait causes some hybrid populations to shift between microhabitat niches, promoting ecological divergence between sympatric hybrids and parentals. This contrasts with other well-known systems in which hybrids exhibit intermediate, novel, or transgressive phenotypes. The genetic basis of these phenotypes is unclear and further data are needed to clarify the evolutionary basis of morphological changes with ecological consequences., (© The Author(s) 2024. Published by Oxford University Press, on behalf of the Society of Systematic Biologists. All rights reserved. For commercial re-use, please contact reprints@oup.com for reprints and translation rights for reprints. All other permissions can be obtained through our RightsLink service via the Permissions link on the article page on our site—for further information please contact journals.permissions@oup.com.)

We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O (5 k · n · m) . We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d and at most k reticulations in O ((8 k) d 5 k · k · n · m) time. Lastly, we introduce an O (6 k k ! · k · n 2) time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance. [ABSTRACT FROM AUTHOR]

Tree‐child networks are a class of directed acyclic graphs that have recently risen to prominence in phylogenetics. Although these networks have numerous, attractive mathematical properties, many combinatorial questions concerning them remain intractable. We show that endowing tree‐child networks with a biologically relevant ranking structure yields mathematically tractable objects, which we term ranked tree‐child networks (RTCNs). We derive explicit enumerative formulas and explain how to sample RTCNS uniformly at random. We study the properties of uniform RTCNs, including: lengths of random walks between root and leaves; distribution of number of cherries in the network; and sampling RTCNs conditional on displaying a given tree. We also formulate a conjecture regarding the scaling limit of the process counting the number of lineages in the ancestry of a leaf. The main idea in this paper, namely using ranking as a way to achieve combinatorial tractability, may also extend to other classes of networks. [ABSTRACT FROM AUTHOR]

We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O ((8 k) k poly (n , t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods. [ABSTRACT FROM AUTHOR]

• The invasive ascomycete kills common ash throughout Europe (ash dieback disease). • Genome-wide sequencing revealed a mosaic of two preserved ancestral haplotypes. • Despite annual outcrossing, recombination seems to be constraint. • A hybrid origin involving distinct Asian and European lineages needs to be tested. • Future clarification of the two parental ancestries will allow studies of gene functions. In the 1990s, a highly pathogenic and invasive lineage of the Asian ascomycete Hymenoscyphus fraxineus appeared in Europe. Spreading across the continent, the fungal lineage devastates common ash (Fraxinus excelsior) populations and is a threat to ash species worldwide. In contrast to highly diverse reference populations in Japan and East Russia, the expanding European population is characterized by the persistence of a mosaic of two ancestral haplotypes, and presumed constraints to recombination. Four hypotheses were proposed for the evolutionary origin of the European lineage. The first hypothesis H1 states that two, and only two, pathogenic founder individuals were transferred from Asia to Europe and successfully established. Alternatively, in addition to the fungus arriving in Europe, a change in function might have occurred and only then the lineage became invasive. The cause of such a change might have been H2: one to two mutations during meiosis; H3: the lateral transfer of a European cytoplasmatic element modifying the behavior of H. fraxineus ; or H4: a hybridization event with a closely related European ascomycete. Only the hybridization hypothesis seems to explain all of the genome-wide characteristics observed for the nuclear genome. Existing reconstructions of phylogenetic relationships at different taxonomic levels provide the evolutionary context of the lineages potentially involved. Vital information was gained from three configurations of nucleotide diversity and population differentiation associated with the genomic mosaic of monomorphic tracts and diversity islands. This synthesis points to the importance of identifying the taxonomic and geographic origins of the conserved two genomic ancestries within the European lineage of H. fraxineus and of reconstructing the mosaic of ancestral parental haplotypes (ancestry blocks) across the genome. Only with this information at hand will it be possible, to reliably interpret population-genomic data in the search for the functional elements underlying this unbalanced host-pathogen system. [ABSTRACT FROM AUTHOR]

Plant biologists have debated the evolutionary origin of the apple tribe (Maleae; Rosaceae) for over a century. The "wide-hybridization hypothesis" posits that the pome-bearing members of Maleae (base chromosome number x = 17) resulted from a hybridization and/or allopolyploid event between progenitors of other tribes in the subfamily Amygdaloideae with x = 8 and x = 9, respectively. An alternative "spiraeoid hypothesis" proposed that the x = 17 of Maleae arose via the genome doubling of x = 9 ancestors to x = 18, and subsequent aneuploidy resulting in x = 17. We use publicly available genomic data—448 nuclear genes and complete plastomes—from 27 species representing all major tribes within the Amygdaloideae to investigate evolutionary relationships within the subfamily containing the apple tribe. Specifically, we use network analyses and multi-labeled trees to test the competing wide-hybridization and spiraeoid hypotheses. Hybridization occurred between an ancestor of the tribe Spiraeeae (x = 9) and an ancestor of the clade Sorbarieae (x = 9) + Exochordeae (x = 8) + Kerrieae (x = 9), giving rise to the clade Gillenieae (x = 9) + Maleae (x = 17). The ancestor of the Maleae + Gillenieae arose via hybridization between distantly related tribes in the Amygdaloideae (i.e., supporting the wide hybridization hypothesis). However, some evidence supports an aspect of the spiraeoid hypothesis—the ancestors involved in the hybridization event were likely both x = 9, so genome doubling was followed by aneuploidy to result in x = 17 observed in Maleae. By synthesizing existing genomic data with novel analyses, we resolve the nearly century-old mystery regarding the origin of the apple tribe. Our results also indicate that nuclear gene tree-species tree conflict and/or cytonuclear conflict are pervasive at several other nodes in subfamily Amygdaloideae of Rosaceae. [ABSTRACT FROM AUTHOR]

Recently it was shown that a certain class of phylogenetic networks, called level-2 networks, cannot be reconstructed from their associated distance matrices. In this paper, we show that they can be reconstructed from their induced shortest and longest distance matrices. That is, if two level-2 networks induce the same shortest and longest distance matrices, then they must be isomorphic. We further show that level-2 networks are reconstructible from their shortest distance matrices if and only if they do not contain a subgraph from a family of graphs. A generator of a network is the graph obtained by deleting all pendant subtrees and suppressing degree-2 vertices. We also show that networks with a leaf on every generator side are reconstructible from their induced shortest distance matrix. [ABSTRACT FROM AUTHOR]

Measures of phylogenetic balance, such as the Colless and Sackin indices, play an important role in phylogenetics. Unfortunately, these indices are specifically designed for phylogenetic trees, and do not extend naturally to phylogenetic networks (which are increasingly used to describe reticulate evolution). This led us to consider a lesser-known balance index, whose definition is based on a probabilistic interpretation that is equally applicable to trees and to networks. This index, known as the B 2 index, was first proposed by Shao and Sokal (Syst Zool 39(3): 266–276, 1990). Surprisingly, it does not seem to have been studied mathematically since. Likewise, it is used only sporadically in the biological literature, where it tends to be viewed as arcane. In this paper, we study mathematical properties of B 2 such as its expectation and variance under the most common models of random trees and its extremal values over various classes of phylogenetic networks. We also assess its relevance in biological applications, and find it to be comparable to that of the Colless and Sackin indices. Altogether, our results call for a reevaluation of the status of this somewhat forgotten measure of phylogenetic balance. [ABSTRACT FROM AUTHOR]

Tree-based phylogenetic networks, which may be roughly defined as leaf-labeled networks built by adding arcs only between the original tree edges, have elegant properties for modeling evolutionary histories. We answer an open question of Francis, Semple, and Steel about the complexity of determining how far a phylogenetic network is from being tree-based, including non-binary phylogenetic networks. We show that finding a phylogenetic tree covering the maximum number of nodes in a phylogenetic network can be computed in polynomial time via an encoding into a minimum-cost flow problem. [ABSTRACT FROM AUTHOR]

Human papillomavirus type-16 (HPV16) is classified into lineages, A, B, C and D and 10 sub-lineages portraying variable infectivity, persistence, and cytological outcomes, however, with geographical variations. Our objective was to delineate the distinctive features of lineages among cervical squamous cell carcinoma (SCC) in the eastern region of India. A total of 145 SCC cases and 24 non-malignant specimens, harboring episomal HPV16, were included. The presence of higher proportion of lineage A over D was observed among SCC cases (86.89% A1, 8.97% D1 and 4.14% D2), while only A1 sub-lineage viruses were found among control specimens. Among the A1 viruses, an association of variants in the E5 (Y44L, I65V), E6 (L83V) genes and LCR: C7577T with SCC, with combined Odd's ratio (95% CI) of 20.5(4.61–91.25) was observed. Network analyses revealed the presence of 10 clades of lineage A viruses comprising of 64 HPV16 genomes harboring the risk alleles. High episomal HPV16 DNA copy numbers (adjusted p-value= 0.0271) and E7 mRNA expression (p-value=0.000017) predominated in SCC with lineage A, over D. Our study highlights the distinctive modalities of oncogenicity among different HPV16 lineages.

Plant biologists have debated the evolutionary origin of the apple tribe (Maleae; Rosaceae) for over a century. The “wide-hybridization hypothesis” posits that the pome-bearing members of Maleae (base chromosome number x = 17) resulted from a hybridization and/or allopolyploid event between progenitors of other tribes in the subfamily Amygdaloideae with x = 8 and x = 9, respectively. An alternative “spiraeoid hypothesis” proposed that the x = 17 of Maleae arose via the genome doubling of x = 9 ancestors to x = 18, and subsequent aneuploidy resulting in x = 17. We use publicly available genomic data—448 nuclear genes and complete plastomes—from 27 species representing all major tribes within the Amygdaloideae to investigate evolutionary relationships within the subfamily containing the apple tribe. Specifically, we use network analyses and multi-labeled trees to test the competing wide-hybridization and spiraeoid hypotheses. Hybridization occurred between an ancestor of the tribe Spiraeeae (x = 9) and an ancestor of the clade Sorbarieae (x = 9) + Exochordeae (x = 8) + Kerrieae (x = 9), giving rise to the clade Gillenieae (x = 9) + Maleae (x = 17). The ancestor of the Maleae + Gillenieae arose via hybridization between distantly related tribes in the Amygdaloideae (i.e., supporting the wide hybridization hypothesis). However, some evidence supports an aspect of the spiraeoid hypothesis—the ancestors involved in the hybridization event were likely both x = 9, so genome doubling was followed by aneuploidy to result in x = 17 observed in Maleae. By synthesizing existing genomic data with novel analyses, we resolve the nearly century-old mystery regarding the origin of the apple tribe. Our results also indicate that nuclear gene tree-species tree conflict and/or cytonuclear conflict are pervasive at several other nodes in subfamily Amygdaloideae of Rosaceae.

Gene flow between diverging lineages challenges the resolution of species boundaries and the understanding of evolutionary history in recent radiations. Here, we integrate phylogenetic and coalescent tools to resolve reticulate patterns of diversification and use a perspective focused on evolutionary mechanisms to distinguish interspecific and intraspecific taxonomic variation. We use this approach to resolve the systematics for one of the most intensively studied but difficult to understand groups of reptiles: the spotted whiptail lizards of the genus Aspidoscelis (A. gularis complex). Whiptails contain the largest number of unisexual species known within any vertebrate group and the spotted whiptail complex has played a key role in the generation of this diversity through hybrid speciation. Understanding lineage boundaries and the evolutionary history of divergence and reticulation within this group is therefore key to understanding the generation of unisexual diversity in whiptails. Despite this importance, long-standing confusion about their systematics has impeded understanding of which gonochoristic species have contributed to the formation of unisexual lineages. Using reduced representation genomic data, we resolve patterns of divergence and gene flow within the spotted whiptails and clarify patterns of hybrid speciation. We find evidence that biogeographically structured ecological and environmental variation has been important in morphological and genetic diversification, as well as the maintenance of species boundaries in this system. Our study elucidates how gene flow among lineages and the continuous nature of speciation can bias the practice of species delimitation and lead taxonomists operating under different frameworks to different conclusions (here we propose that a two species arrangement best reflects our current understanding). In doing so, this study provides conceptual and methodological insights into approaches to resolving diversification patterns and species boundaries in rapid radiations with complex histories, as well as long-standing taxonomic challenges in the field of systematic biology., (© The Author(s) 2024. Published by Oxford University Press, on behalf of the Society of Systematic Biologists. All rights reserved. For commercial re-use, please contact reprints@oup.com for reprints and translation rights for reprints. All other permissions can be obtained through our RightsLink service via the Permissions link on the article page on our site—for further information please contact journals.permissions@oup.com.)

Microbial studies typically involve the sequencing and assembly of draft genomes for individual microbes or whole microbiomes. Given a draft genome, one first task is to determine its phylogenetic context, that is, to place it relative to the set of related reference genomes. We provide a new interactive graphical tool that addresses this task using Mash sketches to compare against all bacterial and archaeal representative genomes in the Genome Taxonomy Database taxonomy, all within the framework of SplitsTree5. The phylogenetic context of the query sequences is then displayed as a phylogenetic outline, a new type of phylogenetic network that is more general than a phylogenetic tree, but significantly less complex than other types of phylogenetic networks. We propose to use such networks, rather than trees, to represent phylogenetic context, because they can express uncertainty in the placement of taxa, whereas a tree must always commit to a specific branching pattern. We illustrate the new method using a number of draft genomes of different assembly quality. [ABSTRACT FROM AUTHOR]

The use of diverse data sets in phylogenetic studies aiming for understanding evolutionary histories of species can yield conflicting inference. Phylogenetic conflicts observed in animal and plant systems have often been explained by hybridization, incomplete lineage sorting (ILS), or horizontal gene transfer. Here, we used target enrichment data, species tree, and species network approaches to infer the backbone phylogeny of the family Caprifoliaceae, while distinguishing among sources of incongruence. We used 713 nuclear loci and 46 complete plastome sequence data from 43 samples representing 38 species from all major clades to reconstruct the phylogeny of the family using concatenation and coalescence approaches. We found significant nuclear gene tree conflict as well as cytonuclear discordance. Additionally, coalescent simulations and phylogenetic species network analyses suggested putative ancient hybridization among subfamilies of Caprifoliaceae, which seems to be the main source of phylogenetic discordance. Ancestral state reconstruction of six morphological characters revealed some homoplasy for each character examined. By dating the branching events, we inferred the origin of Caprifoliaceae at approximately 66.65 Ma in the late Cretaceous. By integrating evidence from molecular phylogeny, divergence times, and morphology, we here recognize Zabelioideae as a new subfamily in Caprifoliaceae. This work shows the necessity of using a combination of multiple approaches to identify the sources of gene tree discordance. Our study also highlights the importance of using data from both nuclear and plastid genomes to reconstruct deep and shallow phylogenies of plants. [ABSTRACT FROM AUTHOR]

Phylogenetic networks can represent evolutionary events that cannot be described by phylogenetic trees. These networks are able to incorporate reticulate evolutionary events such as hybridization, introgression, and lateral gene transfer. Recently, network-based Markov models of DNA sequence evolution have been introduced along with model-based methods for reconstructing phylogenetic networks. For these methods to be consistent, the network parameter needs to be identifiable from data generated under the model. Here, we show that the semi-directed network parameter of a triangle-free, level-1 network model with any fixed number of reticulation vertices is generically identifiable under the Jukes–Cantor, Kimura 2-parameter, or Kimura 3-parameter constraints. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks. In particular, one needs to distinguish different networks and determine whether one network is contained in another. In this paper, we introduce cherry-picking networks, a class of networks that can be reduced by a so-called cherry-picking sequence. We then show how to compare such networks using their sequences. We characterize reconstructible cherry-picking networks, which are the networks that are uniquely determined by the sequences that reduce them, making them distinguishable. Furthermore, we show that a cherry-picking network is contained in another cherry picking network if a sequence for the latter network reduces the former network, provided both networks can be reconstructed from their sequences in a similar way (i.e., they are in the same reconstructible class). Lastly, we show that the converse of the above statement holds for tree-child networks, thereby showing that Network Containment , the problem of checking whether a network is contained in another, can be solved by computing cherry picking sequences in linear time for tree-child networks. [ABSTRACT FROM AUTHOR]

Evolutionary history, systematics and taxonomy of charrs of the genus Salvelinus and especially of the representatives of the S. alpinus–S. malma species complex remain confused that is connected with a substantial ecological and morphological flexibility of this group and with supposed ancient hybridization between some taxa. For the analysis of phylogenetic relationships and introgressive hybridization between the species of the genus Salvelinus including three endemic species from Lake El'gygytgyn and all main representatives of the S. alpinus–S. malma species complex, nucleotide sequences of the mtDNA control region and two nuclear genes (ITS1 and RAG1) were analyzed. The differences in the topologies of individual gene trees, among other reasons, were connected with incomplete lineage sorting and historical introgressive hybridization between certain taxa. Several cases of mtDNA capture by different taxa and phylogenetic groups were proposed. Main phylogenetic groups of the S. alpinus–S. malma species complex were revised. The origin and phylogenetic relationships of southern Dolly Varden from North America were not unambiguously defined. We proposed that introgressive hybridization had an important role in the evolutionary history of charrs, in particular, in the appearance of a high level of morphological, ecological and taxonomical diversity. [ABSTRACT FROM AUTHOR]

The process of hybridization occurs in approximately 40% of vascular plants, and this exchange of genetic material between non-conspecific individuals occurs unequally among plant lineages, being more frequent in certain groups such as Opuntia (Cactaceae). This genus is known for multiple taxonomic controversies due to widespread polyploidy and probable hybrid origin of several of its species. Southern Mexico species of this genus have been poorly studied despite their great diversity in regions such as the Tehuacán-Cuicatlán Valley which contains around 12% of recognized Mexico’s native Opuntia species. In this work, we focus on testing the hybrid status of two putative hybrids from this region, Opuntia tehuacana and Opuntia pilifera, and estimate if hybridization occurs among sampled southern opuntias using two newly identified nuclear intron markers to construct phylogenetic networks with HyDe and Dsuite and perform invariant analysis under the coalescent model with HyDe and Dsuite. For the test of hybrid origin in O. tehuacana, our results could not recover hybridization as proposed in the literature, but we found introgression into O. tehuacana individuals involving O. decumbens and O. huajuapensis. Regarding O. pilifera, we identified O. decumbens as probable parental species, supported by our analysis, which sustains the previous hybridization hypothesis between Nopalea and Basilares clades. Finally, we suggest new hybridization and introgression cases among southern Mexican species involving O. tehuantepecana and O. depressa as parental species of O. velutina and O. decumbens.

The process of hybridization occurs in approximately 40% of vascular plants, and this exchange of genetic material between non-conspecific individuals occurs unequally among plant lineages, being more frequent in certain groups such as Opuntia (Cactaceae). This genus is known for multiple taxonomic controversies due to widespread polyploidy and probable hybrid origin of several of its species. Southern Mexico species of this genus have been poorly studied despite their great diversity in regions such as the Tehuacán-Cuicatlán Valley which contains around 12% of recognized Mexico's native Opuntia species. In this work, we focus on testing the hybrid status of two putative hybrids from this region, Opuntia tehuacana and Opuntia pilifera , and estimate if hybridization occurs among sampled southern opuntias using two newly identified nuclear intron markers to construct phylogenetic networks with HyDe and Dsuite and perform invariant analysis under the coalescent model with HyDe and Dsuite. For the test of hybrid origin in O. tehuacana , our results could not recover hybridization as proposed in the literature, but we found introgression into O. tehuacana individuals involving O. decumbens and O. huajuapensis. Regarding O. pilifera , we identified O. decumbens as probable parental species, supported by our analysis, which sustains the previous hybridization hypothesis between Nopalea and Basilares clades. Finally, we suggest new hybridization and introgression cases among southern Mexican species involving O. tehuantepecana and O. depressa as parental species of O. velutina and O. decumbens. [ABSTRACT FROM AUTHOR]