Digital microfluidic biochips

Digital

MicrofluiDic

Biochips

Design Automation

and Optimization

Digital

MicrofluiDic

Biochips

Design Automation

and Optimization

Krishnendu chakrabarty

tao Xu

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

© 2010 by Taylor and Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Printed in the United States of America on acid-free paper

10 9 8 7 6 5 4 3 2 1

International Standard Book Number: 978-1-4398-1915-9 (Hardback)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts

have been made to publish reliable data and information, but the author and publisher cannot assume

responsibility for the validity of all materials or the consequences of their use. The authors and publishers

have attempted to trace the copyright holders of all material reproduced in this publication and apologize to

copyright holders if permission to publish in this form has not been obtained. If any copyright material has

not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit￾ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented,

including photocopying, microfilming, and recording, or in any information storage or retrieval system,

without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.

com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood

Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and

registration for a variety of users. For organizations that have been granted a photocopy license by the CCC,

a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used

only for identification and explanation without intent to infringe.

Library of Congress Cataloging‑in‑Publication Data

Chakrabarty, Krishnendu.

Digital microfluidic biochips : design automation and optimization / authors,

Krishnendu Chakrabarty and Tao Xu.

p. cm.

“A CRC title.”

Includes bibliographical references and index.

ISBN 978-1-4398-1915-9 (hard back : alk. paper)

1.  Biochips. 2.  Microfluidics. 3.  Microfluidic devices. 4.  Digital electronics.  I. Xu,

Tao, 1982- II. Title.

R857.B5C455 2010

610.285--dc22 2009052543

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

To my parents and my dear fiancée, Tong

Tao Xu

To Kamalika, Arunangshu, Ishani, and Arijit

Krishnendu Chakrabarty

vii

Contents

Preface......................................................................................................................xi

Acknowledgments .............................................................................................. xiii

1 Introduction.....................................................................................................1

1.1 Digital Microfluidic Technology.........................................................4

1.2 Synthesis, Testing, and Pin-Constrained Design Techniques........6

1.3 Protein Crystallization ....................................................................... 11

1.4 Book Outline........................................................................................ 13

References ....................................................................................................... 15

2 Defect-Tolerant and Routing-Aware Synthesis ...................................... 19

2.1 Background.......................................................................................... 19

2.2 Routing-Aware Synthesis...................................................................20

2.2.1 Droplet-Routability Estimation............................................ 21

2.2.2 Routing Time Cost and Assay Completion Time..............23

2.3 Defect-Tolerant Synthesis................................................................... 24

2.3.1 Postsynthesis Defect Tolerance............................................ 24

2.3.2 Presynthesis Defect Tolerance..............................................25

2.3.2.1 Defect Tolerance Index ..........................................25

2.3.2.2 Partial Reconfiguration and Partial

Resynthesis..............................................................26

2.4 Simulation Results ..............................................................................27

2.4.1 Results for Routing-Aware Synthesis..................................29

2.4.2 Results for Postsynthesis Defect Tolerance ........................ 32

2.4.3 Results for Presynthesis Defect Tolerance..........................33

2.5 Chapter Summary and Conclusions ................................................36

References ....................................................................................................... 37

3 Pin-Constrained Chip Design ...................................................................43

3.1 Droplet-Trace-Based Array-Partitioning Method...........................43

3.1.1 Impact of Droplet Interference and Electrode￾Addressing Problem..............................................................43

3.1.1.1 Impact of Droplet Interference .............................43

3.1.1.2 Minimum Number of Pins for a Single

Droplet.....................................................................44

3.1.1.3 Pin-Assignment Problem for Two Droplets .......45

3.1.2 Array Partitioning and Pin-Assignment Methods ...........47

3.1.3 Pin-Assignment Algorithm..................................................50

3.1.4 Application to Multiplexed Bioassay ..................................53

viii Contents

3.2 Cross-Referencing-Based Droplet Manipulation Method ............55

3.2.1 Cross-Referencing Addressing ............................................55

3.2.2 Power-Efficient Interference-Free Droplet Manipulation

Based on Destination-Cell Categorization.........................57

3.2.2.1 Electrode Interference............................................57

3.2.2.2 Fluidic Constraints................................................. 57

3.2.2.3 Destination-Cell Categorization ..........................57

