title: SEED: efficient clustering of next-generation sequences.
abstract: BACKGROUND
  Similarity clustering of next-generation sequences (NGS) is an important computational problem to study the population sizes of DNA/RNA molecules and to reduce the redundancies in NGS data. Currently, most sequence clustering algorithms are limited by their speed and scalability, and thus cannot handle data with tens of millions of reads.
  
  
  RESULTS
  Here, we introduce SEED-an efficient algorithm for clustering very large NGS sets. It joins sequences into clusters that can differ by up to three mismatches and three overhanging residues from their virtual center. It is based on a modified spaced seed method, called block spaced seeds. Its clustering component operates on the hash tables by first identifying virtual center sequences and then finding all their neighboring sequences that meet the similarity parameters. SEED can cluster 100 million short read sequences in <4 h with a linear time and memory performance. When using SEED as a preprocessing tool on genome/transcriptome assembly data, it was able to reduce the time and memory requirements of the Velvet/Oasis assembler for the datasets used in this study by 60-85% and 21-41%, respectively. In addition, the assemblies contained longer contigs than non-preprocessed data as indicated by 12-27% larger N50 values. Compared with other clustering tools, SEED showed the best performance in generating clusters of NGS data similar to true cluster results with a 2- to 10-fold better time performance. While most of SEED's utilities fall into the preprocessing area of NGS data, our tests also demonstrate its efficiency as stand-alone tool for discovering clusters of small RNA sequences in NGS data from unsequenced organisms.
  
  
  BACKGROUND
  The SEED software can be downloaded for free from this site: http://manuals.bioinformatics.ucr.edu/home/seed.
  
  
  BACKGROUND
  thomas.girke@ucr.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA.
authors.forename: Ergude
authors.initials: E
authors.lastname: Bao
authors.forename: Tao
authors.initials: T
authors.lastname: Jiang
authors.forename: Isgouhi
authors.initials: I
authors.lastname: Kaloshian
authors.forename: Thomas
authors.initials: T
authors.lastname: Girke
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D016000:Cluster Analysis; D016678:Genome; D035683:MicroRNAs; D017421:Sequence Analysis / Q000379:methods*; D017423:Sequence Analysis, RNA; D012984:Software; D059467:Transcriptome
chemical_list: D035683:MicroRNAs