{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:33:52Z","timestamp":1761294832553,"version":"build-2065373602"},"reference-count":14,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T00:00:00Z","timestamp":1743292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2107344"],"award-info":[{"award-number":["2107344"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>A de Bruijn sequence of order k over a finite alphabet is a cyclic sequence with the property that it contains every possible k-sequence as a substring exactly once. Orthogonal de Bruijn sequences are the collections of de Bruijn sequences of the same order, k, that satisfy the joint constraint that every (k+1)-sequence appears as a substring in, at most, one of the sequences in the collection. Both de Bruijn and orthogonal de Bruijn sequences have found numerous applications in synthetic biology, although the latter remain largely unexplored in the coding theory literature. Here, we study three relevant practical generalizations of orthogonal de Bruijn sequences, where we relax either the constraint that every (k+1)-sequence appears exactly once or the sequences themselves are de Bruijn rather than balanced de Bruijn sequences. We also provide lower and upper bounds on the number of fixed-weight orthogonal de Bruijn sequences. The paper concludes with parallel results for orthogonal nonbinary Kautz sequences, which satisfy similar constraints as de Bruijn sequences, except for being only required to cover all subsequences of length k whose maximum run length equals one.<\/jats:p>","DOI":"10.3390\/e27040366","type":"journal-article","created":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T05:10:07Z","timestamp":1743397807000},"page":"366","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Generalized Orthogonal de Bruijn and Kautz Sequences"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0850-5009","authenticated-orcid":false,"given":"Yuan-Pon","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin","family":"Sima","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olgica","family":"Milenkovic","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Chen, Y.P., Sima, J., and Milenkovic, O. (2025). Generalized Orthogonal de Bruijn Sequences. arXiv.","DOI":"10.3390\/e27040366"},{"key":"ref_2","unstructured":"de Bruijn, N.G. (1975). Acknowledgement of Priority to C. Flye Sainte-Marie on the Counting of Circular Arrangements of 2n Zeros and Ones that Show Each n-Letter Word Exactly Once, WSK, Dept. of Mathematics and Computing Science, Technische Hogeschool Eindhoven. EUT report."},{"key":"ref_3","unstructured":"van Aardenne-Ehrenfest, T., and de Bruijn, N.G. (1987). Circuits and trees in oriented linear graphs. Classic Papers in Combinatorics, Birkh\u00e4user."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Kiah, H.M., Puleo, G.J., and Milenkovic, O. (2015, January 14\u201319). Codes for DNA sequence profiles. Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT), Hong Kong, China.","DOI":"10.1109\/ISIT.2015.7282568"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Marcovich, S., Etzion, T., and Yaakobi, E. (2021, January 12\u201320). Balanced de Bruijn Sequences. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9517873"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/100808782","article-title":"De Bruijn Sequences for Fixed-Weight Binary Strings","volume":"26","author":"Ruskey","year":"2012","journal-title":"SIAM J. Discret. Math."},{"key":"ref_7","first-page":"19","article-title":"Enumerating Kautz sequences","volume":"24","author":"Rosenfeld","year":"2002","journal-title":"Kragujev. J. Math."},{"key":"ref_8","unstructured":"Lin, Y.L., Ward, C., Jain, B., and Skiena, S. (2011, January 15\u201317). Constructing orthogonal de Bruijn sequences. Proceedings of the Algorithms and Data Structures: 12th International Symposium, WADS 2011, New York, NY, USA. Proceedings 12."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Fleischner, H., and Jackson, B. (1990). Compatible Euler Tours In Eulerian Digraphs. Cycles and Rays, Springer Netherlands.","DOI":"10.1007\/978-94-009-0517-7_9"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1142\/S0129626493000411","article-title":"On the number of arc-disjoint Hamiltonian circuits in the de Bruijn Graph","volume":"03","author":"Rowley","year":"1993","journal-title":"Parallel Process. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Tabatabaei Yazdi, S.H., Yuan, Y., Ma, J., Zhao, H., and Milenkovic, O. (2015). A rewritable, random-access DNA-based storage system. Sci. Rep., 5.","DOI":"10.1038\/srep14138"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Yazdi, S.H.T., Gabrys, R., and Milenkovic, O. (2017). Portable and error-free DNA-based data storage. Sci. Rep., 7.","DOI":"10.1038\/s41598-017-05188-1"},{"key":"ref_13","first-page":"135","article-title":"k-walks in graphs","volume":"2","author":"Jackson","year":"1990","journal-title":"Australas. J. Comb."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1112\/jlms\/s1-21.3.169","article-title":"Note on a Paper By I. J. Good","volume":"s1-21","author":"Rees","year":"1946","journal-title":"J. Lond. Math. Soc."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/4\/366\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:05:51Z","timestamp":1760029551000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/4\/366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,30]]},"references-count":14,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,4]]}},"alternative-id":["e27040366"],"URL":"https:\/\/doi.org\/10.3390\/e27040366","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,3,30]]}}}