title: Acceleration of sequence clustering using longest common subsequence filtering.
abstract: BACKGROUND
  Huge numbers of genomes can now be sequenced rapidly with recent improvements in sequencing throughput. However, data analysis methods have not kept up, making it difficult to process the vast amounts of available sequence data. This increased processing time is especially critical in DNA sequence clustering because of the intrinsic difficulty in parallelization. Thus, there is a strong demand for a faster clustering algorithm.
  
  
  RESULTS
  We developed a new fast DNA sequence clustering method called LCS-HIT, based on the popular CD-HIT program. The proposed method uses a novel filtering technique based on the longest common subsequence to identify similar sequence pairs. This filtering technique makes the LCS-HIT considerably faster than CD-HIT, without loss of sensitivity. For a dataset of two million DNA sequences, our method was approximately 7.1, 4.4, and 2.2 times faster than CD-HIT for 100, 150, and 400 bases, respectively.
  
  
  CONCLUSIONS
  The LCS-HIT clustering program, using a novel filtering technique based on the longest common subsequence, is significantly faster than CD-HIT without compromising clustering accuracy. Moreover, the filtering technique itself is independent from the CD-HIT algorithm. Thus, this technique can be applied to similar clustering algorithms.
authors.affiliation: Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Ookayama, Meguro, Tokyo 152-8552, Japan.
authors.forename: Youhei
authors.initials: Y
authors.lastname: Namiki
authors.forename: Takashi
authors.initials: T
authors.lastname: Ishida
authors.forename: Yutaka
authors.initials: Y
authors.lastname: Akiyama
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D057225:Data Mining; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software