Search

Background: The impacts of hybridization on the process of speciation are manifold, leading to distinct patterns across the genome. Genetic differentiation accumulates in certain genomic regions, while divergence is hampered in other regions by homogenizing gene flow, resulting in a heterogeneous genomic landscape. A consequence of this heterogeneity is that genomes are mosaics of different gene histories that can be compared to unravel complex speciation and hybridization events. However, incomplete lineage sorting (often the outcome of rapid speciation) can result in similar patterns. New statistical techniques, such as the D-statistic and hybridization networks, can be applied to disentangle the contributions of hybridization and incomplete lineage sorting. We unravel patterns of hybridization and incomplete lineage sorting during and after the diversification of the True Geese (family Anatidae, tribe Anserini, genera Anser and Branta) using an exon-based hybridization network approach and taking advantage of discordant gene tree histories by re-sequencing all taxa of this clade. In addition, we determine the timing of introgression and reconstruct historical effective population sizes for all goose species to infer which demographic or biogeographic factors might explain the observed patterns of introgression. Results: We find indications for ancient interspecific gene flow during the diversification of the True Geese and were able to pinpoint several putative hybridization events. Specifically, in the genus Branta, both the ancestor of the White-cheeked Geese (Hawaiian Goose, Canada Goose, Cackling Goose and Barnacle Goose) and the ancestor of the Brent Goose hybridized with Red-breasted Goose. One hybridization network suggests a hybrid origin for the Red-breasted Goose, but this scenario seems unlikely and it not supported by the D-statistic analysis. The complex, highly reticulated evolutionary history of the genus Anser hampered the estimation of ancient hybridization events by means of hybridization networks. The reconstruction of historical effective population sizes shows that most species showed a steady increase during the Pliocene and Pleistocene. These large effective population sizes might have facilitated contact between diverging goose species, resulting in the establishment of hybrid zones and consequent gene flow. Conclusions: Our analyses suggest that the evolutionary history of the True Geese is influenced by introgressive hybridization. The approach that we have used, based on genome-wide phylogenetic incongruence and network analyses, will be a useful procedure to reconstruct the complex evolutionary histories of many naturally hybridizing species groups. [ABSTRACT FROM AUTHOR]

Over the last fifteen years, phylogenetic networks have become a popular tool to analyse relationships between species whose past includes reticulation events such as hybridisation or horizontal gene transfer. However, the space of phylogenetic networks is significantly larger than that of phylogenetic trees, and how to analyse and search this enlarged space remains a poorly understood problem. Inspired by the widely-used rooted subtree prune and regraft (rSPR) operation on rooted phylogenetic trees, we propose a new operation—called subnet prune and regraft (SNPR)—that induces a metric on the space of all rooted phylogenetic networks on a fixed set of leaves. We show that the spaces of several popular classes of rooted phylogenetic networks (e.g. tree child, reticulation visible, and tree based) are connected under SNPR and that connectedness remains for the subclasses of these networks with a fixed number of reticulations. Lastly, we bound the distance between two rooted phylogenetic networks under the SNPR operation, show that it is computationally hard to compute this distance exactly, and analyse how the SNPR-distance between two such networks relates to the rSPR-distance between rooted phylogenetic trees that are embedded in these networks. [ABSTRACT FROM AUTHOR]

Maximum parsimony is one of the most frequently-discussed tree reconstruction methods in phylogenetic estimation. However, in recent years it has become more and more apparent that phylogenetic trees are often not sufficient to describe evolution accurately. For instance, processes like hybridization or lateral gene transfer that are commonplace in many groups of organisms and result in mosaic patterns of relationships cannot be represented by a single phylogenetic tree. This is why phylogenetic networks, which can display such events, are becoming of more and more interest in phylogenetic research. It is therefore necessary to extend concepts like maximum parsimony from phylogenetic trees to networks. Several suggestions for possible extensions can be found in recent literature, for instance the softwired and the hardwired parsimony concepts. In this paper, we analyze the so-called big parsimony problem under these two concepts, i.e. we investigate maximum parsimonious networks and analyze their properties. In particular, we show that finding a softwired maximum parsimony network is possible in polynomial time. We also show that the set of maximum parsimony networks for the hardwired definition always contains at least one phylogenetic tree. Lastly, we investigate some parallels of parsimony to different likelihood concepts on phylogenetic networks. [ABSTRACT FROM AUTHOR]

