Sliding MinPD: building evolutionary networks of serial samples via an automated recombination detection approach

MOTIVATION: Traditional phylogenetic methods assume tree-like evolutionary models and are likely to perform poorly when provided with sequence data from fast-evolving, recombining viruses. Furthermore, these methods assume that all the sequence data are from contemporaneous taxa, which is not valid for serially-sampled data. A more general approach is proposed here, referred to as the Sliding MinPD method, that reconstructs evolutionary networks for serially-sampled sequences in the presence of recombination. RESULTS: Sliding MinPD combines distance-based phylogenetic methods with automated recombination detection based on the best-known sliding window approaches to reconstruct serial evolutionary networks. Its performance was evaluated through comprehensive simulation studies and was also applied to a set of serially-sampled HIV sequences from a single patient. The resulting network organizations reveal unique patterns of viral evolution and may help explain the emergence of disease-associated mutants and drug-resistant strains with implications for patient prognosis and treatment strategies.     

Heterogeneity in antibody range and the antigenic drift of influenza A viruses

In this paper we explore the consequences of a heterogeneous immune response in individuals on the evolution of a rapidly mutating virus. We show that several features of the incidence and phylogenetic patterns typical of influenza A may be understood in this framework. In our model, limited diversity and rapid drift of the circulating viral strains result from the interplay of two interacting subpopulations with different types of immune response, narrow or broad, upon infection. The subpopulation with the narrow immune response acts as a reservoir where consecutive mutations escape immunity and can persist. Strains with a number of accumulated mutations escape immunity in the other subpopulation as well, causing larger epidemic peaks in the whole population, and reducing strain diversity. Overall, our model produces a modulation of epidemic peak heights and patterns of antigenic drift consistent with reported observations, suggesting an underlying mechanism for the evolutionary epidemiology of influenza, in particular, and other infectious diseases, more generally.     

Evidence for an independent radiation of endosymbiotic litostome ciliates within Australian marsupial herbivores

Observations from molecular marker studies on recently diverged species indicate that substitution patterns in DNA sequences can often be complex and poorly described by tree-like bifurcating evolutionary models. These observations might result from processes of species diversification and/or processes of sequence evolution that are not tree-like. In these cases, bifurcating tree representations provide poor visualization of phylogenetic signals in sequence data. In this paper, we use median networks to study DNA sequence substitution patterns in plant nuclear and chloroplast markers. We describe how to prune median networks to obtain so called pruned median networks. These simpler networks may help to provide a useful framework for investigating the phylogenetic complexity of recently diverged taxa with hybrid origins.     

Stochastic processes are key determinants of short-term evolution in influenza a virus

Understanding the evolutionary dynamics of influenza A virus is central to its surveillance and control. While immune-driven antigenic drift is a key determinant of viral evolution across epidemic seasons, the evolutionary processes shaping influenza virus diversity within seasons are less clear. Here we show with a phylogenetic analysis of 413 complete genomes of human H3N2 influenza A viruses collected between 1997 and 2005 from New York State, United States, that genetic diversity is both abundant and largely generated through the seasonal importation of multiple divergent clades of the same subtype. These clades cocirculated within New York State, allowing frequent reassortment and generating genome-wide diversity. However, relatively low levels of positive selection and genetic diversity were observed at amino acid sites considered important in antigenic drift. These results indicate that adaptive evolution occurs only sporadically in influenza A virus; rather, the stochastic processes of viral migration and clade reassortment play a vital role in shaping short-term evolutionary dynamics. Thus, predicting future patterns of influenza virus evolution for vaccine strain selection is inherently complex and requires intensive surveillance, whole-genome sequencing, and phenotypic analysis.     

Explaining the geographical origins of seasonal influenza A (H3N2)