3.2.2.4 Graph-Theoretic Model and Clique

Partitioning .............................................................60

3.2.2.5 Algorithm for Droplet Grouping ......................... 61

3.2.3 Scheduling of Routing for Efficient Grouping................... 62

3.2.4 Variant of Droplet-Manipulation Method for

High-Throughput Power-Oblivious Applications ............66

3.2.5 Simulation Results .................................................................66

3.2.5.1 Random Synthetic Benchmarks ...........................66

3.2.5.2 A Multiplexed Bioassay Example ........................ 67

3.3 Broadcast-Addressing Method.......................................................... 74

3.3.1 “Don’t-Cares” in Electrode-Actuation Sequences............. 74

3.3.2 Optimization Based on Clique Partitioning in Graphs...... 76

3.3.3 Broadcast Addressing for Multifunctional Biochips ........78

3.3.4 Experimental Results ............................................................78

3.3.4.1 Multiplexed Assay..................................................78

3.3.4.2 Polymerase Chain Reaction (PCR)....................... 81

3.3.4.3 Protein Dilution......................................................82

3.3.4.4 Broadcast Addressing for a

Multifunctional Chip.............................................83

3.4 Chapter Summary and Conclusions ................................................85

References .......................................................................................................86

4 Testing and Diagnosis ................................................................................. 91

4.1 Parallel Scan-Like Test........................................................................ 91

4.1.1 Off-Line Test and Diagnosis.................................................95

4.1.2 Online Parallel Scan-Like Test........................................... 100

4.2 Diagnosis of Multiple Defects ......................................................... 101

4.2.1 Incorrectly Classified Defects ............................................ 101

4.2.2 Untestable Sites..................................................................... 102

4.3 Performance Evaluation................................................................... 104

4.3.1 Complexity Analysis ........................................................... 104

4.3.2 Probabilistic Analysis.......................................................... 104

4.3.3 Occurrence Probability of Untestable Sites ...................... 106

4.4 Application to a Fabricated Biochip ............................................... 108

4.5 Functional Test .................................................................................. 110

4.5.1 Dispensing Test.................................................................... 112

4.5.2 Routing Test and Capacitive Sensing Test........................ 113

4.5.3 Mixing and Splitting Test................................................... 114

Contents ix

4.5.4 Application to Pin-Constrained Chip Design ................. 118

4.5.4.1 An n-Phase Chip .................................................. 119

4.5.4.2 Cross-Referencing-Based Chip........................... 120

4.5.4.3 Array-Partitioning-Based Chip .......................... 120

4.5.4.4 Broadcast-Addressing-Based Chip .................... 121

4.6 Experimental and Simulation Results ...........................................123

4.7 Chapter Summary and Conclusions .............................................. 128

References ..................................................................................................... 129

5 Design-for-Testability for Digital Microfluidic Biochips .................. 135

5.1 Testability of a Digital Microfluidic Biochip................................. 135

5.2 Testability-Aware Pin-Constrained Chip Design......................... 138

5.2.1 Design Method..................................................................... 138

5.2.2 Euler-Path-Based Functional Test Method for

Irregular Chip Layouts ....................................................... 140

5.3 Simulation Results ............................................................................ 141

5.3.1 Multiplexed Assay ............................................................... 142

5.3.2 Polymerase Chain Reaction (PCR) .................................... 143

5.4 Chapter Summary and Conclusions .............................................. 146

References ..................................................................................................... 146

6 Application to Protein Crystallization................................................... 151

6.1 Chip Design and Optimization ...................................................... 151

6.1.1 Pin-Constrained Chip Design............................................ 152

6.1.2 Shuttle-Passenger-Like Well-Loading Algorithm........... 157

6.1.3 Chip Testing.......................................................................... 159

6.1.4 Defect Tolerance................................................................... 161

6.1.4 Evaluation of Well-Loading Algorithm and

Defect Tolerance................................................................... 164

6.1.4.1 Loading Time........................................................ 164

6.1.4.2 Defect Tolerance ................................................... 164

6.2 Automated Solution Preparation.................................................... 165

6.2.1 Efficient Solution-Preparation Planning Algorithm....... 166

6.2.1.1 Concentration Manipulation Using

Mixing and Dispensing....................................... 166

