We consider efficient construction of DNA-based polymers in a model introduced by Dabby and Chen (SODA 2013) called insertion systems, where monomers insert themselves into the middle of a growing linear polymer. Specifically, we describe a new family of non-deterministic insertion systems that construct length-n polymers in θ(log~(3/2)(n)) expected time, breaking the lower bound of Ω(log~(5/3)(n)) for deterministic construction. We also prove that this time is optimal for systems constructing finite polymers, and that the θ(log(n)) monomer types used in the construction is optimal for this time.
展开▼
