Transcript mix - Bill Thies

Bringing Programmability to
Experimental Biology
Bill Thies
Joint work with Vaishnavi Ananthanarayanan, J.P. Urbanski,
Nada Amin, David Craig, Jeremy Gunawardena,
Todd Thorsen, and Saman Amarasinghe
Microsoft Research India
ICIP 2011
Microfluidic Chips
• Idea: a whole biology lab on a single chip
– Input/output
– Sensors: pH, glucose,
temperature, etc.
– Actuators: mixing, PCR,
electrophoresis, cell lysis, etc.
• Benefits:
– Small sample volumes
– High throughput
• Applications:
– Biochemistry
- Cell biology
– Biological computing
1 mm 10x real-time
Application to Rural Diagnostics
Disposable
Enteric Card
PATH,
Washington U.
Micronics, Inc.,
U. Washington
Targets:
- E. coli, Shigella,
Salmonella,
C. jejuni
DxBox
CARD
U. Washington,
Micronics, Inc.,
Nanogen, Inc.
Rheonix, Inc.
Targets:
- malaria (done)
- dengue, influenza,
Rickettsial diseases,
typhoid, measles
(under development)
Targets:
- HPV diagnosis
- Detection of
specific gene
sequences
Moore’s Law of Microfluidics:
Valve Density Doubles Every 4 Months
Source: Fluidigm Corporation (http://www.fluidigm.com/images/mlaw_lg.jpg)
Moore’s Law of Microfluidics:
Valve Density Doubles Every 4 Months
Source: Fluidigm Corporation (http://www.fluidigm.com/didIFC.htm)
Current Practice: Manage Gate-Level
Details from Design to Operation
• For every change in the experiment or the chip design:
fabricate
chip
1. Manually draw in AutoCAD
2. Operate each gate from LabView
Abstraction Layers for Microfluidics
Silicon Analog
Protocol Description Language
- architecture-independent protocol description
Fluidic Instruction Set Architecture (ISA)
- primitives for I/O, storage, transport, mixing
C
x86
Pentium III,
Pentium IV
chip 1
chip 2
chip 3
Fluidic Hardware Primitives
- valves, multiplexers, mixers, latches
transistors,
registers, …
Abstraction Layers for Microfluidics
Contributions
Protocol Description Language
- architecture-independent protocol description
Fluidic Instruction Set Architecture (ISA)
- primitives for I/O, storage, transport, mixing
BioCoder Language
[J.Bio.Eng. 2010]
Optimized Compilation
[Natural Computing 2007]
Demonstrate Portability
[DNA 2006]
Micado AutoCAD Plugin
chip 1
chip 2
chip 3
Fluidic Hardware Primitives
- valves, multiplexers, mixers, latches
[MIT 2008, ICCD 2009]
Digital Sample Control
Using Soft Lithography
[Lab on a Chip ‘06]
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Thick layer (poured)
Thin layer (spin-coated)
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
Primitive 1: A Valve (Quake et al.)
Control
Layer
Flow
Layer
pressure
actuator
Primitive 2: A Multiplexer (Thorsen et al.)
Bit 2
0 1
Bit 1
0 1
Bit 0
0 1
flow layer
control layer
Output 7
Output 6
Output 5
Input
Output 4
Output 3
Output 2
Output 1
Output 0
Primitive 2: A Multiplexer (Thorsen et al.)
Bit 2
0 1
Bit 1
0 1
Bit 0
0 1
flow layer
control layer
Output 7
Output 6
Output 5
Input
Output 4
Output 3
Output 2
Output 1
Output 0
Example: select 3 = 011
Primitive 2: A Multiplexer (Thorsen et al.)
Bit 2
0 1
Bit 1
0 1
Bit 0
0 1
flow layer
control layer
Output 7
Output 6
Output 5
Input
Output 4
Output 3
Output 2
Output 1
Output 0
Example: select 3 = 011
Primitive 2: A Multiplexer (Thorsen et al.)
Bit 2
0 1
Bit 1
0 1
Bit 0
0 1
flow layer
control layer
Output 7
Output 6
Output 5
Input
Output 4
Output 3
Output 2
Output 1
Output 0
Example: select 3 = 011
Primitive 3: A Mixer (Quake et al.)
1. Load sample on bottom
2. Load sample on top
3. Peristaltic pumping
Rotary Mixing
Abstraction Layers for Microfluidics
Protocol Description Language
- architecture-independent protocol description
Fluidic Instruction Set Architecture (ISA)
- primitives for I/O, storage, transport, mixing
chip 1
chip 2
chip 3
Fluidic Hardware Primitives
- valves, multiplexers, mixers, latches
Driving Applications
1. What are the best indicators for oocyte viability?
-
-
With Mark Johnson’s and
Todd Thorsen’s groups
During in-vitro fertilization,
monitor cell metabolites and
select healthiest embryo for implantation
2. How do mammalian signal transduction pathways
respond to complex inputs?
-
With Jeremy Gunawardena’s
and Todd Thorsen’s groups
Isolate cells and stimulate with
square wave, sine wave, etc.
CAD Tools for Microfluidic Chips
• Goal: automate placement, routing, control of
microfluidic features
• Why is this different than electronic CAD?
CAD Tools for Microfluidic Chips
• Goal: automate placement, routing, control of
microfluidic features
• Why is this different than electronic CAD?
1. Control ports (I/O pins) are bottleneck to scalability
– Pressurized control signals cannot yet be generated on-chip
– Thus, each logical set of valves requires its own I/O port
2. Control signals correlated due to continuous flows
pipelined flow
continuous flow
 Demand & opportunity for minimizing control logic
Our Technique:
Automatic Generation of Control Layer
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
2. Infer control valves
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
2. Infer control valves
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
2. Infer control valves
3. Infer control sharing
Our Technique:
Automatic Generation of Control Layer
1. Describe Fluidic ISA
2. Infer control valves
3. Infer control sharing
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
5.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Generate an interactive GUI
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
5.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Generate an interactive GUI
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
5.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Generate an interactive GUI
Our Technique:
Automatic Generation of Control Layer
1.
2.
3.
4.
5.
Describe Fluidic ISA
Infer control valves
Infer control sharing
Route valves to control ports
Generate an interactive GUI
Routing Algorithm
• Build on recent algorithm
for simultaneous pin
assignment & routing
[Xiang et al., 2001]
• Idea: min cost - max flow
from valves to ports
• Our contribution: extend algorithm to allow sharing
– Previous capacity constraint on each edge:
f1 + f2 + f3 + f4 + f5 + f6 ≤ 1
– Modified capacity constraint on each edge:
max(f1, f4) + max(f2 , f3) + f5 + f6 ≤ 1
Solve with linear programming, allowing sharing where beneficial
Routing Algorithm
• Build on recent algorithm
for simultaneous pin
assignment & routing
[Xiang et al., 2001]
• Idea: min cost - max flow
from valves to ports
• Our contribution: extend algorithm to allow sharing
– Previous capacity constraint on each edge:
f1 + f2 + f3 + f4 + f5 + f6 ≤ 1
– Modified capacity constraint on each edge:
max(f1, f4) + max(f2 , f3) + f5 + f6 ≤ 1
Solve with linear programming, allowing sharing where beneficial
Embryonic Cell Culture
Courtesy J.P. Urbanski
Embryonic Cell Culture
Courtesy J.P. Urbanski
Cell Culture with Waveform Generator
Courtesy David Craig
Cell Culture with Waveform Generator
Courtesy David Craig
Metabolite Detector
Courtesy J.P. Urbanski
Metabolite Detector
Courtesy J.P. Urbanski
Micado: An AutoCAD Plugin
• Implements ISA, control inference, routing, GUI export
– Using slightly older algorithms
than presented here [Amin ‘08]
– Parameterized design rules
– Incremental construction of chips
• Realistic use by at least 3
microfluidic researchers
• Freely available at:
http://groups.csail.mit.edu/cag/micado/
Open Problems
• Automate the design of the flow layer
– Hardware description language for microfluidics
– Define parameterized and reusable modules
• Replicate and pack a primitive as densely as possible
– How many cell cultures can you fit on a chip?
• Support additional primitives and functionality
–
–
–
–
–
Metering volumes
Sieve valves
Alternate mixers
Separation primitives
…
Abstraction Layers for Microfluidics
Protocol Description Language
- architecture-independent protocol description
Fluidic Instruction Set Architecture (ISA)
- primitives for I/O, storage, transport, mixing
chip 1
chip 2
chip 3
Fluidic Hardware Primitives
- valves, multiplexers, mixers, latches
Toward “General Purpose”
Microfluidic Chips
In
Fluidic
Storage
(RAM)
Out
Outputs
Inputs
Sensors
Mixing
and
Chambers
Actuators
Towards a Fluidic ISA
• Microfluidic chips have various mixing technologies
– Electrokinetic mixing [Levitan et al.]
– Droplet mixing [Fair et al.]
– Rotary mixing [Quake et al.]
• Common attributes:
– Ability to mix two samples in equal proportions, store result
• Fluidic ISA: mix (int src1, int src2, int dst)
– Ex: mix(1, 2, 3)
Storage Cells
1
2
3
4
Mixer
– To allow for lossy transport, only 1 unit of mixture retained
Implementation: Oil-Driven Chip
Inputs Storage Cells Background Phase Wash Phase
Chip 1
2
8
Oil
—
Mixing
Rotary
Implementation: Oil-Driven Chip
mix (S1, S2, D) {
1. Load S1
2. Load S2
3. Rotary mixing
4. Store into D
}
50x real-time
Inputs Storage Cells Background Phase Wash Phase
Chip 1
2
8
Oil
—
Mixing
Rotary
Implementation 2: Air-Driven Chip
Inputs Storage Cells Background Phase Wash Phase
Mixing
Chip 1
2
8
Oil
—
Rotary
Chip 2
4
32
Air
Water
In channels
Implementation 2: Air-Driven Chip
mix (S1, S2, D) {
1. Load S1
2. Load S2
3. Mix / Store into D
4. Wash S1
5. Wash S2
}
50x real-time
Inputs Storage Cells Background Phase Wash Phase
Mixing
Chip 1
2
8
Oil
—
Rotary
Chip 2
4
32
Air
Water
In channels
“Write Once, Run Anywhere”
• Example: Gradient generation
Fluid yellow = input (0);
Fluid blue = input(1);
for (int i=0; i<=4; i++) {
mix(yellow, 1-i/4, blue, i/4);
}
• Hidden from programmer:
–
–
–
–
Location of fluids
Details of mixing, I/O
Logic of valve control
Timing of chip operations
450 Valve Operations
Algorithms for Efficient Mixing
• Mixing is fundamental operation of microfluidics
– Prepare samples for analysis
– Dilute concentrated substances
– Control reagant volumes
Analogous to ALU operations on microprocessors
• How to synthesize complex mixture using simple steps?
– Many systems support only 50/50 mixers
– Should minimize number of mixes, reagent usage
– Note: some mixtures only reachable within error tolerance 
Interesting scheduling and optimization problem
• N
Why Not Binary Search?
0
3/8
1
1/2
1/4
3/8
1/2
5 inputs, 4 mixes
Why Not Binary Search?
0
3/8
1
1/2
3/4
3/8
4 inputs, 3 mixes
1/2
1/4
3/8
1/2
5 inputs, 4 mixes
Min-Mix Algorithm
•
Simple algorithm yields minimal number of mixes
– For any number of reagents, to any reachable concentration
– Also minimizes reagent usage on certain chips
Min-Mix Algorithm: Key Insights
1. The mixing process can be represented by a tree.
A
B
B
A
5/8 A, 3/8 B
Min-Mix Algorithm: Key Insights
1. The mixing process can be represented by a tree.
d
2-d
3
1/8
2
1/4
1
1/2
A
B
B
A
5/8 A, 3/8 B
2. The contribution of an input sample to the overall mixture
is 2-d, where d is the depth of the sample in the tree
Min-Mix Algorithm: Key Insights
1. The mixing process can be represented by a tree.
d
2-d
3
1/8
1
2
1/4
0
1
1/2
1
A
A
5 = 101
B
1
B
1
0
3 = 011
5/8 A, 3/8 B
2. The contribution of an input sample to the overall mixture
is 2-d, where d is the depth of the sample in the tree
3. In the optimal mixing tree, a reagent appears at depths
corresponding to the binary representation of its overall
concentration.
Min-Mix Algorithm
• Example: mix 5/16 A, 7/16 B, 4/16 C
d
2-d
4
1/16
3
1/8
2
1/4
1
1/2
A
B
A
B
A
A=5
=0101
B
B=7
=0111
B
B
C
A
B
C
C=4
=0100
• To mix k fluids with precision 1/n:
– Min-mix algorithm: O(k log n) mixes
– Binary search: O(k n) mixes
[Natural Computing 2007]
Abstraction Layers for Microfluidics
Protocol Description Language
- architecture-independent protocol description
Fluidic Instruction Set Architecture (ISA)
- primitives for I/O, storage, transport, mixing
chip 1
chip 2
chip 3
Fluidic Hardware Primitives
- valves, multiplexers, mixers, latches
“Immunological detection ... was carried out as
described in the Boehringer digoxigenin-nucleic
acid detection kit with some modifications.”
- Main paper
- References
- Ref. papers
BioCoder: A High-Level Programming
Language for Biology Protocols
In biology publications, can we replace the textual
description of the methods used with a computer program?
1. Enable automation
via microfluidic chips
2. Improve reproducibility
of manual experiments
Example: Plasmid DNA Extraction
I. Original protocol (Source: Klavins Lab)
Add 100 ul of 7X Lysis Buffer (Blue) and mix by inverting the
tube 4-6 times. Proceed to step 3 within 2 minutes.
II. BioCoder code
FluidSample f1 = measure_and_add(f0, lysis_buffer, 100*uL);
FluidSample f2 = mix(f1, INVERT, 4, 6);
time_constraint(f1, 2*MINUTES, next_step);
III. Auto-generated text output
Add 100 ul of 7X Lysis Buffer (Blue).
Invert the tube 4-6 times.
NOTE: Proceed to the next step within 2 mins.
Example: Plasmid DNA Extraction
Auto-Generated
Dependence Graph
BioCoder Language Primitives
• Declaration / measurement / disposal
- declare_fluid
- declare_column
- measure_sample
- measure_fluid
- volume
- discard
- transfer
- transfer_column
- declare_tissue
• Combination / mixing
- combine
- mix
- combine_and_mix
- addto_column
- mixing_table
• Centrifugation
- centrifuge_pellet
- centrifuge_phases
- centrifuge_column
• Temperature
- set_temp
- use_or_store
- autoclave
• Timing
- wait
- time_constraint
- store_until
- inoculation
- invert_dry
• Detection
- ce_detect
- gas_chromatography
- nanodrop
- electrophoresis
- mount_observe_slide
- sequencing
Standardizing Ad-Hoc Language
• Need to convert qualitative words to quantitative scale
• Example: a common scale for mixing
–
–
–
–
–
When a protocol says “mix”, it could mean many things
Level 1: tap
Level 2: stir
Level 3: invert
Level 4: vortex / resuspend / dissolve
• Similar issues with temperature, timing, opacity, …
Separating Instructions from Hints
• How to translate abstract directions?
– “Remove the medium by aspiration, leaving the bacterial
pellet as dry as possible.”
centrifuge(&medium, ...);
hint(pellet_dry)
Aspirate and remove medium.
Leave the pellet as dry as possible.
• Hints provide tutorial or self-check information
– Can be ignored if rest of protocol is executed correctly
Benchmark Suite
65 protocols
5800 LOC
Example: PCR
repeat
thermocycling
Example: Molecular Barcodes
Preparation
+ PCR (2)
Example: DNA Sequencing
Preparation
PCR PCR PCR PCR
Analysis
Validating the Language
• Eventual validation: automatic execution
– But BioCoder more capable than most chips today
– Need to decouple language research from microfluidics
research
• Initial validation: human execution
– In collaboration with Prof. Utpal Nath’s lab at IISc
– Target Plant DNA Isolation, common task for summer intern
Original
Lab Notes
BioCoder
Code
Auto-Generated
Protocol
Execution
in Lab
Biologist is never exposed to original lab notes
• To the best of our knowledge, first execution of a real
biology protocol from a portable programming language
Growing a Community
Growing a Community
Growing a Community
Conclusions
• Abstraction layers for
a programmable biology
– CAD tools for microfluidics
– Fluidic ISA
– BioCoder language
• Vision for microfluidics:
everyone uses standard chip
• Vision for software:
a de-facto language for protocols
– Download a colleague’s code,
run it on your chip
– Compose modules and libraries
to enable complex experiments
that are impossible to perform today