Scalable design of orthogonal DNA barcode libraries

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¹ to the problem of orthogonal sequence design. We demonstrate the scalability of seqwalk by designing a library of >10⁶ SSM-satisfying barcode sequences in less than 20 s on a standard laptop.