In studies of molecular evolution, phylogenetic trees are rooted binary trees, whereas phylogenetic networks are rooted acyclic digraphs. Edges are directed away from the root and leaves are uniquely labeled with taxa in phylogenetic networks. For the purpose of validating evolutionary models, biologists check whether or not a phylogenetic tree (resp. cluster) is contained in a phylogenetic network on the same taxa. These tree and cluster containment problems are known to be NP-complete. A phylogenetic network is reticulation-visible if every reticulation node separates the root of the network from at least a leaf. We answer an open problem by proving that the tree containment problem is solvable in quadratic time for reticulation-visible networks. The key tool used in our answer is a powerful decomposition theorem. It also allows us to design a linear-time algorithm for the cluster containment problem for networks of this type and to prove that every galled network with n leaves has 2 ( n − 1 ) reticulation nodes at most. [ABSTRACT FROM AUTHOR]

We consider the problem of when the total number n of vertices in a phylogenetic network N is bounded by the number ℓ of leaves in N . The main result of the paper says that, provided N avoids three certain substructures, then n is at most quadratic in ℓ . Furthermore, if any of these substructures is present in N , then ℓ does not necessarily bound n . [ABSTRACT FROM AUTHOR]

Phylogenetic networks are rooted, labelled directed acyclic graphswhich are commonly used to represent reticulate evolution. There is a close relationship between phylogenetic networks and multi-labelled trees (MUL-trees). Indeed, any phylogenetic network N can be 'unfolded' to obtain a MUL-tree U( N) and, conversely, a MUL-tree T can in certain circumstances be 'folded' to obtain aphylogenetic network F( T) that exhibits T. In this paper, we study properties of the operations U and F in more detail. In particular, we introduce the class of stable networks, phylogenetic networks N for which F( U( N)) is isomorphic to N, characterise such networks, and show that they are related to the well-known class of tree-sibling networks. We also explore how the concept of displaying a tree in a network N can be related to displaying the tree in the MUL-tree U( N). To do this, we develop aphylogenetic analogue of graph fibrations. This allows us to view U( N) as the analogue of the universal cover of a digraph, and to establish a close connection between displaying trees in U( N) and reconciling phylogenetic trees with networks. [ABSTRACT FROM AUTHOR]

Traditional “distance based methods” reconstruct a phylogenetic tree from a matrix of pair-wise distances between taxa. A phylogenetic network is a generalisation of a phylogenetic tree that can describe evolutionary events such as reticulation and hybridisation that are not tree-like. Although evolution has been known to be more accurately modelled by a network than a tree for some time, only recently have efforts been made to directly reconstruct a phylogenetic network from sequence data, as opposed to reconstructing several trees first and then trying to combine them into a single coherent network. In this work we present a generalisation of the UPGMA algorithm for ultrametric tree reconstruction which can accurately reconstruct ultrametric tree-child networks from the set of distinct distances between each pair of taxa. [ABSTRACT FROM AUTHOR]

Reconstructing the avian tree of life has become one of the major goals in ornithology. The use of genomic tools seemed a promising approach to reach this goal, but, instead, phylogenetic analyses of large numbers of genes uncovered high levels of incongruence between the resulting gene trees. This incongruence can be caused by several biological processes, such as recombination, hybridization, and rapid speciation (which can lead to incomplete lineage sorting). These processes directly or indirectly amount to deviations from tree-like patterns, thereby thwarting the use of phylogenetic trees. Phylogenetic networks provide an ideal tool to deal with these difficulties. We illustrate the usefulness of phylogenetic networks to capture the complexity and subtleties of diversification processes by discussing several recent genomic analyses of birds in general and the well-known radiation of Darwin's finches. With the increasing amount of genomic data in avian phylogenetic studies, capturing the evolutionary history of a set of taxa in a phylogenetic tree will become increasingly difficult. Moreover, given the widespread occurrence of hybridization and the numerous adaptive radiations in birds, phylogenetic networks provide a powerful tool to display and analyse the evolutionary history of many bird groups. The genomic era might thus result in a paradigm shift in avian phylogenetics from trees to bushes. [ABSTRACT FROM AUTHOR]

