Parsimony via consensus

Pathogenomes and variations in Shiga toxin production among geographically distinct clones of Escherichia coli O113:H21

Infections with globally disseminated Shiga toxin-producing Escherichia coli (STEC) of the O113:H21 serotype can progress to severe clinical complications, such as hemolytic uremic syndrome (HUS). Two phylogeographically distinct clonal complexes have been established by multi locus sequence typing (MLST). Infections with ST-820 isolates circulating exclusively in Australia have caused severe human disease, such as HUS. Conversely, ST-223 isolates prevalent in the US and outside Australia seem to rarely cause severe human disease but are frequent contaminants. Following a genomic epidemiology approach, we wanted to gain insights into the underlying cause for this disparity. We examined the plasticity in the genome make-up and Shiga toxin production in a collection of 20 ST-820 and ST-223 strains isolated from produce, the bovine reservoir, and clinical cases. STEC are notorious for assembly into fragmented draft sequences when using short-read sequencing technologies due to the extensive and partly homologous phage complement. The application of long-read technology (LRT) sequencing yielded closed reference chromosomes and plasmids for two representative ST-820 and ST-223 strains. The established high-resolution framework, based on whole genome alignments, single nucleotide polymorphism (SNP)-typing and MLST, includes the chromosomes and plasmids of other publicly available O113:H21 sequences and allowed us to refine the phylogeographical boundaries of ST-820 and ST-223 complex isolates and to further identify a historic non-shigatoxigenic strain from Mexico as a quasi-intermediate. Plasmid comparison revealed strong correlations between the strains' featured pO113 plasmid genotypes and chromosomally inferred ST, which suggests coevolution of the chromosome and virulence plasmids. Our pathogenicity assessment revealed statistically significant differences in the Stx_2a-production capabilities of ST-820 as compared to ST-223 strains under RecA-induced Stx phage mobilization, a condition that mimics Stx-phage induction. These observations suggest that ST-820 strains may confer an increased pathogenic potential in line with the strain-associated epidemiological metadata. Still, some of the tested ST-223 cultures sourced from contaminated produce or the bovine reservoir also produced Stx at levels comparable to those of ST-820 isolates, which calls for awareness and for continued surveillance of this lineage.

A reconsideration of inapplicable characters, and an approximation with step-matrix recoding

Evidence for phylogenetic analysis comes in the form of observed similarities, and trees are selected to minimize the number of similarities that cannot be accounted for by homology (homoplasies). Thus, the classical argument for parsimony directly links homoplasy with explanatory power. When characters are hierarchically related, a first character may represent a primary structure such as tail absence/presence and a secondary (subordinate) character may describe tail colour; this makes tail colour inapplicable when tail is absent. It has been proposed that such character hierarchies should be evaluated on the same logical basis as standard characters, maximizing the number of similarities accounted for by secondary homology, i.e. common ancestry. Previous evaluations of the homology of a given ancestral reconstruction contain the unintuitive quantity "subcharacters" (number of regions of applicability). Rather than counting subcharacters, this paper proposes an equivalent but more intuitive formulation, based on counting the number of changes into each separate state. In this formulation, x-transformations, the homoplasy for the reconstruction is simply the number of changes into the state beyond the first, summed over all states. There is thus no direct connection between homoplasy and number of steps, only between homoplasy and extra steps. The link between the two formulations is that, for any region of applicability of any character, a subcharacter can be interpreted as the change into the state that is plesiomorphic in that region. Although some authors have claimed that the equivalence between maximizing explanatory power and minimizing independent originations of similar features (i.e. the standard justification of parsimony) does not hold for inapplicable characters, evaluating homoplasy with x-transformations clearly connects the two sides of that equation. Furthermore, as the evaluation with x-transformations provides a direct count and a straightforward interpretation of homoplasy, it extends naturally into implied weighting, and sheds light on problems with additive, step-matrix or continuous characters. It also allows deriving transformation costs for recoding hierarchies as step-matrix characters (where recoded states correspond to permissible combinations of states in primary and secondary characters), so that homology of the original observations is properly measured. Those transformation costs set the cost of gaining the primary structure to the maximum difference between "present" states plus cost of loss, and difference between "present" states to the sum of user-defined transformation costs between secondary features. With such recoding, invoking multiple independent derivations of the structure and similar features will cost as many extra "steps" as the instances of similarities (in both original characters) that are not being homologized. The step-matrix recoding also can take into account nested dependences. We present a simple convention for naming characters, which TNT can use to automatically convert the original data into a step-matrix form and set the proper transformation costs. Finally, the basic elements for handling inapplicable characters in the context of maximum-likelihood inference are outlined, and some quantitative comparisons between different approaches to inapplicables are provided.

