Algorithms for automated DNA assembly.

Generating a defined set of genetic constructs within a large combinatorial space provides a powerful method for engineering novel biological functions. However, the process of assembling more than a few specific DNA sequences can be costly, time consuming and error prone. Even if a correct theoretical construction scheme is developed manually, it is likely to be suboptimal by any number of cost metrics. Modular, robust and formal approaches are needed for exploring these vast design spaces. By automating the design of DNA fabrication schemes using computational algorithms, we can eliminate human error while reducing redundant operations, thus minimizing the time and cost required for conducting biological engineering experiments. Here, we provide algorithms that optimize the simultaneous assembly of a collection of related DNA sequences. We compare our algorithms to an exhaustive search on a small synthetic dataset and our results show that our algorithms can quickly find an optimal solution. Comparison with random search approaches on two real-world datasets show that our algorithms can also quickly find lower-cost solutions for large datasets.

Selection of chromosomal DNA libraries using a multiplex CRISPR system.

The directed evolution of biomolecules to improve or change their activity is central to many engineering and synthetic biology efforts. However, selecting improved variants from gene libraries in living cells requires plasmid expression systems that suffer from variable copy number effects, or the use of complex marker-dependent chromosomal integration strategies. We developed quantitative gene assembly and DNA library insertion into the Saccharomyces cerevisiae genome by optimizing an efficient single-step and marker-free genome editing system using CRISPR-Cas9. With this Multiplex CRISPR (CRISPRm) system, we selected an improved cellobiose utilization pathway in diploid yeast in a single round of mutagenesis and selection, which increased cellobiose fermentation rates by over 10-fold. Mutations recovered in the best cellodextrin transporters reveal synergy between substrate binding and transporter dynamics, and demonstrate the power of CRISPRm to accelerate selection experiments and discoveries of the molecular determinants that enhance biomolecule function.

Scalable plasmid transfer using engineered P1-based phagemids.

Dramatic improvements to computational, robotic, and biological tools have enabled genetic engineers to conduct increasingly sophisticated experiments. Further development of biological tools offers a route to bypass complex or expensive mechanical operations, thereby reducing the time and cost of highly parallelized experiments. Here, we engineer a system based on bacteriophage P1 to transfer DNA from one E. coli cell to another, bypassing the need for intermediate DNA isolation (e.g., minipreps). To initiate plasmid transfer, we refactored a native phage element into a DNA module capable of heterologously inducing phage lysis. After incorporating known cis-acting elements, we identified a novel cis-acting element that further improves transduction efficiency, exemplifying the ability of synthetic systems to offer insight into native ones. The system transfers DNAs up to 25 kilobases, the maximum assayed size, and operates well at microliter volumes, enabling manipulation of most routinely used DNAs. The system's large DNA capacity and physical coupling of phage particles to phagemid DNA suggest applicability to biosynthetic pathway evolution, functional proteomics, and ultimately, diverse molecular biology operations including DNA fabrication.

Evaluation of three automated genome annotations for Halorhabdus utahensis.

Genome annotations are accumulating rapidly and depend heavily on automated annotation systems. Many genome centers offer annotation systems but no one has compared their output in a systematic way to determine accuracy and inherent errors. Errors in the annotations are routinely deposited in databases such as NCBI and used to validate subsequent annotation errors. We submitted the genome sequence of halophilic archaeon Halorhabdus utahensis to be analyzed by three genome annotation services. We have examined the output from each service in a variety of ways in order to compare the methodology and effectiveness of the annotations, as well as to explore the genes, pathways, and physiology of the previously unannotated genome. The annotation services differ considerably in gene calls, features, and ease of use. We had to manually identify the origin of replication and the species-specific consensus ribosome-binding site. Additionally, we conducted laboratory experiments to test H. utahensis growth and enzyme activity. Current annotation practices need to improve in order to more accurately reflect a genome's biological potential. We make specific recommendations that could improve the quality of microbial annotation projects.

Solving a Hamiltonian Path Problem with a bacterial computer.

BACKGROUND: The Hamiltonian Path Problem asks whether there is a route in a directed graph from a beginning node to an ending node, visiting each node exactly once. The Hamiltonian Path Problem is NP complete, achieving surprising computational complexity with modest increases in size. This challenge has inspired researchers to broaden the definition of a computer. DNA computers have been developed that solve NP complete problems. Bacterial computers can be programmed by constructing genetic circuits to execute an algorithm that is responsive to the environment and whose result can be observed. Each bacterium can examine a solution to a mathematical problem and billions of them can explore billions of possible solutions. Bacterial computers can be automated, made responsive to selection, and reproduce themselves so that more processing capacity is applied to problems over time. RESULTS: We programmed bacteria with a genetic circuit that enables them to evaluate all possible paths in a directed graph in order to find a Hamiltonian path. We encoded a three node directed graph as DNA segments that were autonomously shuffled randomly inside bacteria by a Hin/hixC recombination system we previously adapted from Salmonella typhimurium for use in Escherichia coli. We represented nodes in the graph as linked halves of two different genes encoding red or green fluorescent proteins. Bacterial populations displayed phenotypes that reflected random ordering of edges in the graph. Individual bacterial clones that found a Hamiltonian path reported their success by fluorescing both red and green, resulting in yellow colonies. We used DNA sequencing to verify that the yellow phenotype resulted from genotypes that represented Hamiltonian path solutions, demonstrating that our bacterial computer functioned as expected. CONCLUSION: We successfully designed, constructed, and tested a bacterial computer capable of finding a Hamiltonian path in a three node directed graph. This proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems. The results of our experiments also validate synthetic biology as a valuable approach to biological engineering. We designed and constructed basic parts, devices, and systems using synthetic biology principles of standardization and abstraction.