Mapping to Algorithmic Models

This section provides a mapping of the hybrid platform and the single-cell analysis protocol to algorithmic models.

Modeling of a Valve-Based Crossbar

Recall that an nb-to-ть valve-based crossbar can be constructed using different combinations of transposers. We represent the set of transposers and their interconnections as a directed acyclic graph (DAG) Gi, = (V),. Еь), where a vertex уы € Ц, is a transposer node, and an edge еы 6 Еь represents a connection between two transposers. Within a transposer, the point at which a droplet can be routed either straight or crossed is defined as a decision point.


Mapping a valve-based crossbar to a graph model: (a) a full transposer; (b) a half transposer; (c) a 4-to-2 crossbar.

We map an nb-to-mb valve-based crossbar (with a transposer network Gb) into a DAG ЕЩхть = {'^пьхть,Упьхть), where a vertex dbiТ>щхт„ is a flow-decision node, and an edge уыУп,,хть represents a channel that connects two decision nodes. To simplify the discussion, we do not include Gb in the notation for the crossbar DAG. We can view a full (half) transposer as a 2-to-2 (2-to-l) valve-based crossbar; thus, we represent fluid-flow control in a full (half) transposer as a DAG T-ix'i (^2xi); see Figure 5.6(a)-(b). The cost сы of уы represents the time needed to transport fluid between the two connected nodes, measured in flow time steps (Tb). We assume that the routing time of a droplet on a straight channel between two decision nodes is a unit of Tb. For example, as shown in Figure 5.6(a), q(1 is equal to Tb. whereas q,2 is equal to 2 Tb, since even though a diagonal is shown in Figure 5.4 as a fluidic path, routing of such paths in a transposer is implemented only along the x- and у-directions and the distances along these dimensions are equal [232]. Figure 5.6(c) depicts the graph TX2 for a 4-to-2 crossbar with 4 levels of transposers and 5 levels of nodes (denoted henceforth by q; q = 5 in this case).

Modeling of a Digital-Microfluidic Biochip

While DMFBs are highly reconfigurable and can support a diverse set of transport paths, we reduce the burden of managing droplet transport in real-time by considering a unidirectional ring-based architecture, as shown in Figure 5.1. Connected to this ring are on-chip resources. Since there is always a route between any pair of on-chip resources, a ring-based DMFB is modeled as a strongly connected DAG Gf = (Vf,Ef), where a vertex VfiVf represents the fluid-handling operation offered by an on-chip resource, and a directed edge e/, € Ej represents a path (over the ring) that connects two resources.


CFG of type-driven analysis for a single cell pathway.

The cost Cfi of eji indicates the number of digital time steps (Tf) needed to transport a droplet. We assume that the durations corresponding to Ть and Tf are equal, which can be achieved in practice by tuning the actuation frequency (Hz) and the flow rate (mL/min).

Protocol Model and Cell State Machine

To solve the synthesis problem for single-cell analysis, we take into account the complexity imposed by the barcoding mechanism. Similar to the design methodology in Chapter 2, we represent the protocol as a control flow graph (CFG) Gc = (Vr. Ec). in which every node vciVc (referred to as a supernode) models a bioassay such as qPCR; see Figure 5.7. A directed edge eci 6 Ec linking two supernodes {vCJ, vck} indicates that a potential decision can be made at runtime to direct the protocol flow to execute the bioassay vcf after vCJ. A supernode vci. in turn, encapsulates the sequencing graph that describes the fluid-handling operations of a bioassay and the interdependencies among them. Since there is inherent uncertainty about the type of barcoding droplets for a sample cell at design time, we extend the basic CFG model by incorporating an internal supernode (barcode propagation) that describes all possible dispensing options of barcoding droplets. Note that this model is agnostic about the type of the microfluidic technology used for implementing the protocol. Yet, the synthesis of each supernode is accomplished in a technology-aware manner using CoSyn.

The model shown in Figure 5.7 represents a protocol where a dispensed cell can be processed using one of two biochemical procedures, namely gene-expression analysis (GEA) and ChIP procedures. As shown in the CFG model, the execution of the protocol starts with dispensing an aqueous sample droplet (Sample Dispense supernode). The type of the sample is then identified and mixed with an associated barcoding droplet that is routed through the reconfigurable valve-based fabric (Identification and Labeling supernode). Next, according to the cell type, either GEA or ChIP procedures will be executed. If GEA is selected, then fluid-handling operations of cell-lysis, mRNA preparation, control preparation, and qPCR will be carried out. At the end of each bioassay, a detection operation is performed to ensure that the efficiency of the resulting solution is above a certain threshold, as described in Section 2.5. Similarly, if ChIP is selected, then fluid-handling operations of postfixation, cell-lysis, chromatin shearing, immuno-precipitation, DNA washing, control preparation, and qPCR will be performed.

In addition to the CFG model, a state machine is utilized to model the progression of each cell along the single-cell pipeline. Typically, the hybrid platform can iteratively process thousands of cells; such cells might be scattered across the platform domains at any given point in time. Therefore, this state machine (Figure 5.7) is necessary to keep track of the cells that are being processed simultaneously.

Co-Synthesis Methodology

In this section, we describe the synthesis problem and present an overview of the proposed co-synthesis methodology. Table 5.2 summarizes the notation used in this chapter.

Problem Formulation

Our optimization problem is as follows:

Inputs: (i) The protocol CFG Gc. (ii) A matrix C: each vector Cj € C corresponds to a cell, and consists of integers that encode cell state machine, cell type, and the assigned bioassays in Gc. (iii) The configuration of the valve-based system; this information includes the graph J-Ubxmb, the number of inputs щ, and the number of outputs ть. (iv) The types of resources corresponding to the DMFB, their operation time, and the routing distance between each pair of resources.

Output: Allocation of chip modules by the individual cells, protocol completion time Tcornp.

Objective: Minimize Tcomp to provide high throughput and minimize Tresp to improve system responsiveness.


Notation used in Chapter 5.


The graph model of an щ-Ьо-ть crossbar

Fпь x гпь

The flow-decision model of an щАо-ть crossbar


The set of vertices in Pu,,-xmb


^nb xmb

The set of unoccupied vertices in РПьХГПь


A set of vertices in P„bX,nil representing a routing path


A Boolean variable; True if a path Pi, is complete


The graph model of a DMFB


The set of DMFB resources


The set of unoccupied DMFB resources (P С P)


Minimum value of the cost function associated with P


Cell metadata


The set of fluidic-operation types


The control-flow graph of a protocol


The DTMC model of a protocol


The set of states of Л4


The transition-probability matrix of Ad

Proposed Solution

The proposed co-synthesis scheme, depicted in Figure 5.8, consists of four components: (1) valve-based synthesizer, which is used to route barcoding droplets through the valve-based crossbar; (2) DMFB synthesizer, which is utilized for allocating DMFB resources, e.g., mixers and heaters, to sample pathways; (3) biology-sample model, which records the progress of a sample (cell) within the protocol CFG and also provides updated resource preferences; (4) time-wheel engine, which seamlessly coordinates real-time interactions between the individual sample models and the synthesizers of the hybrid system. Note that the stages of the single-cell pipeline, simulated by this scheme, match the states of the cell state machine (Figure 5.7).

The time-wheel interacts with other components through APIs. For example, whenever the time-wheel locates an available fluorescence detector at the DMFB. a new sample model is initialized (Figure 5.8) and the associated cell is allocated to the detector in order to perform type identification. Next, when the cell type is identified and there are available valve-based routes to route the associated barcoding droplet, the time-wheel triggers the valve-based synthesizer to start the pipelined routing process of the barcoding droplet; valve- based routing is performed through iterations until the droplet reaches the electrode interface at the digital-microfluidic side and is mixed with the cell. We discuss two methods for valve-based routing in Section 5.4.

When a DMFB resource is available to further process the cell, the previously reserved valve-based channels are released by the time-wheel. Hence,


Overview of the proposed co-synthesis methodology.

real-time resource allocation for the DMFB is also initiated by the time-wheel, which in turn, commits a cell pathway whenever its particular single-cell bioassays have executed. Based on an intermediate decisions whose outcome is communicated to the sample model, the cell might also be discarded during analysis.

DMFB Synthesizer

We use a greedy method to solve the resource-allocation problem in the DMFB; the pseduocode is shown in Algorithm 5.1. We denote a DMFB resource by r,1Z, where 7Z encapsulates all DMFB resources. Thus, the cost of allocating resource r, to execute a fluidic operation of type ayA (the set A incorporates all operation types) is "(?’,, r,. yy) = ОТ(r,. ay) + CR(rj, ri), where ОТ {г,, ay) is the operation time on r; and CR(rj,ri) is the routing distance from rj (the currently occupied resource) to r,. The worst-case computational complexity of this algorithm is 0(|V/|).

Algorithm 5.1 DMFB Resource Allocation Input: Cj, Gf. current simulation time “f”

Output: Assigned Resource “rj” l: R 4- GetCurrentlyUnoccupiedResources(G/, t):

  • 2: if (1Z is empty) then return NULL;
  • 4: sf- CalculateMinimumCostAllAvailableResources^j, TZ);
  • 5: if (s = oc) then return NULL; i> No suitable resource
  • 6: Г; 4- GETSELECTEDRESOURCE(s): return rj;
< Prev   CONTENTS   Source   Next >