A new fast method for inferring multiple consensus trees using k-medoids

Background

Gene trees carry important information about specific evolutionary patterns which characterize the evolution of the corresponding gene families. However, a reliable species consensus tree cannot be inferred from a multiple sequence alignment of a single gene family or from the concatenation of alignments corresponding to gene families having different evolutionary histories. These evolutionary histories can be quite different due to horizontal transfer events or to ancient gene duplications which cause the emergence of paralogs within a genome. Many methods have been proposed to infer a single consensus tree from a collection of gene trees. Still, the application of these tree merging methods can lead to the loss of specific evolutionary patterns which characterize some gene families or some groups of gene families. Thus, the problem of inferring multiple consensus trees from a given set of gene trees becomes relevant.

Results

We describe a new fast method for inferring multiple consensus trees from a given set of phylogenetic trees (i.e. additive trees or X-trees) defined on the same set of species (i.e. objects or taxa). The traditional consensus approach yields a single consensus tree. We use the popular k-medoids partitioning algorithm to divide a given set of trees into several clusters of trees. We propose novel versions of the well-known Silhouette and Caliński-Harabasz cluster validity indices that are adapted for tree clustering with k-medoids. The efficiency of the new method was assessed using both synthetic and real data, such as a well-known phylogenetic dataset consisting of 47 gene trees inferred for 14 archaeal organisms.

Conclusions

The method described here allows inference of multiple consensus trees from a given set of gene trees. It can be used to identify groups of gene trees having similar intragroup and different intergroup evolutionary histories. The main advantage of our method is that it is much faster than the existing tree clustering approaches, while providing similar or better clustering results in most cases. This makes it particularly well suited for the analysis of large genomic and phylogenetic datasets.

Calculating the Unrooted Subtree Prune-and-Regraft Distance

The subtree prune-and-regraft (SPR) distance metric is a fundamental way of comparing evolutionary trees. It has wide-ranging applications, such as to study lateral genetic transfer, viral recombination, and Markov chain Monte Carlo phylogenetic inference. Although the rooted version of SPR distance can be computed relatively efficiently between rooted trees using fixed-parameter-tractable maximum agreement forest (MAF) algorithms, no MAF formulation is known for the unrooted case. Correspondingly, previous algorithms are unable to compute unrooted SPR distances larger than 7.

Triplet supertree heuristics for the tree of life

BACKGROUND

There is much interest in developing fast and accurate supertree methods to infer the tree of life. Supertree methods combine smaller input trees with overlapping sets of taxa to make a comprehensive phylogenetic tree that contains all of the taxa in the input trees. The intrinsically hard triplet supertree problem takes a collection of input species trees and seeks a species tree (supertree) that maximizes the number of triplet subtrees that it shares with the input trees. However, the utility of this supertree problem has been limited by a lack of efficient and effective heuristics.

RESULTS

We introduce fast hill-climbing heuristics for the triplet supertree problem that perform a step-wise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. To realize time efficient heuristics we designed the first nontrivial algorithms for two standard search problems, which greatly improve on the time complexity to the best known (naïve) solutions by a factor of n and n2 (the number of taxa in the supertree). These algorithms enable large-scale supertree analyses based on the triplet supertree problem that were previously not possible. We implemented hill-climbing heuristics that are based on our new algorithms, and in analyses of two published supertree data sets, we demonstrate that our new heuristics outperform other standard supertree methods in maximizing the number of triplets shared with the input trees.

CONCLUSION

With our new heuristics, the triplet supertree problem is now computationally more tractable for large-scale supertree analyses, and it provides a potentially more accurate alternative to existing supertree methods.