Reassortment networks for investigating the evolution of segmented viruses

Phylogenetic network analysis as a parsimony optimization problem

BACKGROUND

Many problems in comparative biology are, or are thought to be, best expressed as phylogenetic "networks" as opposed to trees. In trees, vertices may have only a single parent (ancestor), while networks allow for multiple parent vertices. There are two main interpretive types of networks, "softwired" and "hardwired." The parsimony cost of hardwired networks is based on all changes over all edges, hence must be greater than or equal to the best tree cost contained ("displayed") by the network. This is in contrast to softwired, where each character follows the lowest parsimony cost tree displayed by the network, resulting in costs which are less than or equal to the best display tree. Neither situation is ideal since hard-wired networks are not generally biologically attractive (since individual heritable characters can have more than one parent) and softwired networks can be trivially optimized (containing the best tree for each character). Furthermore, given the alternate cost scenarios of trees and these two flavors of networks, hypothesis testing among these explanatory scenarios is impossible.

RESULTS

A network cost adjustment (penalty) is proposed to allow phylogenetic trees and soft-wired phylogenetic networks to compete equally on a parsimony optimality basis. This cost is demonstrated for several real and simulated datasets. In each case, the favored graph representation (tree or network) matched expectation or simulation scenario.

CONCLUSIONS

The softwired network cost regime proposed here presents a quantitative criterion for an optimality-based search procedure where trees and networks can participate in hypothesis testing simultaneously.

Molecular epidemiology of influenza A/H3N2 viruses circulating in Mexico from 2003 to 2012

In this work, nineteen influenza A/H3N2 viruses isolated in Mexico between 2003 and 2012 were studied. Our findings show that different human A/H3N2 viral lineages co-circulate within a same season and can also persist locally in between different influenza seasons, increasing the chance for genetic reassortment events. A novel minor cluster was also identified, named here as Korea, that circulated worldwide during 2003. Frequently, phylogenetic characterization did not correlate with the determined antigenic identity, supporting the need for the use of molecular evolutionary tools additionally to antigenic data for the surveillance and characterization of viral diversity during each flu season. This work represents the first long-term molecular epidemiology study of influenza A/H3N2 viruses in Mexico based on the complete genomic sequences and contributes to the monitoring of evolutionary trends of A/H3N2 influenza viruses within North and Central America.

FluShuffle and FluResort: new algorithms to identify reassorted strains of the influenza virus by mass spectrometry

BACKGROUND

Influenza is one of the oldest and deadliest infectious diseases known to man. Reassorted strains of the virus pose the greatest risk to both human and animal health and have been associated with all pandemics of the past century, with the possible exception of the 1918 pandemic, resulting in tens of millions of deaths. We have developed and tested new computer algorithms, FluShuffle and FluResort, which enable reassorted viruses to be identified by the most rapid and direct means possible. These algorithms enable reassorted influenza, and other, viruses to be rapidly identified to allow prevention strategies and treatments to be more efficiently implemented.

RESULTS

The FluShuffle and FluResort algorithms were tested with both experimental and simulated mass spectra of whole virus digests. FluShuffle considers different combinations of viral protein identities that match the mass spectral data using a Gibbs sampling algorithm employing a mixed protein Markov chain Monte Carlo (MCMC) method. FluResort utilizes those identities to calculate the weighted distance of each across two or more different phylogenetic trees constructed through viral protein sequence alignments. Each weighted mean distance value is normalized by conversion to a Z-score to establish a reassorted strain.

CONCLUSIONS

The new FluShuffle and FluResort algorithms can correctly identify the origins of influenza viral proteins and the number of reassortment events required to produce the strains from the high resolution mass spectral data of whole virus proteolytic digestions. This has been demonstrated in the case of constructed vaccine strains as well as common human seasonal strains of the virus. The algorithms significantly improve the capability of the proteotyping approach to identify reassorted viruses that pose the greatest pandemic risk.

Reassortment Networks and the evolution of pandemic H1N1 swine-origin influenza