Background: Curious parallels between the processes of species and language evolution have been observed by many researchers. Retracing the evolution of Indo-European (IE) languages remains one of the most intriguing intellectual challenges in historical linguistics. Most of the IE language studies use the traditional phylogenetic tree model to represent the evolution of natural languages, thus not taking into account reticulate evolutionary events, such as language hybridization and word borrowing which can be associated with species hybridization and horizontal gene transfer, respectively. More recently, implicit evolutionary networks, such as split graphs and minimal lateral networks, have been used to account for reticulate evolution in linguistics. Results: Striking parallels existing between the evolution of species and natural languages allowed us to apply three computational biology methods for reconstruction of phylogenetic networks to model the evolution of IE languages. We show how the transfer of methods between the two disciplines can be achieved, making necessary methodological adaptations. Considering basic vocabulary data from the well-known Dyen’s lexical database, which contains word forms in 84 IE languages for the meanings of a 200-meaning Swadesh list, we adapt a recently developed computational biology algorithm for building explicit hybridization networks to study the evolution of IE languages and compare our findings to the results provided by the split graph and galled network methods. Conclusion: We conclude that explicit phylogenetic networks can be successfully used to identify donors and recipients of lexical material as well as the degree of influence of each donor language on the corresponding recipient languages. We show that our algorithm is well suited to detect reticulate relationships among languages, and present some historical and linguistic justification for the results obtained. Our findings could be further refined if relevant syntactic, phonological and morphological data could be analyzed along with the available lexical data. [ABSTRACT FROM AUTHOR]

The role of hybridization and subsequent introgression has been demonstrated in an increasing number of species. Recently, Fontaine et al. ( Science, 347, 2015, 1258524) conducted a phylogenomic analysis of six members of the Anopheles gambiae species complex. Their analysis revealed a reticulate evolutionary history and pointed to extensive introgression on all four autosomal arms. The study further highlighted the complex evolutionary signals that the co-occurrence of incomplete lineage sorting ( ILS) and introgression can give rise to in phylogenomic analyses. While tree-based methodologies were used in the study, phylogenetic networks provide a more natural model to capture reticulate evolutionary histories. In this work, we reanalyse the Anopheles data using a recently devised framework that combines the multispecies coalescent with phylogenetic networks. This framework allows us to capture ILS and introgression simultaneously, and forms the basis for statistical methods for inferring reticulate evolutionary histories. The new analysis reveals a phylogenetic network with multiple hybridization events, some of which differ from those reported in the original study. To elucidate the extent and patterns of introgression across the genome, we devise a new method that quantifies the use of reticulation branches in the phylogenetic network by each genomic region. Applying the method to the mosquito data set reveals the evolutionary history of all the chromosomes. This study highlights the utility of 'network thinking' and the new insights it can uncover, in particular in phylogenomic analyses of large data sets with extensive gene tree incongruence. [ABSTRACT FROM AUTHOR]