6.2.1.2 Solution-Preparation Algorithm ........................ 167

6.2.2 Experimental Results and Comparison............................ 173

6.3 Chapter Summary and Conclusions .............................................. 173

References ..................................................................................................... 174

7 Conclusions and Future Work.................................................................. 179

7.1 Book Contributions........................................................................... 179

7.2 Future Work....................................................................................... 180

7.2.1 Synthesis Based on Physical Constraints ......................... 181

7.2.1.1 Mismatch Problems ............................................. 181

x Contents

7.2.1.2 Synthesis Guided by Physical Constraints ....... 183

7.2.2 Control-Path Design and Synthesis................................... 183

7.2.2.1 Control-Path Design Based on Error

Propagation ........................................................... 184

7.2.2.2 Control-Path Synthesis ........................................ 185

References ..................................................................................................... 186

Index ..................................................................................................................... 191

xi

Preface

Microfluidics-based biochips combine electronics with biochemistry to open

new application areas such as point-of-care medical diagnostics, on-chip DNA

analysis, automated drug discovery, and protein crystallization. Bioassays

can be mapped to microfluidic arrays using synthesis tools, and they can

be executed through the electronic manipulation of sample and reagent

droplets. The 2007 International Technology Roadmap for Semiconductors

articulates the need for innovations in biochip and microfluidics as part of

functional diversification (“Higher Value Systems” and “More than Moore”).

This document also highlights “Medical” as being a System Driver for 2009.

This book envisions an automated design flow for microfluidic biochips,

in the same way as design automation revolutionized IC design in the

1980s–1990s. Electronic design-automation techniques are leveraged when￾ever possible, and new design-automation solutions are developed for prob￾lems that are unique to digital microfluidics. Biochip users (e.g., chemists,

nurses, doctors, and clinicians) and the biotech/pharmaceutical industry

will adapt more easily to new technology if appropriate design tools and

in-system automation methods are made available.

The book is focused on a design automation framework that addresses

optimization problems related to layout, synthesis, droplet routing, testing,

and testing for digital microfluidic biochips. The optimization goal includes

the minimization of time-to-response, chip area, and test complexity. The

emphasis here is on practical issues such as defects, fabrication cost, physical

constraints, and application-driven design. To obtain robust, easy-to-route

chip designs, a unified synthesis method is presented to incorporate droplet

routing and defect tolerance in architectural synthesis and physical design.

It allows routing-aware architectural-level design choices and defect-tolerant

physical design decisions to be made simultaneously.

In order to facilitate the manufacture of low-cost and disposable biochips,

design methods that rely on a small number of control pins are also pre￾sented. Three techniques are introduced for the automated design of such

pin-constraint biochips. First, a droplet-trace-based array partitioning method

is combined with an efficient pin assignment technique, referred to as the

“Connect-5 algorithm.” The second pin-constrained design method is based

on the use of “rows” and “columns” to access electrodes. An efficient drop￾let manipulation method is presented for this cross-referencing technique.

The method maps the droplet-movement problem to the clique-partitioning

problem from graph theory, and it allows simultaneous movement of a large

number of droplets on a microfluidic array.

The third pin-constrained design technique is referred to as broadcast￾addressing. This method provides high throughput for bioassays, and it

xii Preface

reduces the number of control pins by identifying and connecting control

pins with “compatible” actuation sequences.

Dependability is another important attribute for microfluidic biochips,

especially for safety-critical applications such as point-of-care health assess￾ment, air-quality monitoring, and food-safety testing. Therefore, these

devices must be adequately tested after manufacture and during bioassay

operations. This book presents a cost-effective testing method, referred to as

“parallel scan-like test,” and a rapid diagnosis method based on test outcomes.

The diagnosis outcome can be used for dynamic reconfiguration, such that

faults can be easily avoided, thereby enhancing chip yield and defect toler￾ance. The concept of functional test for digital biochip is also introduced for

the first time in this book. Functional test methods address fundamental bio￾chip operations such as droplet dispensing, droplet transportation, mixing,

splitting, and capacitive sensing.

To facilitate the application of the above testing methods and to increase

their effectiveness, the concept of design-for-testability (DFT) for micro￾fluidic biochips is introduced in this book for the first time. A DFT method is