Most antigenically novel and evolutionarily successful strains of seasonal influenza A (H3N2) originate in East, South and Southeast Asia. To understand this pattern, we simulated the ecological and evolutionary dynamics of influenza in a host metapopulation representing the temperate north, tropics and temperate south. Although seasonality and air traffic are frequently used to explain global migratory patterns of influenza, we find that other factors may have a comparable or greater impact. Notably, a region''s basic reproductive number (R₀) strongly affects the antigenic evolution of its viral population and the probability that its strains will spread and fix globally: a 17–28% higher R₀ in one region can explain the observed patterns. Seasonality, in contrast, increases the probability that a tropical (less seasonal) population will export evolutionarily successful strains but alone does not predict that these strains will be antigenically advanced. The relative sizes of different host populations, their birth and death rates, and the region in which H3N2 first appears affect influenza''s phylogeography in different but relatively minor ways. These results suggest general principles that dictate the spatial dynamics of antigenically evolving pathogens and offer predictions for how changes in human ecology might affect influenza evolution.     

Uprooted Phylogenetic Networks

The need for structures capable of accommodating complex evolutionary signals such as those found in, for example, wheat has fueled research into phylogenetic networks. Such structures generalize the standard model of a phylogenetic tree by also allowing for cycles and have been introduced in rooted and unrooted form. In contrast to phylogenetic trees or their unrooted versions, rooted phylogenetic networks are notoriously difficult to understand. To help alleviate this, recent work on them has also centered on their “uprooted” versions. By focusing on such graphs and the combinatorial concept of a split system which underpins an unrooted phylogenetic network, we show that not only can a so-called (uprooted) 1-nested network N be obtained from the Buneman graph (sometimes also called a median network) associated with the split system \(\Sigma (N)\) induced on the set of leaves of N but also that that graph is, in a well-defined sense, optimal. Along the way, we establish the 1-nested analogue of the fundamental “splits equivalence theorem” for phylogenetic trees and characterize maximal circular split systems.     

The Evolutionary Dynamics of Human Influenza B Virus

Despite their close phylogenetic relationship, type A and B influenza viruses exhibit major epidemiological differences in humans, with the latter both less common and less often associated with severe disease. However, it is unclear what processes determine the evolutionary dynamics of influenza B virus, and how influenza viruses A and B interact at the evolutionary scale. To address these questions we inferred the phylogenetic history of human influenza B virus using complete genome sequences for which the date (day) of isolation was available. By comparing the phylogenetic patterns of all eight viral segments we determined the occurrence of segment reassortment over a 30-year sampling period. An analysis of rates of nucleotide substitution and selection pressures revealed sporadic occurrences of adaptive evolution, most notably in the viral hemagglutinin and compatible with the action of antigenic drift, yet lower rates of overall and nonsynonymous nucleotide substitution compared to influenza A virus. Overall, these results led us to propose a model in which evolutionary changes within and between the antigenically distinct 'Yam88' and 'Vic87' lineages of influenza B virus are the result of changes in herd immunity, with reassortment continuously generating novel genetic variation. Additionally, we suggest that the interaction with influenza A virus may be central in shaping the evolutionary dynamics of influenza B virus, facilitating the shift of dominance between the Vic87 and the Yam88 lineages.     

Detecting phylogenetic signal in mutualistic interaction networks using a Markov process model

Ecological interaction networks, such as those describing the mutualistic interactions between plants and their pollinators or between plants and their frugivores, exhibit non‐random structural properties that cannot be explained by simple models of network formation. One factor affecting the formation and eventual structure of such a network is its evolutionary history. We argue that this, in many cases, is closely linked to the evolutionary histories of the species involved in the interactions. Indeed, empirical studies of interaction networks along with the phylogenies of the interacting species have demonstrated significant associations between phylogeny and network structure. To date, however, no generative model explaining the way in which the evolution of individual species affects the evolution of interaction networks has been proposed. We present a model describing the evolution of pairwise interactions as a branching Markov process, drawing on phylogenetic models of molecular evolution. Using knowledge of the phylogenies of the interacting species, our model yielded a significantly better fit to 21% of a set of plant–pollinator and plant–frugivore mutualistic networks. This highlights the importance, in a substantial minority of cases, of inheritance of interaction patterns without excluding the potential role of ecological novelties in forming the current network architecture. We suggest that our model can be used as a null model for controlling evolutionary signals when evaluating the role of other factors in shaping the emergence of ecological networks.     