Prior research developed Reassortment Networks to reconstruct the evolution of segmented viruses under both reassortment and mutation. We report their application to the swine-origin pandemic H1N1 virus (S-OIV). A database of all influenza A viruses, for which complete genome sequences were available in Genbank by October 2009, was created and dynamic programming was used to compute distances between all corresponding segments. A reassortment network was created to obtain the minimum cost evolutionary paths from all viruses to the exemplar S-OIV A/California/04/2009. This analysis took 35 hours on the Cray Extreme Multithreading (XMT) supercomputer, which has special hardware to permit efficient parallelization. Six specific H1N1/H1N2 bottleneck viruses were identified that almost always lie on minimum cost paths to S-OIV. We conjecture that these viruses are crucial to S-OIV evolution and worthy of careful study from a molecular biology viewpoint. In phylogenetics, ancestors are typically medians that have no functional constraints. In our method, ancestors are not inferred, but rather chosen from previously observed viruses along a path of mutation and reassortment leading to the target virus. This specificity and functional constraint render our results actionable for further experiments in vitro and in vivo.

Molecular epidemiology of influenza A/H3N2 viruses circulating in Uganda

The increasing availability of complete influenza virus genomes is deepening our understanding of influenza evolutionary dynamics and facilitating the selection of vaccine strains. However, only one complete African influenza virus sequence is available in the public domain. Here we present a complete genome analysis of 59 influenza A/H3N2 viruses isolated from humans in Uganda during the 2008 and 2009 season. Isolates were recovered from hospital-based sentinel surveillance for influenza-like illnesses and their whole genome sequenced. The viruses circulating during these two seasons clearly differed from each other phylogenetically. They showed a slow evolution away from the 2009/10 recommended vaccine strain (A/Brisbane/10/07), instead clustering with the 2010/11 recommended vaccine strain (A/Perth/16/09) in the A/Victoria/208/09 clade, as observed in other global regions. All of the isolates carried the adamantane resistance marker S31N in the M2 gene and carried several markers of enhanced transmission; as expected, none carried any marker of neuraminidase inhibitor resistance. The hemagglutinin gene of the 2009 isolates differed from that of the 2008 isolates in antigenic sites A, B, D, and to a lesser extent, C and E indicating evidence of an early phylogenetic shift from the 2008 to 2009 viruses. The internal genes of the 2009 isolates were similar to those of one 2008 isolate, A/Uganda/MUWRP-050/2008. Another 2008 isolate had a truncated PB1-F2 protein. Whole genome sequencing can enhance surveillance of future seasonal changes in the viral genome which is crucial to ensure that selected vaccine strains are protective against the strains circulating in Eastern Africa. This data provides an important baseline for this surveillance. Overall the influenza virus activity in Uganda appears to mirror that observed in other regions of the southern hemisphere.

GiRaF: robust, computational identification of influenza reassortments via graph mining

Reassortments in the influenza virus—a process where strains exchange genetic segments—have been implicated in two out of three pandemics of the 20th century as well as the 2009 H1N1 outbreak. While advances in sequencing have led to an explosion in the number of whole-genome sequences that are available, an understanding of the rate and distribution of reassortments and their role in viral evolution is still lacking. An important factor in this is the paucity of automated tools for confident identification of reassortments from sequence data due to the challenges of analyzing large, uncertain viral phylogenies. We describe here a novel computational method, called GiRaF (Graph-incompatibility-based Reassortment Finder), that robustly identifies reassortments in a fully automated fashion while accounting for uncertainties in the inferred phylogenies. The algorithms behind GiRaF search large collections of Markov chain Monte Carlo (MCMC)-sampled trees for groups of incompatible splits using a fast biclique enumeration algorithm coupled with several statistical tests to identify sets of taxa with differential phylogenetic placement. GiRaF correctly finds known reassortments in human, avian, and swine influenza populations, including the evolutionary events that led to the recent ‘swine flu’ outbreak. GiRaF also identifies several previously unreported reassortments via whole-genome studies to catalog events in H5N1 and swine influenza isolates.

A survey of combinatorial methods for phylogenetic networks

The evolutionary history of a set of species is usually described by a rooted phylogenetic tree. Although it is generally undisputed that bifurcating speciation events and descent with modifications are major forces of evolution, there is a growing belief that reticulate events also have a role to play. Phylogenetic networks provide an alternative to phylogenetic trees and may be more suitable for data sets where evolution involves significant amounts of reticulate events, such as hybridization, horizontal gene transfer, or recombination. In this article, we give an introduction to the topic of phylogenetic networks, very briefly describing the fundamental concepts and summarizing some of the most important combinatorial methods that are available for their computation.