Zorita, EduardCuscó Pons, Pol, 1987-Filion, Guillaume2015-11-112015-11-112015Zorita E, Cuscó P, Filion GJ. Starcode: sequence clustering based on all-pairs search. Bioinformatics. 2015;31(12):1913-9. DOI: 10.1093/bioinformatics/btv0531367-4803http://hdl.handle.net/10230/25055Motivation: The increasing throughput of sequencing technologies offers new applications and challenges for computational biology. In many of those applications, sequencing errors need to be/ncorrected. 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/nof 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. Availability and implementation: The C source code is available at http://github.com/gui11aume/starcode.application/pdfeng© The Author 2014. Published by Oxford University Press. This is an open access article published under a Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited.BioinformàticaBiologia computacionalinfo:eu-repo/semantics/articlehttp://dx.doi.org/10.1093/bioinformatics/btv053info:eu-repo/semantics/openAccess