Swarm v2: highly-scalable and high-resolution amplicon clustering.
Mahé F, Rognes T, Quince C, de Vargas C, Dunthorn M. · 2015
Read Swarm v2: highly-scalable and high-resolution amplicon clustering. by Mahé F, Rognes T, Quince C, de Vargas C, Dunthorn M. (2015) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc4690345.txt.
Introduction
Frédéric Mahé, Torbjørn Rognes, Christopher Quince, and three colleagues presented Swarm v2 in PeerJ in 2015. Swarm is free software that groups DNA reads from environmental samples into clusters standing for species-like units. Older methods used one fixed similarity cutoff for all data, which fits some groups badly, and their results could shift with input order. Swarm avoids a global cutoff by linking reads step by step at a small local distance.
Version two adds two things. A new fast routine for the tightest clustering makes run time grow in step with data size, so huge datasets stay manageable. A fastidious option then attaches rare lone reads to bigger clusters, reducing split groups. Clustering and cleanup now run in one pass, with outputs ready for analysis. The upgrade keeps fine detail while scaling to modern sequencing loads.
Catalog record
| CREATOR | Mahé F, Rognes T, Quince C, de Vargas C, Dunthorn M. |
|---|---|
| YEAR | 2015 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Swarm v2: highly-scalable and high-resolution amplicon clustering By Frédéric Mahé, Torbjørn Rognes, Christopher Quince, Colomban de Vargas, Micah Dunthorn, Gilles van Wezel Published in: PeerJ DOI: 10.7717/peerj.1420 ABSTRACT Previously we presented Swarm v1, a novel and open source amplicon clustering program that produced fine-scale molecular operational taxonomic units (OTUs), free of arbitrary global clustering thresholds and input-order dependency. Swarm v1 worked with an initial phase that used iterative single-linkage with a local clustering threshold (d), followed by a phase that used the internal abundance structures of clusters to break chained OTUs. Here we present Swarm v2, which has two important novel features: (1) a new algorithm for d = 1 that allows the computation time of the program to scale linearly with increasing amounts of data; and (2) the new fastidious option that reduces under-grouping by grafting low abundant OTUs (e.g., singletons and doubletons) onto larger ones. Swarm v2 also directly integrates the clustering and breaking phases, dereplicates sequencing reads with d = 0, outputs OTU representatives in fasta format, and plots individual OTUs as two-dimensional networks. INTRODUCTION Traditional de novo amplicon clustering methods that can handle large high-throughput sequencing datasets (e.g., Edgar, 2010; Ghodsi, Liu & Pop, 2011; Fu et al., 2012) suffer from two fundamental problems. First, they rely on an arbitrary fixed global clustering threshold to group amplicons into molecular operational taxonomic units (OTUs). Global clustering thresholds have rarely been justified and are not applicable to all taxa and marker lengths (e.g., Caron et al., 2009; Nebel et al., 2011; Dunthorn et al., 2012; Brown et al., 2015). Second, there is variability in the clustering results due to amplicon input order (Koeppel & Wu, 2013; Mahé et al., 2014). To solve these problems, we previously introduced the open source Swarm v1 program that implemented an initial clustering phase written in C+ +, then a breaking phase written in Python (Mahé et al., 2014). Swarm’s clustering phase (Fig. 1A) was novel in its approach to single linkage clustering in that, instead of using a global clustering (e.g., Hartmann et al., 2012; Huse et al., 2010), amplicons were iteratively added together using a small local clustering threshold (d) until no more amplicons could be added. Using d = 1 produced the highest resolution OTUs. Swarm’s breaking phase (Fig. 1B) was novel in that it used the abundance of amplicons to reveal the internal structure of potentially chained OTUs (i.e., a low abundant link between high abundant amplicons). These chained OTUs were then refined by splitting them. [Figure: Schematic view of Swarm’s clustering and refinement approach.(A) Swarm clusters amplicons iteratively by using a small user-chosen local threshold, d, allowing OTUs to grow to their natural limits, where no other amplicons can be added. (B) Swarm takes into account the abundance of each amplicon to produce higher resolution clusters, by not allowing the formation of amplicon chains. The darker the red, the higher the abundance. (C) The fastidious option avoids under-grouping (e.g., the production of small OTUs such as singletons and doubletons) by postulating the existence of virtual linking amplicons to graft smaller OTUs onto larger ones.] Since its introduction, Swarm v1 has been used in a variety of datasets (De Vargas et al., 2015; Filker et al., 2015; Lima-Mendez et al., 2015; Mahé et al., 2015; Oikonomou et al., 2015). However, since the breaking phase was written in Python, it lacked scalability and was cumbersome to use. Kopylova et al. (pers. comm., 2015) also found that in comparison to other clustering methods, Swarm v1 tended to produce relatively more low abundant OTUs; e.g., singletons and doubletons. And most importantly, Swarm v1 and other current de novo algorithms could not cluster today’s largest high-throughout sequencing datasets within a reasonable amount of time (Rideout et al., 2014). Here we introduce Swarm v2 to help solve these problems, as well as to introduce new and useful features. MATERIAL AND METHODS Linear complexity de novo clustering approach Today’s largest amplicon datasets contain hundreds of millions of amplicons and pose a computational challenge to de novo clustering methods. Because of this scalability problem, Rideout et al. (2014) proposed using a mixed clustering approach with an initial closed-reference clustering that compares the amplicons to what is known in taxonomic reference databases to capture most of the data, followed by a de novo clustering with the remaining amplicons. We feel that using only de novo clustering is the most powerful approach when working with amplicons from unexplored environments that lack sufficient taxonomic reference databases, or with rare taxa that were previously missed in already-sampled environments. We therefore worked to improve Swarm’s scalability. Like other current de novo clustering approaches, Swarm v1 presented an apparent quadratic behavior in that it needs to perform a number of comparisons that grows as the square of the number of amplicons. In Swarm v2, we first reduced computational time by improving the multithreading and making a better usage of multi-core CPUs. We further reduced computational time by using a novel algorithmic approach. This linear complexity approach only applies for d = 1, which is Swarm’s default and preferred parameter as it produces the highest resolution clusters. As background to this linear approach, let us consider a nucleic sequence S made of As, Cs, Gs and Ts. A “microvariant” is a sequence with one difference (d = 1) to the original sequence S. How many distinct microvariants can derive from S? In a sequence S of length L, each position can be substituted with 3 different bases, so there are 3L possible microvariants due to substitutions. Each position in S can be deleted once, so there are L possible microvariants due to deletions. Insertions are more complicated. An insertion can happen before or after each position in the sequence S, and four different nucleotides can be inserted resulting in 4(L + 1) microvariants. However, some insertions will result in the same microvariant: for example, inserting a “G” before or after a “G” will result in the same sequence “GG.” As that situation arises for all positions in S but one, the maximum number of distinct insertions is not 4(L + 1), but 3(L + 1) + 1 = 3L + 4. In total, the maximum number of microvariants that can be obtained from a given sequence S of length L is 3L + L + 3L + 4 = 7L + 4. As stated above, different sequence modifications can produce the same microvariant. The final number of distinct microvariants depends on the number of homopolymer stretches in the sequence. In the extreme situation where the sequence is entirely made of one type of nucleotide, the number of microvariants due to deletions drops from L to 1. For example, if S is entirely made of “G,” all possible deletions yield the same microvariant. The total number of distinct microvariants then drops to its minimum value: 3L + 1 + 3(L + 1) + 1 = 6L + 5. The number of distinct microvariants that can be obtained from a sequence S of length L then varies from 6L + 5 to 7L + 4. In practice, it means that a typical high-throughput sequencing 16S rRNA sequence of 130 nucleotides will yield at least 785