A quantitative genotype algorithm reflecting H5N1 Avian influenza niches

MOTIVATION: Computational genotyping analyses are critical for characterizing molecular evolutionary footprints, thus providing important information for designing the strategies of influenza prevention and control. Most of the current methods that are available are based on multiple sequence alignment and phylogenetic tree construction, which are time consuming and limited by the number of taxa. Arbitrarily defining genotypes further complicates the interpretation of genotyping results. METHODS: In this study, we describe a quantitative influenza genotyping algorithm based on the theory of quasispecies. First, the complete composition vector (CCV) was utilized to calculate the pairwise evolutionary distance between genotypes. Next, Hierarchical Bayesian Modeling using the Gibbs Sampling algorithm was applied to identify the segment genotype threshold, which is used to identify influenza segment genotype through a modularity calculation. The viral genotype was defined by combining eight segment genotypes based on the genetic reassortment feature of influenza A viruses. RESULTS: We applied this method for H5N1 avian influenza viruses and identified 107 niches among 283 viruses with a complete genome set. The diversity of viral genotypes, and their correlation with geographic locations suggests that these viruses form local niches after being introduced to a new ecological environment through poultry trade or bird migration. This novel method allows us to define genotypes in a robust, quantitative as well as hierarchical manner. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

Clade replacements in dengue virus serotypes 1 and 3 are associated with changing serotype prevalence

The evolution of dengue virus (DENV) is characterized by phylogenetic trees that have a strong temporal structure punctuated by dramatic changes in clade frequency. To determine the cause of these large-scale phylogenetic patterns, we examined the evolutionary history of DENV serotype 1 (DENV-1) and DENV-3 in Thailand, where gene sequence and epidemiological data are relatively abundant over a 30-year period. We found evidence for the turnover of viral clades in both serotypes, most notably in DENV-1, where a major clade replacement event took place in genotype I during the mid-1990s. Further, when this clade replacement event was placed in the context of changes in serotype prevalence in Thailand, a striking pattern emerged; an increase in DENV-1 clade diversity was associated with an increase in the abundance of this serotype and a concomitant decrease in DENV-4 prevalence, while clade replacement was associated with a decline in DENV-1 prevalence and a rise of DENV-4. We postulate that intraserotypic genetic diversification proceeds at times of relative serotype abundance and that replacement events can result from differential susceptibility to cross-reactive immune responses.     

Hitchhiking and the Population Genetic Structure of Avian Influenza Virus

Previous studies have revealed a major difference in the phylogenetic structure, extent of genetic diversity, and selection pressure between the surface glycoproteins and internal gene segments of avian influenza viruses (AIV) sampled from wild birds. However, what evolutionary processes are responsible for these strikingly different evolutionary patterns is unclear. To address this issue, we estimated the rate of evolutionary change and time of origin of each segment of AIV sampled globally. Strikingly, the internal segments of the sampled AIV strains possess common ancestors that existed less than 200 years ago. Similarly recent times of origin were observed for each of the individual subtypes within the HA, NA, and NS gene segments. Such a shallow history of genetic diversity suggests an evolutionary model in which the genetic structure of AIV is shaped by a combination of occasional selective sweeps in the HA and NA (and possibly NS) segments, coupled with transient genetic linkage to the internal gene segments.     

Coevolution in Multispecific Interactions among Free-Living Species

Ecological interactions among species are the backbone of biodiversity. Interactions take a tremendous variety of forms in nature and have pervasive consequences for the population dynamics and evolution of species. A persistent challenge in evolutionary biology has been to understand how coevolution has produced complex webs of interacting species, where a large number of species interact through mutual dependences (e.g., mutualisms) or influences (e.g., predator–prey interactions in food webs). Recent work on megadiverse species assemblages in ecological communities has uncovered interesting repeated patterns that emerge in these complex networks of multispecies interactions. They include the presence of a core of super- generalists, proper patterns of interaction (that resemble nested chinese boxes), and multiple modules that act as the basic blocks of the complex network. The structure of multispecies interactions resembles other complex networks and is central to understanding its evolution and the consequences of species losses for the persistence of the whole network. These patterns suggest both precise ways on how coevolution goes on beyond simple pairwise interactions and scales up to whole communities.     

