CLUSTOM-CLOUD: In-Memory Data Grid-Based Software for Clustering 16S rRNA Sequence Data in the Cloud Environment

Abstract

High-throughput sequencing can produce hundreds of thousands of 16S rRNA sequence reads corresponding to different organisms present in the environmental samples. Typically, analysis of microbial diversity in bioinformatics starts from pre-processing followed by clustering 16S rRNA reads into relatively fewer operational taxonomic units (OTUs). The OTUs are reliable indicators of microbial diversity and greatly accelerate the downstream analysis time. However, existing hierarchical clustering algorithms that are generally more accurate than greedy heuristic algorithms struggle with large sequence datasets. To keep pace with the rapid rise in sequencing data, we present CLUSTOM-CLOUD, which is the first distributed sequence clustering program based on In-Memory Data Grid (IMDG) technology-a distributed data structure to store all data in the main memory of multiple computing nodes. The IMDG technology helps CLUSTOM-CLOUD to enhance both its capability of handling larger datasets and its computational scalability better than its ancestor, CLUSTOM, while maintaining high accuracy. Clustering speed of CLUSTOM-CLOUD was evaluated on published 16S rRNA human microbiome sequence datasets using the small laboratory cluster (10 nodes) and under the Amazon EC2 cloud-computing environments. Under the laboratory environment, it required only ~3 hours to process dataset of size 200 K reads regardless of the complexity of the human microbiome data. In turn, one million reads were processed in approximately 20, 14, and 11 hours when utilizing 20, 30, and 40 nodes on the Amazon EC2 cloud-computing environment. The running time evaluation indicates that CLUSTOM-CLOUD can handle much larger sequence datasets than CLUSTOM and is also a scalable distributed processing system. The comparative accuracy test using 16S rRNA pyrosequences of a mock community shows that CLUSTOM-CLOUD achieves higher accuracy than DOTUR, mothur, ESPRIT-Tree, UCLUST and Swarm. CLUSTOM-CLOUD is written in JAVA and is freely available at http://clustomcloud.kopri.re.kr.

Fig 1. System architecture.

CLUSTOM-CLOUD consists of Application and Cluster units. Application is composed of Job Tracker and Data Manager. Job Tracker assigns Task Tracker to each Cluster Node in Cluster and checks its status. Task Tracker processes a distributed task in parallel using multi-threads. Data manager manages processed results and generates clustering results. Cluster is a set of N-nodes, which are unified by IMDG. Cluster is composed of Cluster Node and Task Tracker. A part of RAM in each Cluster Node is assigned to IMDG data structure and backup area.

Fig 2. Schematic diagram of clustering workflow.

16S rRNA sequences in FASTA format are provided as input. Each input file, already checked for low-quality and chimera errors, is pre-processed by the removal of duplicates and transformation of k-mer into numeric values. A fixed number of sequence pairs are distributed to each cluster node for k-mer (initial) and NW (refinement) distance calculation. Processed results are merged upon completion of each unit task. Clusters are determined based on criteria described previously [11] and in text. Output files are created and data are cleared from memory.

Fig 3. Representation of k-mer transformation method.

The diagram summarizes the layout of the k-mer transformation method. (A) All k-mer strings in the input sequence dataset along with non-redundant numeric values are loaded into hash map. (B) All k-mer in each sequence are replaced with numeric values corresponding to each key in hash map.

Fig 4. Fine-grained task distribution in CLUSTOM-CLOUD.

The figure summarizes the workflow of distributed processing in CLUSTOM-CLOUD. (A) The number of all possible sequence pairs that need to be compared for distance calculation is represented as a right-angled triangle; n represents the total number of sequences. (B) A chunk-size based on system granularity is determined to distribute only a fixed number of sequence pairs (shown here with 2 K) to each cluster node. (C) Each task (e.g., T_i) is assigned to nodes from top to bottom and left to right. (D) Each node takes and processes tasks in the order of task priority. (E) The assigned task (T_i) is divided into smaller sub-tasks (t_j) and processed in parallel using multi-threads (w_k) depending on the number of threads on the cluster node.

Fig 5. Running time and memory usage evaluation of the k-mer transformation method.

Comparison of the memory usage (A) and running time (B) were performed with and without k-mer transformation method only at the k-mer distance calculation step. Two of 100K 16S sequences were independently and randomly extracted from the sequence datasets of high-, intermediate- and low-complexity. For each of the six different sequence datasets, the running time and memory usage were measured three times independently.

Fig 6. Running time of the whole process according to the complexity of the microbial diversity.

Running time (A) and memory usage (B) of CLUSTOM-CLOUD were measured by analyzing 50 K, 100 K, 150 K, and 200 K sequences in high-, intermediate-, and low-complexity datasets (3% distance threshold). The measures were repeated three times per dataset and the average values are plotted.

Fig 7. Comparative accuracy test of existing clustering programs.

The clustering accuracy of CLUSTOM, CLUSTOM-CLOUD, DOTUR-AL-PSA, ESPRIT-Tree, mothur-AL-PSA, mothur-AL-MSA, UCLUST and Swarm was performed based on 16S rRNA pyrosequences of a mock community that was constructed by pooled DNA of 21 human-associated prokaryotic strains with even concentration (HMP-Mock-community). The precision and recall metrics as well as their F₂ values were used to compare the clustering accuracy of the eight programs at the species (A) and genus (B) levels.