{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:09:47Z","timestamp":1773277787953,"version":"3.50.1"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1201,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Novel technologies can generate large sets of short double-stranded DNA sequences that can be used to measure their regulatory effects. Microarrays can measure in vitro the binding intensity of a protein to thousands of probes. Synthetic enhancer sequences inserted into an organism\u2019s genome allow us to measure in vivo the effect of such sequences on the phenotype. In both applications, by using sequence probes that cover all k-mers, a comprehensive picture of the effect of all possible short sequences on gene regulation is obtained. The value of k that can be used in practice is, however, severely limited by cost and space considerations. A key challenge is, therefore, to cover all k-mers with a minimal number of probes. The standard way to do this uses the de Bruijn sequence of length . However, as probes are double stranded, when a k-mer is included in a probe, its reverse complement k-mer is accounted for as well.<\/jats:p>\n               <jats:p>Results: Here, we show how to efficiently create a shortest possible sequence with the property that it contains each k-mer or its reverse complement, but not necessarily both. The length of the resulting sequence approaches half that of the de Bruijn sequence as k increases resulting in a more efficient array, which allows covering more longer sequences; alternatively, additional sequences with redundant k-mers of interest can be added.<\/jats:p>\n               <jats:p>Availability: The software is freely available from our website http:\/\/acgt.cs.tau.ac.il\/shortcake\/.<\/jats:p>\n               <jats:p>Contact: rshamir@tau.ac.il<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt230","type":"journal-article","created":{"date-parts":[[2013,6,27]],"date-time":"2013-06-27T05:33:26Z","timestamp":1372311206000},"page":"i71-i79","source":"Crossref","is-referenced-by-count":16,"title":["Design of shortest double-stranded DNA sequences covering all <i>k<\/i>-mers with applications to protein-binding microarrays and synthetic enhancers"],"prefix":"10.1093","volume":"29","author":[{"given":"Yaron","family":"Orenstein","sequence":"first","affiliation":[]},{"given":"Ron","family":"Shamir","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2013,6,19]]},"reference":[{"key":"2023062614331634300_btt230-B1","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1038\/nbt1246","article-title":"Compact, universal DNA microarrays to comprehensively determine transcription-factor binding site specificities","volume":"24","author":"Berger","year":"2006","journal-title":"Nat. Biotechnol."},{"key":"2023062614331634300_btt230-B2","doi-asserted-by":"crossref","first-page":"i72","DOI":"10.1093\/bioinformatics\/btm224","article-title":"Rankmotif++: a motif-search algorithm that accounts for relative ranks of k-mers in binding transcription factors","volume":"23","author":"Chen","year":"2007","journal-title":"Bioinformatics"},{"key":"2023062614331634300_btt230-B19","article-title":"An introduction to matching","volume-title":"Notes of Engineering Summer Conference","author":"Edmonds","year":"1967"},{"key":"2023062614331634300_btt230-B3","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","article-title":"Matching, Euler tours and the Chinese postman","volume":"5","author":"Edmonds","year":"1973","journal-title":"Math. Program."},{"key":"2023062614331634300_btt230-B4","volume-title":"Eulerian Graphs and Related Topics","author":"Fleischner","year":"1990"},{"key":"2023062614331634300_btt230-B5","doi-asserted-by":"crossref","first-page":"970","DOI":"10.1038\/nbt.1675","article-title":"De novo identification and biophysical characterization of transcription-factor binding sites with microfluidic affinity analysis","volume":"28","author":"Fordyce","year":"2010","journal-title":"Nat. Biotechnol."},{"key":"2023062614331634300_btt230-B6","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.cell.2012.12.009","article-title":"DNA-binding specificities of human transcription factors","volume":"152","author":"Jolma","year":"2013","journal-title":"Cell"},{"key":"2023062614331634300_btt230-B7","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/3-540-63890-3_39","article-title":"All-cavity maximum matchings","volume":"1350","author":"Kao","year":"1997","journal-title":"Algorithms Comput."},{"key":"2023062614331634300_btt230-B8","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","article-title":"Combinatorial algorithms for DNA sequence assembly","volume":"13","author":"Kececioglu","year":"1995","journal-title":"Algorithmica"},{"key":"2023062614331634300_btt230-B9","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"2006","journal-title":"Naval Res. Logist. Q."},{"key":"2023062614331634300_btt230-B10","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1089\/cmb.2009.0047","article-title":"Maximum likelihood genome assembly","volume":"16","author":"Medvedev","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023062614331634300_btt230-B11","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/978-3-540-74126-8_27","article-title":"Computability of models for sequence assembly","author":"Medvedev","year":"2007","journal-title":"Algorithms Bioinform."},{"key":"2023062614331634300_btt230-B12","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1186\/1471-2105-7-429","article-title":"Design of a combinatorial DNA microarray for protein-DNA interaction studies","volume":"7","author":"Mintseris","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023062614331634300_btt230-B13","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1038\/nbt.1882","article-title":"Direct measurement of DNA affinity landscapes on a high-throughput sequencing instrument","volume":"29","author":"Nutiu","year":"2011","journal-title":"Nat. Biotechnol."},{"key":"2023062614331634300_btt230-B14","doi-asserted-by":"crossref","DOI":"10.1089\/cmb.2012.0253","article-title":"Rap: Accurate and fast motif finding based on protein-binding microarray data","author":"Orenstein","year":"2013","journal-title":"J. Comput. Biol."},{"key":"2023062614331634300_btt230-B15","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1089\/cmb.2007.0114","article-title":"Design of compact, universal DNA microarrays for protein binding microarray experiments","volume":"15","author":"Philippakis","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023062614331634300_btt230-B16","unstructured":"Riesenfeld\n              S\n            \n            \n              Pollard\n              K\n            \n          \n          2012\n          Computing MRCC libraries and related types of DNA oligomer libraries. https:\/\/github.com\/sriesenfeld\/MRCC-Libraries (1 April 2013, date last accessed)"},{"key":"2023062614331634300_btt230-B17","unstructured":"Smith\n              R\n            \n            \n              Ahituv\n              N\n            \n          \n          2012\n          Deciphering the vertebrate regulatory code using short synthetic enhancers in vivo. http:\/\/zendev.ucsf.edu\/projectview.php?project=6mer (1 April 2013, date last accessed)"},{"key":"2023062614331634300_btt230-B18","volume-title":"Introduction to Graph Theory","author":"West","year":"2001"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i71\/50705119\/bioinformatics_29_13_i71.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i71\/50705119\/bioinformatics_29_13_i71.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T15:33:52Z","timestamp":1687793632000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/13\/i71\/195654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,19]]},"references-count":19,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt230","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2013,7]]},"published":{"date-parts":[[2013,6,19]]}}}