{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T13:22:27Z","timestamp":1770816147120,"version":"3.50.1"},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"15","license":[{"start":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T00:00:00Z","timestamp":1655337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2017-04963"],"award-info":[{"award-number":["2017-04963"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004063","name":"Knut and Alice Wallenberg Foundation","doi-asserted-by":"publisher","award":["2017.0163"],"award-info":[{"award-number":["2017.0163"]}],"id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014437","name":"Wenner-Gren Foundations","doi-asserted-by":"publisher","award":["UPD2018-0196"],"award-info":[{"award-number":["UPD2018-0196"]}],"id":[{"id":"10.13039\/100014437","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014437","name":"Wenner-Gren Foundations","doi-asserted-by":"publisher","award":["UPD2019-0110"],"award-info":[{"award-number":["UPD2019-0110"]}],"id":[{"id":"10.13039\/100014437","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Faculty of Science, Stockholm University","award":["SU FV-1.2.1-0124-17"],"award-info":[{"award-number":["SU FV-1.2.1-0124-17"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>DNA barcodes are short, random nucleotide sequences introduced into cell populations to track the relative counts of hundreds of thousands of individual lineages over time. Lineage tracking is widely applied, e.g. to understand evolutionary dynamics in microbial populations and the progression of breast cancer in humans. Barcode sequences are unknown upon insertion and must be identified using next-generation sequencing technology, which is error prone. In this study, we frame the barcode error correction task as a clustering problem with the aim to identify true barcode sequences from noisy sequencing data. We present Shepherd, a novel clustering method that is based on an indexing system of barcode sequences using k-mers, and a Bayesian statistical test incorporating a substitution error rate to distinguish true from error sequences.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>When benchmarking with synthetic data, Shepherd provides barcode count estimates that are significantly more accurate than state-of-the-art methods, producing 10\u2013150 times fewer spurious lineages. For empirical data, Shepherd produces results that are consistent with the improvements seen on synthetic data. These improvements enable higher resolution lineage tracking and more accurate estimates of biologically relevant quantities, e.g. the detection of small effect mutations.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>A Python implementation of Shepherd is freely available at: https:\/\/www.github.com\/Nik-Tavakolian\/Shepherd.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac395","type":"journal-article","created":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T14:55:46Z","timestamp":1655391346000},"page":"3710-3716","source":"Crossref","is-referenced-by-count":8,"title":["Shepherd: accurate clustering for correcting DNA barcode errors"],"prefix":"10.1093","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8577-7959","authenticated-orcid":false,"given":"Nik","family":"Tavakolian","sequence":"first","affiliation":[{"name":"Department of Mathematics, Stockholm University , Stockholm 10691, Sweden"}]},{"given":"Jo\u00e3o Guilherme","family":"Fraz\u00e3o","sequence":"additional","affiliation":[{"name":"Department of Zoology, Stockholm University , Stockholm 10691, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0831-7646","authenticated-orcid":false,"given":"Devin","family":"Bendixsen","sequence":"additional","affiliation":[{"name":"Department of Zoology, Stockholm University , Stockholm 10691, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8530-0656","authenticated-orcid":false,"given":"Rike","family":"Stelkens","sequence":"additional","affiliation":[{"name":"Department of Zoology, Stockholm University , Stockholm 10691, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8009-6265","authenticated-orcid":false,"given":"Chun-Biu","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stockholm University , Stockholm 10691, Sweden"}]}],"member":"286","published-online":{"date-parts":[[2022,6,16]]},"reference":[{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1038\/nature07517","article-title":"Accurate whole human genome sequencing using reversible terminator chemistry","volume":"456","author":"Bentley","year":"2008","journal-title":"Nature"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.ygeno.2014.09.005","article-title":"Beyond genome sequencing: lineage tracking with barcodes to study the dynamics of evolution, infection, and cancer","volume":"104","author":"Blundell","year":"2014","journal-title":"Genomics"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1101\/gr.8.3.186","article-title":"Base-calling of automated sequencer traces using phred. II. Error probabilities","volume":"8","author":"Ewing","year":"1998","journal-title":"Genome Res"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1126\/science.1136800","article-title":"Clustering by passing messages between data points","volume":"315","author":"Frey","year":"2007","journal-title":"Science"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1126\/science.aay4199","article-title":"Higher-fitness yeast genotypes are less robust to deleterious mutations","volume":"366","author":"Johnson","year":"2019","journal-title":"Science"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1080\/01621459.1995.10476572","article-title":"Bayes factors","volume":"90","author":"Kass","year":"1995","journal-title":"J. Am. Stat. Assoc"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1038\/nature14279","article-title":"Quantitative evolutionary dynamics using high-resolution lineage tracking","volume":"519","author":"Levy","year":"2015","journal-title":"Nature"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"e113","DOI":"10.7717\/peerj.113","article-title":"Improving transcriptome assembly through error correction of high-throughput sequence reads","volume":"1","author":"Macmanes","year":"2013","journal-title":"PeerJ"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.cbpa.2019.05.014","article-title":"DNA barcodes evolve for high-resolution cell lineage tracing","volume":"52","author":"Masuyama","year":"2019","journal-title":"Curr. Opin. Chem. Biol"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"R112","DOI":"10.1186\/gb-2011-12-11-r112","article-title":"Evaluation of genomic high-throughput sequencing data generated on Illumina HiSeq and Genome Analyzer systems","volume":"12","author":"Minoche","year":"2011","journal-title":"Genome Biol"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1038\/s41586-019-1749-3","article-title":"High-resolution lineage tracking reveals travelling wave of adaptation in laboratory yeast","volume":"575","author":"Nguyen Ba","year":"2019","journal-title":"Nature"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1038\/nature15742","article-title":"Barcoding reveals complex clonal dynamics of de novo transformed human mammary cells","volume":"528","author":"Nguyen","year":"2015","journal-title":"Nature"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"10950","DOI":"10.1038\/s41598-018-29325-6","article-title":"Systematic evaluation of error rates and causes in short samples in next-generation sequencing","volume":"8","author":"Pfeiffer","year":"2018","journal-title":"Sci. Rep"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"17041","DOI":"10.1073\/pnas.2000238117","article-title":"Lineage reconstruction from clonal correlations","volume":"117","author":"Weinreb","year":"2020","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1093\/bioinformatics\/btx655","article-title":"Bartender: a fast and accurate clustering algorithm to count barcode reads","volume":"34","author":"Zhao","year":"2018","journal-title":"Bioinformatics"},{"key":"2023041405352976100_","doi-asserted-by":"crossref","first-page":"1913","DOI":"10.1093\/bioinformatics\/btv053","article-title":"Starcode: sequence clustering based on all-pairs search","volume":"31","author":"Zorita","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btac395\/44251293\/btac395.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/15\/3710\/49884200\/btac395.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/15\/3710\/49884200\/btac395.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,23]],"date-time":"2023-11-23T08:21:53Z","timestamp":1700727713000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/15\/3710\/6609174"}},"subtitle":[],"editor":[{"given":"Christina","family":"Kendziorski","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,6,16]]},"references-count":16,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2022,8,2]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac395","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,8,1]]},"published":{"date-parts":[[2022,6,16]]}}}