{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T19:08:29Z","timestamp":1773169709099,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,6,7]],"date-time":"2024-06-07T00:00:00Z","timestamp":1717718400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,7]],"date-time":"2024-06-07T00:00:00Z","timestamp":1717718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["DP1GM133052"],"award-info":[{"award-number":["DP1GM133052"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["RF1MH128861"],"award-info":[{"award-number":["RF1MH128861"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM124401"],"award-info":[{"award-number":["R01GM124401"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG012926"],"award-info":[{"award-number":["R01HG012926"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["DP1GM133052"],"award-info":[{"award-number":["DP1GM133052"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["RF1MH128861"],"award-info":[{"award-number":["RF1MH128861"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM124401"],"award-info":[{"award-number":["R01GM124401"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG012926"],"award-info":[{"award-number":["R01HG012926"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["DP1GM133052"],"award-info":[{"award-number":["DP1GM133052"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["RF1MH128861"],"award-info":[{"award-number":["RF1MH128861"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM124401"],"award-info":[{"award-number":["R01GM124401"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"U.S. Department of Health & Human Services | National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG012926"],"award-info":[{"award-number":["R01HG012926"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Orthogonal DNA barcode library design is an essential task in bioengineering. Here we present seqwalk, an efficient method for designing barcode libraries that satisfy a sequence symmetry minimization (SSM) heuristic for orthogonality, with theoretical guarantees of maximal or near-maximal library size under certain design constraints. Seqwalk encodes SSM constraints in a de Bruijn graph representation of sequence space, enabling the application of recent advances in discrete mathematics<jats:sup>1<\/jats:sup> to the problem of orthogonal sequence design. We demonstrate the scalability of seqwalk by designing a library of &gt;10<jats:sup>6<\/jats:sup> SSM-satisfying barcode sequences in less than 20\u2009s on a standard laptop.<\/jats:p>","DOI":"10.1038\/s43588-024-00646-z","type":"journal-article","created":{"date-parts":[[2024,6,7]],"date-time":"2024-06-07T10:02:26Z","timestamp":1717754546000},"page":"423-428","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Scalable design of orthogonal DNA barcode libraries"],"prefix":"10.1038","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0911-6889","authenticated-orcid":false,"given":"Gokul","family":"Gowri","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7155-9915","authenticated-orcid":false,"given":"Kuanwei","family":"Sheng","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4773-359X","authenticated-orcid":false,"given":"Peng","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,7]]},"reference":[{"key":"646_CR1","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.disc.2016.09.008","volume":"340","author":"J Sawada","year":"2017","unstructured":"Sawada, J., Williams, A. & Wong, D. A simple shift rule for k-ary de bruijn sequences. Discrete Math. 340, 524\u2013531 (2017).","journal-title":"Discrete Math."},{"key":"646_CR2","doi-asserted-by":"publisher","first-page":"1080","DOI":"10.1038\/s41587-019-0207-y","volume":"37","author":"SK Saka","year":"2019","unstructured":"Saka, S. K. et al. Immuno-SABER enables highly multiplexed and amplified protein imaging in tissues. Nat. Biotechnol. 37, 1080\u20131090 (2019).","journal-title":"Nat. Biotechnol."},{"key":"646_CR3","doi-asserted-by":"publisher","first-page":"1187","DOI":"10.1016\/j.cell.2015.04.044","volume":"161","author":"AM Klein","year":"2015","unstructured":"Klein, A. M. et al. Droplet barcoding for single-cell transcriptomics applied to embryonic stem cells. Cell 161, 1187\u20131201 (2015).","journal-title":"Cell"},{"key":"646_CR4","doi-asserted-by":"publisher","first-page":"6961","DOI":"10.1021\/ja015873n","volume":"123","author":"ZJ Gartner","year":"2001","unstructured":"Gartner, Z. J. & Liu, D. R. The generality of DNA-templated synthesis as a basis for evolving non-natural small molecules. J. Am. Chem. Soc. 123, 6961\u20136963 (2001).","journal-title":"J. Am. Chem. Soc."},{"key":"646_CR5","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1021\/sb4001323","volume":"3","author":"A Casini","year":"2014","unstructured":"Casini, A. et al. R2oDNA designer: computational design of biologically neutral synthetic DNA sequences. ACS Synth. Biol. 3, 525\u2013528 (2014).","journal-title":"ACS Synth. Biol."},{"key":"646_CR6","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-20094-3","volume":"12","author":"TC Yu","year":"2021","unstructured":"Yu, T. C. et al. Multiplexed characterization of rationally designed promoter architectures deconstructs combinatorial logic for IPTG-inducible systems. Nat. Commun. 12, 325 (2021).","journal-title":"Nat. Commun."},{"key":"646_CR7","doi-asserted-by":"publisher","first-page":"2289","DOI":"10.1073\/pnas.0812506106","volume":"106","author":"Q Xu","year":"2009","unstructured":"Xu, Q., Schlabach, M. R., Hannon, G. J. & Elledge, S. J. Design of 240,000 orthogonal 25mer DNA barcode probes. Proc. Natl. Acad. Sci. USA 106, 2289\u20132294 (2009).","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"646_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1089\/10665270152530818","volume":"8","author":"A Marathe","year":"2001","unstructured":"Marathe, A., Condon, A. E. & Corn, R. M. On combinatorial DNA word design. J. Comput. Biol. 8, 201\u2013219 (2001).","journal-title":"J. Comput. Biol."},{"key":"646_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1038\/nchem.2872","volume":"10","author":"JY Kishi","year":"2018","unstructured":"Kishi, J. Y., Schaus, T. E., Gopalkrishnan, N., Xuan, F. & Yin, P. Programmable autonomous synthesis of single-stranded DNA. Nat. Chem. 10, 155\u2013164 (2018).","journal-title":"Nat. Chem."},{"key":"646_CR10","doi-asserted-by":"crossref","unstructured":"Evans, C. G. & Winfree, E. in DNA Computing and Molecular Programming (eds. Soloveichik, D. & Yurke, B.) 61\u201375 (Springer, 2013).","DOI":"10.1007\/978-3-319-01928-4_5"},{"key":"646_CR11","doi-asserted-by":"publisher","first-page":"2665","DOI":"10.1021\/acssynbio.9b00523","volume":"9","author":"ME Fornace","year":"2020","unstructured":"Fornace, M. E., Porubsky, N. J. & Pierce, N. A. A unified dynamic programming framework for the analysis of interacting nucleic acid strands: enhanced models, scalability, and speed. ACS Synth. Biol. 9, 2665\u20132678 (2020).","journal-title":"ACS Synth. Biol."},{"key":"646_CR12","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1080\/07391102.1990.10507829","volume":"8","author":"NC Seeman","year":"1990","unstructured":"Seeman, N. C. De novo design of sequences for nucleic acid structural engineering. J. Biomol. Struct. Dyn. 8, 573\u2013581 (1990).","journal-title":"J. Biomol. Struct. Dyn."},{"key":"646_CR13","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1038\/ng1296-450","volume":"14","author":"DD Shoemaker","year":"1996","unstructured":"Shoemaker, D. D., Lashkari, D. A., Morris, D., Mittmann, M. & Davis, R. W. Quantitative phenotypic analysis of yeast deletion mutants using a highly parallel molecular bar-coding strategy. Nat. Genet. 14, 450\u2013456 (1996).","journal-title":"Nat. Genet."},{"key":"646_CR14","doi-asserted-by":"publisher","first-page":"3753","DOI":"10.1128\/AEM.71.7.3753-3760.2005","volume":"71","author":"Z He","year":"2005","unstructured":"He, Z., Wu, L., Li, X., Fields, M. W. & Zhou, J. Empirical establishment of oligonucleotide probe design criteria. Appl. Environ. Microbiol. 71, 3753\u20133760 (2005).","journal-title":"Appl. Environ. Microbiol."},{"key":"646_CR15","doi-asserted-by":"publisher","first-page":"4552","DOI":"10.1093\/nar\/28.22.4552","volume":"28","author":"MD Kane","year":"2000","unstructured":"Kane, M. D. et al. Assessment of the sensitivity and specificity of oligonucleotide (50mer) microarrays. Nucleic Acids Res. 28, 4552\u20134557 (2000).","journal-title":"Nucleic Acids Res."},{"key":"646_CR16","doi-asserted-by":"publisher","first-page":"E2183","DOI":"10.1073\/pnas.1714530115","volume":"115","author":"BJ Beliveau","year":"2018","unstructured":"Beliveau, B. J. et al. OligoMiner provides a rapid, flexible environment for the design of genome-scale oligonucleotide in situ hybridization probes. Proc. Natl. Acad. Sci. USA 115, E2183\u2013E2192 (2018).","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"646_CR17","doi-asserted-by":"publisher","first-page":"vbad181","DOI":"10.1093\/bioadv\/vbad181","volume":"4","author":"AS Booeshaghi","year":"2024","unstructured":"Booeshaghi, A. S., Min, KyungHoiJoseph, Gehring, J. & Pachter, L. Quantifying orthogonal barcodes for sequence census assays. Bioinform. Adv. 4, vbad181 (2024).","journal-title":"Bioinform. Adv."},{"key":"646_CR18","doi-asserted-by":"crossref","unstructured":"Smith, W. D. & Schweitzer, A. in DIMACS Series in Discrete Mathematics and Theoretical Computer Science (eds. Lipton, R. J. & Baum, E.) 121\u2013185. (American Mathematical Society, 1996).","DOI":"10.1090\/dimacs\/027\/07"},{"key":"646_CR19","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1021\/acssynbio.6b00271","volume":"6","author":"J Kozyra","year":"2017","unstructured":"Kozyra, J. et al. Designing uniquely addressable bio-orthogonal synthetic scaffolds for DNA and RNA origami. ACS Synth. Biol. 6, 1140\u20131149 (2017).","journal-title":"ACS Synth. Biol."},{"key":"646_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.dam.2018.12.029","volume":"259","author":"A Kozak","year":"2019","unstructured":"Kozak, A., G\u0142owacki, T. & Formanowicz, P. A method for constructing artificial DNA libraries based on generalized de bruijn sequences. Discrete Appl. Math. 259, 127\u2013144 (2019).","journal-title":"Discrete Appl. Math."},{"key":"646_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.disc.2015.08.002","volume":"339","author":"J Sawada","year":"2016","unstructured":"Sawada, J., Williams, A. & Wong, D. A surprisingly simple de Bruijn sequence construction. Discrete Math. 339, 127\u2013131 (2016).","journal-title":"Discrete Math."},{"key":"646_CR22","doi-asserted-by":"crossref","unstructured":"van Aardenne-Ehrenfest, T. & de Bruijn, N. G. in Classic Papers in Combinatorics (eds. Gessel, I. & Rota, G. C.) 149\u2013163 (Springer, 2009).","DOI":"10.1007\/978-0-8176-4842-8_12"},{"key":"646_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R. M. in Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations (eds Miller, R. E., Thatcher, J. W. & Bohlinger, J. D.) 85\u2013103 (Springer, 1972).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"646_CR24","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-421","volume":"10","author":"C Camacho","year":"2009","unstructured":"Camacho, C. et al. BLAST+: architecture and applications. BMC Bioinform. 10, 421 (2009).","journal-title":"BMC Bioinform."},{"key":"646_CR25","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1038\/s41592-019-0433-8","volume":"16","author":"CS McGinnis","year":"2019","unstructured":"McGinnis, C. S. et al. MULTI-seq: sample multiplexing for single-cell RNA sequencing using lipid-tagged indices. Nat. Methods 16, 619\u2013626 (2019).","journal-title":"Nat. Methods"},{"key":"646_CR26","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/BF01442866","volume":"6","author":"C Hierholzer","year":"1873","unstructured":"Hierholzer, C. & Wiener, C. \u00dcber die M\u00f6glichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Ann. 6, 30\u201332 (1873).","journal-title":"Math. Ann."},{"key":"646_CR27","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1089\/cmb.1995.2.291","volume":"2","author":"RM Idury","year":"1995","unstructured":"Idury, R. M. & Waterman, M. S. A new algorithm for DNA sequence assembly. J. Comput. Biol. 2, 291\u2013306 (1995).","journal-title":"J. Comput. Biol."},{"key":"646_CR28","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-021-04437-5","volume":"22","author":"J Linder","year":"2021","unstructured":"Linder, J. & Seelig, G. Fast activation maximization for molecular sequence design. BMC Bioinform. 22, 510 (2021).","journal-title":"BMC Bioinform."},{"key":"646_CR29","unstructured":"Weinstein, E. N. et al. Optimal design of stochastic DNA synthesis protocols based on generative sequence models. In Proc. 25th International Conference on Artificial Intelligence and Statistics, Vol. 151 of Proc. Machine Learning Research, (eds Camps-Valls, G., Ruiz, F. J. R. & Valera, I.) 7450\u20137482 (PMLR, 2022)."},{"key":"646_CR30","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-021-24991-z","volume":"12","author":"C Bee","year":"2021","unstructured":"Bee, C. et al. Molecular-level similarity search brings computing to DNA data storage. Nat. Commun. 12, 4764 (2021).","journal-title":"Nat. Commun."},{"key":"646_CR31","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-022-29500-4","volume":"13","author":"NG Xie","year":"2022","unstructured":"Xie, N. G. et al. Designing highly multiplex PCR primer sets with simulated annealing design using dimer likelihood estimation (SADDLE). Nat. Commun. 13, 1881 (2022).","journal-title":"Nat. Commun."},{"key":"646_CR32","doi-asserted-by":"publisher","unstructured":"Gowri, G. ggdna\/seqwalk: v0.3.1 (v0.3.1). Zenodo https:\/\/doi.org\/10.5281\/zenodo.10932482 (2024).","DOI":"10.5281\/zenodo.10932482"}],"container-title":["Nature Computational Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s43588-024-00646-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s43588-024-00646-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s43588-024-00646-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,26]],"date-time":"2024-06-26T16:13:44Z","timestamp":1719418424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s43588-024-00646-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,7]]},"references-count":32,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["646"],"URL":"https:\/\/doi.org\/10.1038\/s43588-024-00646-z","relation":{},"ISSN":["2662-8457"],"issn-type":[{"value":"2662-8457","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,7]]},"assertion":[{"value":"11 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}