Alex Khodaverdian

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-262

December 13, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-262.pdf

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.

Advisors: Nir Yosef

---

BibTeX citation:

@phdthesis{Khodaverdian:EECS-2022-262,
    Author= {Khodaverdian, Alex},
    Title= {Network Optimization Algorithms and Applications to Molecular Biology},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-262.html},
    Number= {UCB/EECS-2022-262},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Khodaverdian, Alex 
%T Network Optimization Algorithms and Applications to Molecular Biology
%I EECS Department, University of California, Berkeley
%D 2022
%8 December 13
%@ UCB/EECS-2022-262
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-262.html
%F Khodaverdian:EECS-2022-262