Exact Design of Digital Microfluidic Biochips 2019

文件名称: Exact Design of Digital Microfluidic Biochips 2019.pdf

所属分类: 专业指导

开发工具:

文件大小: 4mb

下载次数: 0

上传时间: 2019-09-07

提供者: drji*****

下载 (4mb)

不能下载？报告错误

详细说明：Exact Design of Digital Microfluidic Biochips Exact Design of Digital Microfluidic Biochips 2019.pdf (4.03 MB, 下载次数: 121 ) Many biological or medical experiments today are conducted manually by highly trained experts. Usually, a large laboratory requiring a lot of equipment is needed as welOliver keszocze· Robert wille· Rolf drechsler Exact Design of Digital Microfluidic Biochips Springer Oliver keszoczo Robert wille University of Bremen and dFKI Gmbh Johannes Kepler University Linz Bremen, germany Linz. austria Rolf drechsler University of Bremen and dFkI Gmbh Bremen, germany ISBN978-3-31990935-6 ISBN978-3-319-90936-3( e book) https://doi.org/10.10071978-3-319-90936-3 Library of Congress Control Number: 2018942500 o Springer International Publishing AG, part of Springer Nature 2019 his work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology ow known or hereafter developed The use of general descriptive names, registered names, trademarks, service marks, etc in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional laims in published maps and institutional affiliations Printed on acid-free paper This Springer imprint is published by the registered company Springer International Publishing AG part of Springer nati The registered company address is: Gewerbestrasse 11, 6330 Cha, Switzerland Preface Many biological or medical experiments today are conducted manually by highly trained experts. Usually, a large laboratory requiring a lot of equipment is needed as well. This makes the whole process expensive and does not allow for very high throughput This led to the development of automated laboratory equipment such as automated robots. These devices already allow for a high level of automation and integration. Unfortunately, laboratory robots are usually bulky(and expensive) and also use rather large amounts of liquids which may be very expensive on their own To further reduce the size of laboratory devices, researchers investigated how to manipulate liquids at a nanoliter or even picoliter volume scale. This led to the development of microfluidic biochips, also known as lab-on-a-chip The technical capabilities of microfluidic devices have been widely illustrated in the literature. An essential step for being able to actually make use of Digital Microfuidic Biochips (MFBS) is to properly design(or synthesize)those. This process includes to take a medical or biological assay description, a biochip geometry, and further constraints and determine a precise execution scheme for running the assay on the biochip As biochips grow in size and more complex assays are to be conducted, manual design of these devices is often not feasible anymore. Moreover, manual designs are often far from being optimal. Instead. high-quality design methodologies are ired which relieve the design burden of manual optimizations of assays time- consuming chip designs, as well as costly testing and maintenance procedures This book presents exact, that is minimal, solutions to individual steps in the design process as well as to a one-pass approach that combines all design steps i single step. The presented methods are easily adaptable to future needs. In addition to the minimal methods, heuristic approaches are provided and the complexity classes of (some of) the design problems are determined By this, the book summarizes the results of several years of intensive research at the University of Bremen, Germany, the dfkI gmbH Bremen, Germany, and the Johannes Kepler University Linz, Austria. This included several collaborations most importantly with the group of Prof Krishnendu Chakrabarty from the Duke University, USA, and the group of Prof. Tsung-Yi Ho from the National Tsin Hua University, Taiwan. We would like to sincerely thank both colleagues for Preface the very inspiring and fruitful joint work. Besides that, we are thankful to the coauthors of corresponding research papers which formed the basis of this book, including (in alphabetical order) Alexander Kroker, Andre Pols, Andreas Grimmer Jannis Stoppe, Kevin Leonard Schneider, Maximilian Luenert, Mohamed Ibrahim Tobias Boehnisch, and Zipeng Li. Furthermore, many thanks go to our research groups in Bremen and Linz for providing us with a comfortable and inspirational environment from which some authors benefit until today. Finally, we would like to thank Springer and, in particular, Charles"Chuck "Glaser for making this book possible Bremen, germany Oliver Keszocze Linz. austria Robert wille Bremen, Germany Rolf drechsler January 2018 Contents 1 Introduction 2 Background 2.1 Microfluidic biochips 2. 1.1 Microfluidic Operations 2.1.2 Fluidic constraints 12 2.2 Discrete dmfb model 14 2.2.1 Geometry of the biochip 15 2.2.2 Droplet Movement...................... 16 2.2.3 Electrode Actuation. ...........................................17 2.3 Reasoning Engines 19 2.3.1 Boolean Satisfiability...... 20 2.3.2 Satisfiability Modulo Theories 20 2.3.3 Integer Linear Programming 21 3 Routing 23 3.1 Problem formulatic 3.2 Compl of routin 3.3 Heuristic Approaches 28 3.4 Proposed solution 29 3.4.1 SAT Variables 30 3.4.2 SAT Constraints 3.5 Experimental results 34 3.6 Summary 37 4 Pin assignment 4.1 Problem formulation 39 4.2 Complexity of Pin Assignment.….…………,40 4.2.1 Reduction from Pin Assignment to Graph Coloring..... 41 4.2.2 Reduction from Graph Coloring to Pin Assignment......... 42 4.3 Related Work 44 Contents 4.4 Proposed solutions 4.4.1 Heuristic Approach 45 4.4.2 Exact Solution 4.5 Experimental Results 48 4. 5. 1 Evaluation of the Pin Assignment .............. 49 4.5.2 Optimizing the Pin assignment.…… 51 4.6 Summary.….… 53 5 Pin-Aware Routing and Extensions . 5.1 Pin-Aware Routing 5.1.1 SMT Formulation 5.1.2 Related Work 57 5.1. 3 Use Cases 57 5.2 Routing with Timing Information 53 Aging- Aware Routing………………… 5. 4 Routing with Different Cell Forms 66 5.4.1 Problem formulation 67 5.4.2 Transformation of routing Problems............68 5.4.3 SMT Formulation 68 5.4.4 Experimental results 69 5.5 Routing for Micro-Electrode-Dot-Array Biochips .......... 70 5. 5. 1 Motivation and background 5.5.2 MEDA Model and problem formulation 5.5.3 Related Work 74 5.5.4 Proposed Exact Routing Appro 5.5.5 Experimental Results 5.6 Summary 84 6 One-Pass Design 6. 1 The Design Gap Problem.......... 87 6.2 Proposed Solutions 88 6. 2. 1 Heuristic One-Pass Design 88 6.2.2 Exact One-Pass design 6.3 Experimental Results.…......…...…...102 6.3.1 Considered Benchmarks 102 6.3.2 Implementations 102 6.3.3 Evaluation of the Solution Length. ...........................103 6.3.4 Evaluating Iteration Schemes................. 105 6.3.5 Trade-Off Between Grid Size and Time Steps 106 6.4 Summary 107 7 Conclusion and Future ork 109 Contents ppendix a Bio gram: a Dedicated grammar for dMFB design Appendix b Bio Viz: An Interactive Visualization Tool for DMFB Design 115 B. 1 The Graphical User Interface ..116 B.2 Use Case: Interactive routing∴.….…….,19 B.2. 1 Implementation 120 B.2.2 Routing algorithms.…… 120 B.2.3 Case Study 121 Appendix C Notation ............................. 123 References ∴125 Index 131 Chapter 1 Introduction Check for Today, many biological or medical experiments are conducted manually by highly trained experts. Usually, a large laboratory requiring a lot of equipment is needed as well(see Fig. 1.la which shows a typical laboratory setup). This makes the whole process expensive and does not allow for very high throughput. Furthermore, as human beings are no perfectly working robots they are a source of errors especiall when many repetitive and monotonous steps are involved in a biological assay. This led to the development of automated laboratory equipment such as the robots shown in Fig. 1.1b. These devices already allow for a high level of automation and integration, even though in many cases they only physically imitate the steps a human being would perform. Despite already significantly easing laboratory work, this still leaves room for improvement since those laboratory robots are usuall bulky(and expensive) To further reduce the size of laboratory devices, researchers investigated how to manipulate liquids at a nanoliter or even picoliter volume scale. This led to the development of microfluidic biochips(see Fig. lIc), also known as lab-on-a-chip These are devices that automatically manipulate small amounts of liquids in order to perform(a subset of) the same experiments previously conducted in a laboratory In addition to simply saving liquids, which may be expensive or difficult to obtain smaller volumes can also result in shorter experiment execution times. In general, a higher throughput and sensitivity may be achieved The capabilities of microfluidic devices has been widely illustrated in the literature. Early works successfully demonstrate the applicability of biochips for multiplexed real-time polymerase chain reaction(PCR)[Liu+04] and colorimetric glucose assay for various bodily fluids [sri+03]. In [Fai+07], different applications for biochips, such as massively parallel dNA analysis, real-time bio-molecular detection and recognition are presented. In [HZC10], protein crystallization for drug discovery and glucose measurement for blood serum are reported to have successfully been implemented. Another area where biochips are of interest is sample preparation [HLC12, Bha+17a, Bha+17b]. Using biochips, this tedious O Springer International Publishing AG, part of Springer Nature 2019 O. Keszocze et al., Exact Design of Digital Microfluidic biochips, https://doi.org/10.10077978-3-319-90936-3

(系统自动生成,下载前可以参看下载内容)