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