title: Starcode: sequence clustering based on all-pairs search.
abstract: BACKGROUND
  The increasing throughput of sequencing technologies offers new applications and challenges for computational biology. In many of those applications, sequencing errors need to be corrected. This is particularly important when sequencing reads from an unknown reference such as random DNA barcodes. In this case, error correction can be done by performing a pairwise comparison of all the barcodes, which is a computationally complex problem.
  
  
  RESULTS
  Here, we address this challenge and describe an exact algorithm to determine which pairs of sequences lie within a given Levenshtein distance. For error correction or redundancy reduction purposes, matched pairs are then merged into clusters of similar sequences. The efficiency of starcode is attributable to the poucet search, a novel implementation of the Needleman-Wunsch algorithm performed on the nodes of a trie. On the task of matching random barcodes, starcode outperforms sequence clustering algorithms in both speed and precision.
  
  
  METHODS
  The C source code is available at http://github.com/gui11aume/starcode.
authors: Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain.
authors: Eduard
authors: E
authors: Zorita
authors: Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain.
authors: Pol
authors: P
authors: Cuscó
authors: Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain.
authors: Guillaume J
authors: GJ
authors: Filion
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
references: Res Microbiol. 1999 Nov-Dec;150(9-10):603-16
references: 10673000
references: Cell. 2013 Aug 15;154(4):914-27
references: 23953119
references: J Mol Biol. 1970 Mar;48(3):443-53
references: 5420325
references: Mol Cell. 2013 Apr 25;50(2):223-35
references: 23562324
references: Curr Opin Struct Biol. 2013 Feb;23(1):100-8
references: 23253355
references: Bioinformatics. 2012 Dec 1;28(23):3150-2
references: 23060610
references: Bioinformatics. 2012 Nov 1;28(21):2732-7
references: 22942077
references: Bioinformatics. 2011 Sep 15;27(18):2502-9
references: 21810899
references: Nucleic Acids Res. 2011 Jul;39(13):e90
references: 21576222
references: Bioinformatics. 2011 Feb 15;27(4):464-70
references: 21148542
references: Nat Biotechnol. 2009 Jul;27(7):667-70
references: 19561594
references: Science. 2009 Jan 2;323(5910):133-8
references: 19023044
references: J Exp Med. 2008 Sep 29;205(10):2309-18
references: 18809713
references: Nucleic Acids Res. 2008 Sep;36(16):e105
references: 18660515
references: Nature. 2005 Sep 15;437(7057):376-80
references: 16056220