The large-scale blast score ratio (LS-BSR) pipeline: a method to rapidly compare genetic content between bacterial genomes

LS-BSR algorithm speed and scalability

To determine the scalability of the LS-BSR method, 1,000 Escherichia coli and Shigella genomes were downloaded from Genbank (Benson et al., 2012); E. coli was used as a test case due to the large number of genomes deposited in Genbank. Genomes were sub-sampled at different depths (100 through 1000, sampling every 100) with a python script (https://gist.github.com/jasonsahl/115d22bfa35ac932d452) and processed with LS-BSR using 16 processors. A plot of wall time and the number of genomes processed demonstrates the scalability of the method (Fig. 1A) using three different alignment methods. To demonstrate the parallel nature of the algorithm, 100 E. coli genomes were processed with different numbers of processors. The results demonstrate decreased runtime of LS-BSR with an increase in the number of processors used (Fig. 1B).

Improvements on a previous BSR implementation

The LS-BSR method is an improvement on a previous BSR implementation (http://bsr.igs.umaryland.edu/) in terms of speed and ease of use. The former BSR algorithm (Rasko, Myers & Ravel, 2005) requires peptide sequences and genomic coordinates of CDSs to run. LS-BSR only requires genome assemblies in FASTA format, which is the standard output of most genome assemblers. To test the speed differences between methods, 10 E. coli genomes (Table S1) were processed with both methods. Using the same number of processors (n = 2) on the same server, the original BSR method took ∼14 h (wall time) to complete, while the LS-BSR method, using TBLASTN, took ∼25 min to complete (wall time). Because the original BSR method is an “all vs. all” comparison and the LS-BSR method is a “one vs. all” comparison, this difference is expected to be more pronounced as the number of genomes analyzed increases.

Test case: analysis of 96 E. coli and Shigella genomes

To demonstrate the utility of the LS-BSR pipeline, a set of 96 E. coli and Shigella genomes were processed (Table S1); these genomes are in various stages of assembly completeness and have been generated with various sequencing technologies from Sanger to Illumina. The BSR matrix was generated with TBLASTN in 2 h 34 min from a set of ∼20,000 unique CDSs using 16 processors. In addition to the LS-BSR analysis, a core genome single nucleotide polymorphism (SNP) phylogeny was inferred on 96 genomes using methods published previously (Sahl et al., 2011); the SNP phylogeny with labels is shown in Fig. S1. Briefly, all genomes were aligned with Mugsy (Angiuoli & Salzberg, 2011) and the core genome was extracted from the whole genome alignment; the alignment file was then converted into a multiple sequence alignment in FASTA format. Gaps in the alignment were removed with Mothur (Schloss et al., 2009) and a phylogeny was inferred on the reduced alignment with FastTree2 (Price, Dehal & Arkin, 2010).

The compare_ BSR.py script included with LS-BSR was used to identity CDS markers that are unique to specific phylogenetic clades (Fig. 2). Identified CDSs had a BSR value ⩾0.8 in targeted genomes and a BSR value <0.4 in non-targeted genomes; the gene annotation of all marker CDSs is detailed in Table S2. The conservation and distribution of all clade-specific markers was visualized by correlating the phylogeny with a heatmap of BSR values (Fig. 2). This presentation provides an easy way for the user to highlight features conserved in one or more phylogenomic clades.

E. coli and Shigella pathogenic variants (pathovars) are delineated by the presence of genetic markers primarily present on mobile genetic elements (Rasko et al., 2008). The conservation of these markers was used as a validation of the LS-BSR method. A representative sequence from each pathovar-specific marker (Table S2) was screened against the 96-genome test set and the BSR values (Table S3) were visualized as a heatmap (Fig. 2). The BSR matrix demonstrates that pathovar-specific genes were accurately identified in each targeted genome (Table S3, Fig. 2). For example, the ipaH3 marker was positively identified in all Shigella genomes and the Shiga toxin gene (stx2a) was conserved in the clade including O157:H7 E. coli (Fig. 2). A sub-set of these 96 E. coli genomes is included with LS-BSR as test data to characterize the conservation and distribution of pathovar specific genes.

Finally, the BSR values were used to cluster all 96 genomes with an average linkage algorithm implemented in MeV and the structure of the resulting dendrogram was compared to the core SNP phylogeny. The BSR based clustering method incorporates both the core and accessory genome, while the SNP phylogeny relies on core genomic regions alone. A comparison of the tree structures demonstrates that while Shigella genomes share a diverse evolutionary history (Fig. 3A), they all cluster together based on gene presence and conservation (Fig. 3B). This result was also observed using a k-mer frequency method (Sims & Kim, 2011), which uses all possible k-mer values to infer a phylogeny and validates the findings of the LS-BSR pipeline. The dendrogram also differed from the core SNP phylogeny in other genomes, which could represent either assembly problems, or more likely the acquisition of accessory genomic regions that are not a product of direct descent.

The functionality of LS-BSR was compared to recently released pan-genome software packages including GET_HOMOLOGUES (Contreras-Moreira & Vinuesa, 2013), ITEP (Benedict et al., 2014), and PGAP (Zhao et al., 2012). A set of 11 Streptococcus pyogenes genomes was chosen for the comparative analysis, as it was also used as a test set in the PGAP publication; the comparative analysis and results are shown in Table 1. Overall, the size of the core genome was comparable between methods, with LS-BSR (BLASTN) and GET_HOMOLOGUES calculating differing core genome numbers compared to the other methods. However, small differences were expected due to differing thresholds and clustering algorithms. Based on these results, LS-BSR represent a significant improvement in terms of speed and ease of use compared to comparable methods, while having comparable utility.

Pan-genome analyses

One application in comparative genomics is the analysis of the pan-genome, or the combined genome, of isolates within a species. Post matrix-building scripts are available to visualize the pan-genome of a given dataset. One script (BSR_ to_ PANGP.py) creates a matrix compatible with PanGP (Zhao et al., 2014), for visualization of pan-genome statistics. The pan_ genome_ stats.py script provides data that can be used to visualize the conservation of CDSs at different genome depths (Fig. 4A). An additional script randomly subsamples the CDS distribution at all depths and produces data that can be plotted to visualize core genome convergence (Fig. 4B), accumulation of CDSs (Fig. 4C), and the number of unique CDSs for each genome analyzed (Fig. 4D). All analyses were conducted on a set of 100 E. coli genomes, with 100 iterations.