Structure versus time in the evolutionary diversification of avian carotenoid metabolic networks

Historical associations of genes and proteins are thought to delineate pathways available to subsequent evolution; however, the effects of past functional involvements on contemporary evolution are rarely quantified. Here, we examined the extent to which the structure of a carotenoid enzymatic network persists in avian evolution. Specifically, we tested whether the evolution of carotenoid networks was most concordant with phylogenetically structured expansion from core reactions of common ancestors or with subsampling of biochemical pathway modules from an ancestral network. We compared structural and historical associations in 467 carotenoid networks of extant and ancestral species and uncovered the overwhelming effect of pre‐existing metabolic network structure on carotenoid diversification over the last 50 million years of avian evolution. Over evolutionary time, birds repeatedly subsampled and recombined conserved biochemical modules, which likely maintained the overall structure of the carotenoid metabolic network during avian evolution. These findings explain the recurrent convergence of evolutionary distant species in carotenoid metabolism and weak phylogenetic signal in avian carotenoid evolution. Remarkable retention of an ancient metabolic structure throughout extensive and prolonged ecological diversification in avian carotenoid metabolism illustrates a fundamental requirement of organismal evolution – historical continuity of a deterministic network that links past and present functional associations of its components.     

Evolution and dynamics of megaplasmids with genome sizes larger than 100 kb in the Bacillus cereus group

Background

Every year the human population encounters epidemic outbreaks of influenza, and history reveals recurring pandemics that have had devastating consequences. The current work focuses on the development of a robust algorithm for detecting influenza strains that have a composite genomic architecture. These influenza subtypes can be generated through a reassortment process, whereby a virus can inherit gene segments from two different types of influenza particles during replication. Reassortant strains are often not immediately recognised by the adaptive immune system of the hosts and hence may be the source of pandemic outbreaks. Owing to their importance in public health and their infectious ability, it is essential to identify reassortant influenza strains in order to understand the evolution of this virus and describe reassortment pathways that may be biased towards particular viral segments. Phylogenetic methods have been used traditionally to identify reassortant viruses. In many studies up to now, the assumption has been that if two phylogenetic trees differ, it is because reassortment has caused them to be different. While phylogenetic incongruence may be caused by real differences in evolutionary history, it can also be the result of phylogenetic error. Therefore, we wish to develop a method for distinguishing between topological inconsistency that is due to confounding effects and topological inconsistency that is due to reassortment.

Results

The current work describes the implementation of two approaches for robustly identifying reassortment events. The algorithms rest on the idea of significance of difference between phylogenetic trees or phylogenetic tree sets, and subtree pruning and regrafting operations, which mimic the effect of reassortment on tree topologies. The first method is based on a maximum likelihood (ML) framework (MLreassort) and the second implements a Bayesian approach (Breassort) for reassortment detection. We focus on reassortment events that are found by both methods. We test both methods on a simulated dataset and on a small collection of real viral data isolated in Hong Kong in 1999.

Conclusions

The nature of segmented viral genomes present many challenges with respect to disease. The algorithms developed here can effectively identify reassortment events in small viral datasets and can be applied not only to influenza but also to other segmented viruses. Owing to computational demands of comparing tree topologies, further development in this area is necessary to allow their application to larger datasets.

     

Allele dynamics plots for the study of evolutionary dynamics in viral populations