In this paper, we present an analysis of oracle bone characters for animals from a 'cognitive' point of view. After some general remarks on oracle-bone characters presented in Sec. 1 and a short outline of the paper in Sec. 2, we collect various oracle-bone characters for animals from published resources in Sec. 3. In the next section, we begin analyzing a group of 60 ancient animal characters from , a highly acclaimed internet dictionary of Chinese characters that is strictly based on historical sources, and introduce five categories of specific features regarding their (graphical) structure that will be used in Sec. 5 to associate corresponding feature vectors to these characters. In Sec. 6, these feature vectors will be used to investigate their dissimilarity in terms of a family of parameterized distance measures. And in the last section, we apply the method as encoded in the algorithms to construct a corresponding family of dissimilarity-based networks with the intention of elucidating how the ancient Chinese might have perceived the 'animal world' in the late bronze age and to demonstrate that these pictographs reflect an intuitive understanding of this world and its inherent structure that predates its classification in the oldest surviving Chinese encyclopedia from approximately the third century BC, the Er Ya, as well as similar classification systems in the West by one to two millennia. We also present an English dictionary of 70 oracle bone characters for animals in Appendix A. In Appendix B, we list various variants of animal characters that were published in the Jia Gu Wen Bian (cf. 甲骨文编, A Complete Collection of Oracle Bone Characters, edited by the Institute of Archaeology of the Chinese Academy of Social Sciences, published by the Zhonghua Book Company in 1965). We recall the frequencies of the 521 most frequent oracle bone characters in Appendix C as reported in [T. Chen, Yin-Shang Jiaguwen Zixing Xitong Zai Yanjiu, (The Structural System of Oracle Inscriptions) (Shanghai Renmin Chubanshe, Shanghai, 2010); Jiaguwen Shiwen Yongzi Pinlü Biao (A Frequency List of Oracle Characters), Center for the Study and Application of Chinese Characters (East China Normal University, Shanghai, 2010), . And in Appendix D, we list the animals registered in the last five chapters of the Er Ya. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that are used to represent the evolution of species which have undergone reticulate evolution. In this paper we consider spaces of such networks defined by some novel local operations that we introduce for converting one phylogenetic network into another. These operations are modeled on the well-studied nearest-neighbor interchange operations on phylogenetic trees, and lead to natural generalizations of the tree spaces that have been previously associated to such operations. We present several results on spaces of some relatively simple networks, called level-1 networks, including the size of the neighborhood of a fixed network, and bounds on the diameter of the metric defined by taking the smallest number of operations required to convert one network into another. We expect that our results will be useful in the development of methods for systematically searching for optimal phylogenetic networks using, for example, likelihood and Bayesian approaches. [ABSTRACT FROM AUTHOR]

We show that the class of tree-child networks is precisely the class of tree-based networks with the property that every embedded phylogenetic tree is a base tree. [ABSTRACT FROM AUTHOR]

The ever increasing number of computer programs developed for phylogenetic research does not necessarily facilitate the construction of biologically relevant phylogenies. Regardless of the algorithm utilized by new software, the vast majority result in treelike graphs. We suggest that a new, more inclusive framework for phylogenetic studies needs to be developed, which includes trees as an alternative in the absence of conflicting signals in the sequence data set. Conflicts are caused by noisy phylogenetic signal deriving from hybridization, allopolyploidy and lateral gene transfer—biological processes that undermine the construction of simple dichotomic bifurcating graphs. A robust framework for determining biologically relevant phylogenetic relationships should include quality analysis of the phylogenetic signal, a thorough determination of homology, analyses for phylogenetic networks, and exploration of the data for character or tree conflicts.

Background: The classification of royal ferns (Osmundaceae) has long remained controversial. Recent molecular phylogenies indicate that Osmunda is paraphyletic and needs to be separated into Osmundastrum and Osmunda s.str. Here, however, we describe an exquisitely preserved Jurassic Osmunda rhizome (O. pulchella sp. nov.) that combines diagnostic features of both Osmundastrum and Osmunda, calling molecular evidence for paraphyly into question. We assembled a new morphological matrix based on rhizome anatomy, and used network analyses to establish phylogenetic relationships between fossil and extant members of modern Osmundaceae. We re-analysed the original molecular data to evaluate root-placement support. Finally, we integrated morphological and molecular data-sets using the evolutionary placement algorithm. Results: Osmunda pulchella and five additional Jurassic rhizome species show anatomical character suites intermediate between Osmundastrum and Osmunda. Molecular evidence for paraphyly is ambiguous: a previously unrecognized signal from spacer sequences favours an alternative root placement that would resolve Osmunda s.l. as monophyletic. Our evolutionary placement analysis identifies fossil species as probable ancestral members of modern genera and subgenera, which accords with recent evidence from Bayesian dating. Conclusions: Osmunda pulchella is likely a precursor of the Osmundastrum lineage. The recently proposed root placement in Osmundaceae—based solely on molecular data—stems from possibly misinformative outgroup signals in rbcL and atpA genes. We conclude that the seemingly conflicting evidence from morphological, anatomical, molecular, and palaeontological data can instead be elegantly reconciled under the assumption that Osmunda is indeed monophyletic. [ABSTRACT FROM AUTHOR]

The tryptophan biosynthesis pathway is universal for the majority of known organisms, although it is absent in animals and some eubacteria. This pathway is conserved in plants, although various species differ in the number of paralogs of the enzymes involved in it. In this work, the possible role of the changes in the number of tryptophan biosynthesis enzymes paralogs in the course of evolution was analyzed. Towards this, the paralogs of the enzymes in tryptophan biosynthesis pathways were identified in plant species with fully sequenced genomes, and the relationship between the number of paralogs and the organismal complexity was assessed. It was demonstrated that organismal complexity statistically correlates with the number of tryptophan biosynthesis enzymes homologs, both with the total number of homologs and with the number of homologs for three of six enzymes, namely, ASA/ASB, PAI, and IGPS. This relationship may be accounted for by the increase in the organismal complexity and the number of tryptophan biosynthesis enzymes' homologs being the mechanism of evolutionary adaptation to the varying conditions of the terrestrial environment in plants. [ABSTRACT FROM AUTHOR]

We give approximate counting formulae for the numbers of labelled general, treechild, and normal (binary) phylogenetic networks on n vertices. These formulae are of the form $${2^{\gamma n {\rm log}n+O(n)}}$$ , where the constant $${\gamma}$$ is $${\frac{3}{2}}$$ for general networks, and $${\frac{5}{4}}$$ for tree-child and normal networks. We also show that the number of leaf-labelled tree-child and normal networks with $${\ell}$$ leaves are both $${{2}^{2 \ell {\rm log} \ell +O( \ell )}}$$ . Further we determine the typical numbers of leaves, tree vertices, and reticulation vertices for each of these classes of networks. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of maximum parsimony on networks, "hardwired" and "softwired," and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multiterminal Cut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and the softwired parsimony scores can be computed efficiently using integer linear programming. The software has been made freely available. [ABSTRACT FROM AUTHOR]

Hybridization plays an important role in the evolution of certain groups of organisms, adaptation to their environments, and diversification of their genomes. The evolutionary histories of such groups are reticulate, and methods for reconstructing them are still in their infancy and have limited applicability. We present a maximum likelihood method for inferring reticulate evolutionary histories while accounting simultaneously for incomplete lineage sorting. Additionally, we propose methods for assessing confidence in the amount of reticulation and the topology of the inferred evolutionary history. Our method obtains accurate estimates of reticulate evolutionary histories on simulated datasets. Furthermore, our method provides support for a hypothesis of a reticulate evolutionary history inferred from a set of house mouse (Mus musculus) genomes. As evidence of hybridization in eukaryotic groups accumulates, it is essential to have methods that infer reticulate evolutionary histories. The work we present here allows for such inference and provides a significant step toward putting phylogenetic networks on par with phylogenetic trees as a model of capturing evolutionary relationships. [ABSTRACT FROM AUTHOR]

ITS sequences from isolated populations of Acer in the Colchic region allow direct assumptions about the origin, evolution, and radiation of one of the most abundant West Eurasian tree species, Acer campestre L., the field maple. We inferred the molecular evolution of the internal transcribed spacers ITS1 and ITS2 of the nuclear-encoded 35S rDNA cistron in Acer campestre using a range of methods including sequence- and distance-based phylogenetic networks and motif analyses. The data basis for our inference are 344 sequenced clones from 51 individuals of A. campestre, essentially covering the modern distribution range of the species, and 27 individuals representing other species of Acer section Platanoidea. Our results indicate that Acer campestre comprises 2 cryptic species, 1 of which is confined to North-East Turkey and South-West Georgia (ancient Colchis region). Detailed analysis shows that the Colchic genotype is generally more similar to other species of the section than the main genotype of Acer campestre sampled from North Turkey to the Pyrenees. In the light of the fossil record and general differentiation patterns in West Eurasian Acer, we conclude that the Colchic genotype represents a survivor of the initial radiation within section Platanoidea, predating the formation of modern species. [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., (© 2022. The Author(s), under exclusive licence to Springer Nature Switzerland AG.)