Tools for large and detailed experiments in genomics and tissue development
Abstract
In this dissertation I present algorithmic and data representation advances in genomics as well as tools for a new bioinformatic approach to mammalian cell culture experiments which I call highly instrumented cell culture. The first section deals with fast variants of the forward algorithm for the Li and Stephens copying model of haplotypes derived from a population. I introduce a direct optimization of the Li and Stephens model forward algorithm which performs the identical calculation, without any approximations, but achieves this in average case sublinear time. This is an improvement over the classical algorithm which is at best linear time. I achieve this by using a sparse representation of the population haplotypes and by introducing an efficient lazy evaluation scheme. I also introduce a generalization of the recombination modeling component of the Li and Stephens model which operates on haplotypes and populations encoded in variation graphs. The second section deals with algebraic representations of genetic sites in variation graphs. I introduce the concept of the bundle, a motif in bidirected graphs which leads to a well defined concept of adjacency of sets of nodes. This allows a granular decomposition of the graph into sites which extends prior work on ultrabubbles and snarls previously reported by Paten et al. Lastly, I introduce the concept of highly instrumented cell culture and some technologies to enable it. I demonstrate a low-cost, robust, arbitrarily scalable microscope array for simultaneous parallel continuous time-series microscopy. I demonstrate new approaches to rapid prototyping of labware and fluidic actuators. I also demonstrate principles and implementation of incubator-free cell culture, which is my approach to cell culture in media containing carbonic acid-carbonate-bicarbonate buffer systems without using any carbon dioxide rich gas chamber. I finally describe how these technologies integrate together to enable the creation of highly instrumented, automated, data rich biology experiments.