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

Gene regulatory elements play a key role in orchestrating gene expression during cellular differentiation, but what determines their function over time remains largely unknown. Here, we perform perturbation-based massively parallel reporter assays at seven early time points of neural differentiation to systematically characterize how regulatory elements and motifs within them guide cellular differentiation. By perturbing over 2, 000 putative DNA binding motifs in active regulatory regions, we delineate four categories of functional elements, and observe that activity direction is mostly determined by the sequence itself, while the magnitude of effect depends on the cellular environment. We also find that fine-tuning transcription rates is often achieved by a combined activity of adjacent activating and repressing elements. Our work provides a blueprint for the sequence components needed to induce different transcriptional patterns in general and specifically during neural differentiation.

Gene regulatory elements play a key role in orchestrating gene expression during cellular differentiation, but what determines their function over time remains largely unknown. Here, we perform perturbation-based massively parallel reporter assays at seven early time points of neural differentiation to systematically characterize how regulatory elements and motifs within them guide cellular differentiation. By perturbing over 2,000 putative DNA binding motifs in active regulatory regions, we delineate four categories of functional elements, and observe that activity direction is mostly determined by the sequence itself, while the magnitude of effect depends on the cellular environment. We also find that fine-tuning transcription rates is often achieved by a combined activity of adjacent activating and repressing elements. Our work provides a blueprint for the sequence components needed to induce different transcriptional patterns in general and specifically during neural differentiation.

Gene regulatory elements play a key role in orchestrating gene expression during cellular differentiation, but what determines their function over time remains largely unknown. Here, we perform perturbation-based massively parallel reporter assays at seven early time points of neural differentiation to systematically characterize how regulatory elements and motifs within them guide cellular differentiation. By perturbing over 2,000 putative DNA binding motifs in active regulatory regions, we delineate four categories of functional elements, and observe that activity direction is mostly determined by the sequence itself, while the magnitude of effect depends on the cellular environment. We also find that fine-tuning transcription rates is often achieved by a combined activity of adjacent activating and repressing elements. Our work provides a blueprint for the sequence components needed to induce different transcriptional patterns in general and specifically during neural differentiation.

The pairing of CRISPR/Cas9-based gene editing with massively parallel single-cell readouts now enables large-scale lineage tracing. However, the rapid growth in complexity of data from these assays has outpaced our ability to accurately infer phylogenetic relationships. First, we introduce Cassiopeia-a suite of scalable maximum parsimony approaches for tree reconstruction. Second, we provide a simulation framework for evaluating algorithms and exploring lineage tracer design principles. Finally, we generate the most complex experimental lineage tracing dataset to date, 34,557 human cells continuously traced over 15 generations, and use it for benchmarking phylogenetic inference approaches. We show that Cassiopeia outperforms traditional methods by several metrics and under a wide variety of parameter regimes, and provide insight into the principles for the design of improved Cas9-enabled recorders. Together, these should broadly enable large-scale mammalian lineage tracing efforts. Cassiopeia and its benchmarking resources are publicly available at www.github.com/YosefLab/Cassiopeia.

The pairing of CRISPR/Cas9-based gene editing with massively parallel single-cell readouts now enables large-scale lineage tracing. However, the rapid growth in complexity of data from these assays has outpaced our ability to accurately infer phylogenetic relationships. First, we introduce Cassiopeia-a suite of scalable maximum parsimony approaches for tree reconstruction. Second, we provide a simulation framework for evaluating algorithms and exploring lineage tracer design principles. Finally, we generate the most complex experimental lineage tracing dataset to date, 34,557 human cells continuously traced over 15 generations, and use it for benchmarking phylogenetic inference approaches. We show that Cassiopeia outperforms traditional methods by several metrics and under a wide variety of parameter regimes, and provide insight into the principles for the design of improved Cas9-enabled recorders. Together, these should broadly enable large-scale mammalian lineage tracing efforts. Cassiopeia and its benchmarking resources are publicly available at www.github.com/YosefLab/Cassiopeia.

Ontogeny describes the emergence of complex multicellular organisms from single totipotent cells. This field is particularly challenging in mammals, owing to the indeterminate relationship between self-renewal and differentiation, variation in progenitor field sizes, and internal gestation in these animals. Here we present a flexible, high-information, multi-channel molecular recorder with a single-cell readout and apply it as an evolving lineage tracer to assemble mouse cell-fate maps from fertilization through gastrulation. By combining lineage information with single-cell RNA sequencing profiles, we recapitulate canonical developmental relationships between different tissue types and reveal the nearly complete transcriptional convergence of endodermal cells of extra-embryonic and embryonic origins. Finally, we apply our cell-fate maps to estimate the number of embryonic progenitor cells and their degree of asymmetric partitioning during specification. Our approach enables massively parallel, high-resolution recording of lineage and other information in mammalian systems, which will facilitate the construction of a quantitative framework for understanding developmental processes.

Ontogeny describes the emergence of complex multicellular organisms from single totipotent cells. This field is particularly challenging in mammals, owing to the indeterminate relationship between self-renewal and differentiation, variation in progenitor field sizes, and internal gestation in these animals. Here we present a flexible, high-information, multi-channel molecular recorder with a single-cell readout and apply it as an evolving lineage tracer to assemble mouse cell-fate maps from fertilization through gastrulation. By combining lineage information with single-cell RNA sequencing profiles, we recapitulate canonical developmental relationships between different tissue types and reveal the nearly complete transcriptional convergence of endodermal cells of extra-embryonic and embryonic origins. Finally, we apply our cell-fate maps to estimate the number of embryonic progenitor cells and their degree of asymmetric partitioning during specification. Our approach enables massively parallel, high-resolution recording of lineage and other information in mammalian systems, which will facilitate the construction of a quantitative framework for understanding developmental processes.

We introduce a temporal Steiner network problem in which a graph, as well as changes to its edges and/or vertices over a set of discrete times, are given as input; the goal is to find a minimal subgraph satisfying a set of $k$ time-sensitive connectivity demands. We show that this problem, $k$-Temporal Steiner Network ($k$-TSN), is NP-hard to approximate to a factor of $k - \epsilon$, for every fixed $k \geq 2$ and $\epsilon > 0$. This bound is tight, as certified by a trivial approximation algorithm. Conceptually this demonstrates, in contrast to known results for traditional Steiner problems, that a time dimension adds considerable complexity even when the problem is offline. We also discuss special cases of $k$-TSN in which the graph changes satisfy a monotonicity property. We show approximation-preserving reductions from monotonic $k$-TSN to well-studied problems such as Priority Steiner Tree and Directed Steiner Tree, implying improved approximation algorithms. Lastly, $k$-TSN and its variants arise naturally in computational biology; to facilitate such applications, we devise an integer linear program for $k$-TSN based on network flows.