Search

In this thesis, I pursue several problems in molecular biology through abstraction into network optimization algorithms.In the first chapter of this thesis I consider our first flavor of network problems - sub-network optimization within a known dynamic network. In these instances, I introduce the notion of Condition and Time Conditioned networks, in which a network may dynamically change over time (i.e. vertices or edges). In our first set of problems, the goal becomes to find a global sub-network of minimum cost, which satisfies all local connectivity demands across conditions. In the second set of problems, I consider optimizing a singular walk demand beginning at source node $a$ in timepoint $t_1$ and ending at a destination node $b$ at a later timepoint $t_2$, while maintaining a notion of consistency over time. Lastly, I utilize these frameworks to investigate signal transduction in Th17 cells with the purpose of finding novel downstream proteins of interest involved in IL23 receptor signalling. In the second chapter of this thesis, I consider the problem of lineage tracing in CRISPR/Cas9 models - given a set of terminal nodes or cells generated via CRISPR/Cas9 lineage tracing, what is the most likely tree that best represents the ground truth generative process. In particular, I begin by introducing two methods towards this analysis - a greedy approach, and an exact integer linear programming approach. I then test these methods via simulation and via ground truth trees generated in vitro. Lastly, I take a step back and consider the theoretical guarantees of our framework. That is, I explore the relationship between the number of characters/cut sites in our model against variables such as minimum cell division times, number of cells, and cutting rates. In particular I derive upper bounds for the number of characters required for exact reconstruction given perfect knowledge about the experimental setup.In the third and final chapter of this thesis, I consider a network flow abstraction for estimating metabolic activity within cells. Given the relationship between metabolism and immunological function, our goal becomes to discover tissue specific metabolic programs within Th17 cells. To achieve this goal, I leverage a Flux Balance Analysis approach to estimate network wide metabolic flux within Th17 cells collected from mice across various tissues, whereby I discover a novel gut specific metabolic target of interest responsible for regulating effector-like function and homeostasis.

Additional file 1 Fig S1. Time complexity of lineage reconstruction approaches. Fig S2. Evaluation of the stability of the maximum neighborhood size parameter. Fig S3. Observed Frequency of Mutation is a Measure of True Mutation Count. Fig S4. Precision of Cassiopeia-Greedy First Split. Fig S5. Benchmarking of parallel evolution on the greedy heuristic. Fig S6. Determination of mutation rates used in simulation. Fig S7. Triplets Correct Statistic. Fig S8. Unthresholded Triplets Correct. Fig S9. Parsimony of reconstructed trees of 400 cell simulated datasets. Fig S10. Benchmarking of lineage tracing algorithms on 1000 cell synthetic datasets. Fig S11. Benchmarking of greedy and hybrid algorithms on large experiments. Fig S12. Bootstrapping analysis of Cassiopeia and Neighbor-Joining with the Transfer Bootstrap Expectation statistic. Fig S13. Reconstruction accuracy under over-dispersed state distributions. Fig S14. Observed Proportion of Parallel Evolution in Simulations. Fig S15. Determination of the indel prior transformation function. Fig S16. Incorporation of priors into Cassiopeia. Figure S17. Quality control metrics for the target-site sequencing library processing pipeline. Fig S18. Processing pipeline for the in vitro dataset. Fig S19. Identification of doublets using intBCs. Fig S20. Estimation of Prior Probabilities for Tree Reconstruction. Fig S21. Evaluation of algorithms on in vitro lineage tracing clones, First Split. Fig S22. Evaluation of algorithms on in vitro lineage tracing clones, Second Split. Fig S23. Exhaustion of Target Sites across Clones. Fig S24. Vignette of Inferential Mistakes for Clone 3. Fig S25. Parsimony scores from reconstructions of the GESTALT datasets. Fig S26. “Phased Recorder” leverages variability across target sites.

Additional file 2 Review history.