{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T11:13:02Z","timestamp":1786446782810,"version":"3.56.0"},"reference-count":18,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":610,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: 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.<\/jats:p>\n               <jats:p>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\u2013Wunsch 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.<\/jats:p>\n               <jats:p>Availability and implementation: The C source code is available at http:\/\/github.com\/gui11aume\/starcode.<\/jats:p>\n               <jats:p>Contact: \u00a0guillaume.filion@gmail.com<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv053","type":"journal-article","created":{"date-parts":[[2015,2,1]],"date-time":"2015-02-01T01:28:41Z","timestamp":1422754121000},"page":"1913-1919","source":"Crossref","is-referenced-by-count":236,"title":["Starcode: sequence clustering based on all-pairs search"],"prefix":"10.1093","volume":"31","author":[{"given":"Eduard","family":"Zorita","sequence":"first","affiliation":[{"name":"1 Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and 2Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain"},{"name":"1 Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and 2Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pol","family":"Cusc\u00f3","sequence":"additional","affiliation":[{"name":"1 Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and 2Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain"},{"name":"1 Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and 2Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guillaume J.","family":"Filion","sequence":"additional","affiliation":[{"name":"1 Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and 2Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain"},{"name":"1 Genome Architecture, Gene Regulation, Stem Cells and Cancer Programme, Centre for Genomic Regulation (CRG), Dr. Aiguader 88, 08003 Barcelona and 2Universitat Pompeu Fabra (UPF), 08002 Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,1,31]]},"reference":[{"key":"2023020115133803500_btv053-B1","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.cell.2013.07.018","article-title":"Chromatin position effects assayed by thousands of reporters integrated in parallel","volume":"154","author":"Akhtar","year":"2013","journal-title":"Cell"},{"key":"2023020115133803500_btv053-B2","doi-asserted-by":"crossref","first-page":"2502","DOI":"10.1093\/bioinformatics\/btr447","article-title":"SEED: efficient clustering of next-generation sequences","volume":"27","author":"Bao","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020115133803500_btv053-B3","doi-asserted-by":"crossref","first-page":"2732","DOI":"10.1093\/bioinformatics\/bts482","article-title":"Rainbow: an integrated tool for efficient clustering and assembling RAD-seq reads","volume":"28","author":"Chong","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020115133803500_btv053-B4","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.sbi.2012.11.006","article-title":"RRM-RNA recognition: NMR or crystallography and new findings","volume":"23","author":"Daubner","year":"2013","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023020115133803500_btv053-B5","doi-asserted-by":"crossref","first-page":"e105","DOI":"10.1093\/nar\/gkn425","article-title":"Substantial biases in ultra-short read data sets from high-throughput DNA sequencing","volume":"36","author":"Dohm","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023020115133803500_btv053-B6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1126\/science.1162986","article-title":"Real-time DNA sequencing from single polymerase molecules","volume":"323","author":"Eid","year":"2009","journal-title":"Science"},{"key":"2023020115133803500_btv053-B7","doi-asserted-by":"crossref","first-page":"3150","DOI":"10.1093\/bioinformatics\/bts565","article-title":"CD-HIT: accelerated for clustering the next-generation sequencing data","volume":"28","author":"Fu","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020115133803500_btv053-B8","volume-title":"Information Theory, Inference & Learning Algorithms","author":"MacKay","year":"2002"},{"key":"2023020115133803500_btv053-B9","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1038\/nature03959","article-title":"Genome sequencing in microfabricated high-density picolitre reactors","volume":"437","author":"Margulies","year":"2005","journal-title":"Nature"},{"key":"2023020115133803500_btv053-B10","doi-asserted-by":"crossref","first-page":"e90","DOI":"10.1093\/nar\/gkr344","article-title":"Sequence-specific error profile of Illumina sequencers","volume":"39","author":"Nakamura","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023020115133803500_btv053-B11","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"2023020115133803500_btv053-B12","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.molcel.2013.03.001","article-title":"Genome-wide analysis reveals SR protein cooperation and competition in regulated splicing","volume":"50","author":"Pandit","year":"2013","journal-title":"Mol. Cell"},{"key":"2023020115133803500_btv053-B13","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1038\/nbt.1550","article-title":"Rapid and systematic analysis of the RNA recognition specificities of RNA-binding proteins","volume":"27","author":"Ray","year":"2009","journal-title":"Nat. Biotechnol."},{"key":"2023020115133803500_btv053-B14","doi-asserted-by":"crossref","first-page":"2309","DOI":"10.1084\/jem.20072462","article-title":"Dissecting T cell lineage relationships by cellular barcoding","volume":"205","author":"Schepers","year":"2008","journal-title":"J. Exp. Med."},{"key":"2023020115133803500_btv053-B15","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1093\/bioinformatics\/btq677","article-title":"SlideSort: all pairs similarity search for short reads","volume":"27","author":"Shimizu","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020115133803500_btv053-B16","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1016\/S0923-2508(99)00130-8","article-title":"DNA uptake signal sequences in naturally transformable bacteria","volume":"150","author":"Smith","year":"1999","journal-title":"Res. Microbiol."},{"key":"2023020115133803500_btv053-B17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-line construction of suffix trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"2023020115133803500_btv053-B18","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","article-title":"Fast text searching: allowing errors","volume":"35","author":"Wu","year":"1992","journal-title":"Commun. ACM"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/12\/1913\/49014295\/bioinformatics_31_12_1913.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/12\/1913\/49014295\/bioinformatics_31_12_1913.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:03:08Z","timestamp":1675296188000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/12\/1913\/213875"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,31]]},"references-count":18,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv053","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,6,15]]},"published":{"date-parts":[[2015,1,31]]}}}