Phylodynamic techniques combine epidemiological and genetic information to analyze the evolutionary and spatiotemporal dynamics of rapidly evolving pathogens, such as influenza A or human immunodeficiency viruses. We introduce 'allele dynamics plots' (AD plots) as a method for visualizing the evolutionary dynamics of a gene in a population. Using AD plots, we propose how to identify the alleles that are likely to be subject to directional selection. We analyze the method's merits with a detailed study of the evolutionary dynamics of seasonal influenza A viruses. AD plots for the major surface protein of seasonal influenza A (H3N2) and the 2009 swine-origin influenza A (H1N1) viruses show the succession of substitutions that became fixed in the evolution of the two viral populations. They also allow the early identification of those viral strains that later rise to predominance, which is important for the problem of vaccine strain selection. In summary, we describe a technique that reveals the evolutionary dynamics of a rapidly evolving population and allows us to identify alleles and associated genetic changes that might be under directional selection. The method can be applied for the study of influenza A viruses and other rapidly evolving species or viruses.     

Genotype networks shed light on evolutionary constraints

An evolutionary constraint is a bias or limitation in phenotypic variation that a biological system produces. One can distinguish physicochemical, selective, genetic and developmental causes of such constraints. Here, I discuss these causes in three classes of system that bring forth many phenotypic traits and evolutionary innovations: regulatory circuits, macromolecules and metabolic networks. In these systems, genotypes with the same phenotype form large genotype networks that extend throughout a vast genotype space. Such genotype networks can help unify different causes of evolutionary constraints. They can show that these causes ultimately emerge from the process of development; that is, how phenotypes form from genotypes. Furthermore, they can explain important consequences of constraints, such as punctuated stasis and canalization.     

Phylogenetic Networks that Display a Tree Twice

In the last decade, the use of phylogenetic networks to analyze the evolution of species whose past is likely to include reticulation events, such as horizontal gene transfer or hybridization, has gained popularity among evolutionary biologists. Nevertheless, the evolution of a particular gene can generally be described without reticulation events and therefore be represented by a phylogenetic tree. While this is not in contrast to each other, it places emphasis on the necessity of algorithms that analyze and summarize the tree-like information that is contained in a phylogenetic network. We contribute to the toolbox of such algorithms by investigating the question of whether or not a phylogenetic network embeds a tree twice and give a quadratic-time algorithm to solve this problem for a class of networks that is more general than tree-child networks.     

Modularity in the evolution of yeast protein interaction network

Protein interaction networks are known to exhibit remarkable structures: scale-free and small-world and modular structures. To explain the evolutionary processes of protein interaction networks possessing scale-free and small-world structures, preferential attachment and duplication-divergence models have been proposed as mathematical models. Protein interaction networks are also known to exhibit another remarkable structural characteristic, modular structure. How the protein interaction networks became to exhibit modularity in their evolution? Here, we propose a hypothesis of modularity in the evolution of yeast protein interaction network based on molecular evolutionary evidence. We assigned yeast proteins into six evolutionary ages by constructing a phylogenetic profile. We found that all the almost half of hub proteins are evolutionarily new. Examining the evolutionary processes of protein complexes, functional modules and topological modules, we also found that member proteins of these modules tend to appear in one or two evolutionary ages. Moreover, proteins in protein complexes and topological modules show significantly low evolutionary rates than those not in these modules. Our results suggest a hypothesis of modularity in the evolution of yeast protein interaction network as systems evolution.     

Serial evolutionary networks of within-patient HIV-1 sequences reveal patterns of evolution of X4 strains

Background  

The HIV virus is known for its ability to exploit numerous genetic and evolutionary mechanisms to ensure its proliferation, among them, high replication, mutation and recombination rates. Sliding MinPD, a recently introduced computational method [1], was used to investigate the patterns of evolution of serially-sampled HIV-1 sequence data from eight patients with a special focus on the emergence of X4 strains. Unlike other phylogenetic methods, Sliding MinPD combines distance-based inference with a nonparametric bootstrap procedure and automated recombination detection to reconstruct the evolutionary history of longitudinal sequence data. We present serial evolutionary networks as a longitudinal representation of the mutational pathways of a viral population in a within-host environment. The longitudinal representation of the evolutionary networks was complemented with charts of clinical markers to facilitate correlation analysis between pertinent clinical information and the evolutionary relationships.