Recycler: an algorithm for detecting plasmids from de novo assembly graphs

Abstract

Motivation: Plasmids and other mobile elements are central contributors to microbial evolution and genome innovation. Recently, they have been found to have important roles in antibiotic resistance and in affecting production of metabolites used in industrial and agricultural applications. However, their characterization through deep sequencing remains challenging, in spite of rapid drops in cost and throughput increases for sequencing. Here, we attempt to ameliorate this situation by introducing a new circular element assembly algorithm, leveraging assembly graphs provided by a conventional de novo assembler and alignments of paired-end reads to assemble cyclic sequences likely to be plasmids, phages and other circular elements.

Results: We introduce Recycler, the first tool that can extract complete circular contigs from sequence data of isolate microbial genomes, plasmidome and metagenome sequence data. We show that Recycler greatly increases the number of true plasmids recovered relative to other approaches while remaining highly accurate. We demonstrate this trend via simulations of plasmidomes, comparisons of predictions with reference data for isolate samples, and assessments of annotation accuracy on metagenome data. In addition, we provide validation by DNA amplification of 77 plasmids predicted by Recycler from the different sequenced samples in which Recycler showed mean accuracy of 89% across all data types-isolate, microbiome and plasmidome.

Availability and implementation: Recycler is available at http://github.com/Shamir-Lab/Recycler.

Contact: imizrahi@bgu.ac.il.

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Recycler work-flow. An example is shown of generating candidate cycles and peeling off cycles iteratively. For simplicity, all lengths are assumed to be equal and not shown. Here, we consider only candidate cycles that pass through vertex x, but ordinarily such candidates would be generated for each vertex in the component, and the cycle with lowest CV will be chosen and peeled off. (A) The assembly graph. (B) A single component is selected from the assembly graph (framed in A) and represented with vertices for contigs and edges for connecting k-mers. (C) The reduced component after tip removal. The numbers next to vertices are their observed contig coverage. Since vertex x has two incoming edges from vertices b and c, two candidate cycles are generated that pass through edges (b, x) and (c, x), respectively. This is done by computing shortest paths from x to b$(x,e,d,g,h,i,j,b,CV=0.20,\hspace{0.17em}\text{shown}\hspace{0.17em}\text{in}\hspace{0.17em}\mathrm{D})$ and from x to c$(x,e,d,g,h,c,CV=0.41,\hspace{0.17em}\text{not}\hspace{0.17em}\text{shown}\hspace{0.17em})$. Two successive steps of peeling cycles are shown with their respective latent coverage assignments. First, the cycle in D is peeled off because the CV calculated from initially observed coverage is lowest for this cycle. Uncolored vertices correspond to contigs with zero coverage that are removed

Fig. 2

Methods performance on simulated data. Results are shown for SPAdes without repeat resolution (RR), SPAdes with repeat resolution, the method of Jørgensen et al., and Recycler. The contigs of SPAdes before RR were used as input for the three other methods. Recycler also relied on the graph produced at this stage. F1 score calculation is described in the main text. The x axis shows the number of simulated reference sequences in each case

Fig. 3.

PCR based validation of Recycler’s plasmid predictions. High coverage: 60–1000x, med–high:15–60x, med–low: 5–15x, low: 1–5x