Efficient algorithms for designing maximally sized orthogonal DNA sequence libraries

Abstract

Orthogonal sequence library design is an essential task in bioengineering. Typical design approaches scale quadratically in the size of the candidate sequence space. As such, exhaustive searches of sequence space to maximize library size are computationally intractable with existing methods. Here, we present SeqWalk, a time and memory efficient method for designing maximally-sized orthogonal sequence libraries using the sequence symmetry minimization heuristic. SeqWalk encodes sequence design constraints in a de Bruijn graph representation of sequence space, enabling the application of efficient graph traversal techniques to the problem of orthogonal DNA sequence design. We demonstrate the scalability of SeqWalk by designing a provably maximal set of > 106 orthogonal 25nt sequences in less than 20 seconds on a single standard CPU core. We additionally derive fundamental bounds on orthogonal sequence library size under a variety of design constraints.