presented that incorporates a test plan into the fluidic operations of a target

bioassay protocol.

The above optimization tools are used for the design of a digital micro￾fluidic biochip for protein crystallization, a commonly used technique to

understand the structure of proteins. An efficient solution-preparation algo￾rithm is presented to generate a solution-preparation plan that lists the inter￾mediate mixing steps needed to generate target solutions with the required

concentrations. A multiwell, high-throughput digital microfluidic biochip

prototype for protein crystallization is also designed.

This book grew out of an ongoing research project on design automation

for biochips at Duke University. The results of this research have been pub￾lished as papers in a number of journals and conference proceedings. The

chapters in this book present all these results as a research monograph in a

single volume. It can be used as a reference book for academic and indus￾trial researchers in the areas of digital microfluidic biochips and electronic

design automation.

In summary, the research project on which the book is based has led to a

set of practical design tools for digital microfluidics. A protein crystallization

chip has been designed to highlight the benefits of this automated design

flow. It is anticipated that additional biochip applications will also benefit

from these optimization methods.

xiii

Acknowledgments

We are grateful to Nora Konopka of CRC Press for encouraging us to pursue

this book project. We are also grateful to IEEE and ACM for granting us

copyright permission to use materials from our published work. This book

grew out of a research project funded by the National Science Foundation

(NSF). We thank NSF Program Directors Dr. Sankar Basu and Dr. Dmitry

Maslov for supporting this work. We acknowledge the inputs received

from Prof. Richard B. Fair, who leads the digital microfluidic group at Duke

University. We also thank Dr. Vamsee Pamula and Dr. Michael Pollack,

co-founders of Advanced Liquid Logic, for their collaboration. Finally, we

acknowledge the contributions of Dr. Fei Su, Dr. Vijay Srinivasan, Dr. Phil

Paik, William Hwang, and numerous other colleagues who participated in

this research project.

1

1

Introduction

Microfluidics-based biochips, also referred to as lab-on-a-chip, are revo￾lutionizing many areas of biochemistry and biomedical sciences. Typical

applications include enzymatic analysis (e.g., lactate assays), DNA sequenc￾ing, immunoassays, proteomic analysis, blood chemistry for clinical diag￾nostics, and environmental toxicity monitoring [1–3]. These devices enable

the precise control of microliter and nanoliter volumes of biological samples.

They combine electronics with biology, and they integrate various bioassay

operations such as sample preparation, analysis, separation, and detection

[1,4]. Compared to conventional laboratory experiment procedures, which

are usually cumbersome and expensive, these miniaturized and automated

biochip devices offer a number of advantages such as higher sensitivity, lower

cost due to smaller sample and reagent volumes, higher levels of system inte￾gration, and less likelihood of human error.

A popular class of microfluidic biochips is based on continuous fluid flow

in permanently etched microchannels. These devices rely on either micro￾pumps and microvalves; or electrical methods such as electrokinetics, to

control continuous fluidic flow [4,5]. Some recent continuous-flow biochip

products include the Topaz™ system for protein crystallization from

Fluidigm Corporation, the LabChip system from Caliper Life Sciences, and

the LabCD™ system from Tecan Systems [6–8].

An alternative category of microfluidic biochips relies on “digital micro￾fluidics,” which is based on the principle of electrowetting-on-dielectric [9–12].

Since discrete droplets of nanoliter volumes can be manipulated using a pat￾terned array of electrodes, miniaturized bioassay protocols (in terms of liquid

volumes and assay times) can be mapped and executed on a microfluidic

chip. Therefore, digital microfluidic biochips require only nanoliter volumes

of samples and reagents. They offer continuous sampling and analysis capa￾bilities for online and real-time chemical or biological sensing [13]. These

systems also have a desirable property referred to as dynamic reconfigurability,

whereby microfluidic modules can be relocated to other places on the elec￾trode array, without affecting functionality, during the concurrent execution

of a set of bioassays. Reconfigurability enables microfluidic biochips to be

“adaptive” to a wide variety of applications. System reconfiguration can also

be used to bypass faulty cells to enable microfluidic arrays to provide reliable

assay outcomes in the presence of defects.

Recent years have seen growing interest in automated chip design and opti￾mized mapping of multiple bioassays for concurrent execution on a digital