基于演化算法的数字微流控芯片三维模块布局方法研究

AN EVOLUTIONARY ALGORITHM FOR THREE-DIMENSIONAL MODULE PLACEMENT OF DIGITAL MICROFLUIDIC BIOCHIPS

蒋陈

11849334

硕士

计算机技术

袁博

2020-05-30

2020-07-08

哈尔滨工业大学

深圳

数字微流控生物芯片是一种新兴技术，它可以将传统的生物实验室程序整合到一个小型生物芯片上，具有高精确度、自动化、低成本和高效率等优点，在生化分析、临床诊断和药物制备等领域具有广泛的应用前景。随着数字微流控芯片的尺寸越来越大，应用越来越复杂，我们需要更高质量的自动化软件以辅助其应用。数字微流控生物芯片流体层面的综合工具可以获得如何用芯片控制液滴以完成特定生化反应的信息，它包括四个步骤：资源绑定、操作调度、模块布局和液滴路由。综合过程中存在复杂的组合优化问题，适合使用遗传算法来解决。本研究的目的在于对数字微流控芯片流体层面的综合过程进行分析，利用遗传算法，为综合过程中的前三步提出更高质量的算法，在给定芯片上更快地执行生化反应。数字微流控生物芯片流体层面的综合过程的前三步在本文中合称为三维布局问题。数字微流控生物芯片综合过程的目的是让生化反应在芯片上合法地执行，同时增加吞吐量。反应的完成时间是先前相关算法的主要优化目标。由于生化反应执行过程中存在暂时不能参与反应的液滴，需要储存操作为这些液滴分配资源以储存在芯片上。先前算法得到的生化反应执行结果通常存在过多的储存操作，占据了多余的空间，激活了多余的电极，令模块布局和液滴路由更为复杂。针对这一问题，本研究增加了一个次要的优化目标以减少综合结果中的储存操作。基于遗传算法的调度方法，和使用遗传算法或其它元启法式算法的三维布局方法，都会在内部使用启发式调度方法作为产生合法解的方式。启发式调度算法的质量是影响结果中反应完成时间的重要因素。本研究分析了已有的启发式调度算法，发现它们只能生成合法解中的一部分。针对先前遗传调度算法因为搜索空间较小而表现不佳的问题，本研究提出一个新的启发式调度算法——队列调度。利用蛋白质比色反应和体外诊断反应进行实验，与基于已有启法式方法的遗传调度算法相比，基于队列调度的遗传算法可以获得最优的解。由于没有获得模块布局的结果，单独的调度算法通常无法充分利用芯片资源。将资源绑定、操作调度和模块布局三个问题一次性解决的三维模块布局方法可以解决这一问题。先前的三维布局方法所得到的结果通常受限于布局内容的表示方案。本研究提出使用三维矩阵来控制芯片电极资源，芯片上的每一电极的每一时刻都可以独立的表示和分配。这种方法不仅可以表示出所有的布局可能性，还可以直观灵活地应用于各种复杂的资源约束情形。本研究提出了基于遗传算法的三维模块布局算法，此方法内部使用了队列调度和三维矩阵控制的布局方法，保证结果的合法性的同时优化反应完成时间和储存时长。利用蛋白质比色反应和体外诊断反应进行实验，与前人提出的三维布局方法相比，本研究提出的算法可以用更短的时间完成相同的生化反应。除此之外，相比于只考虑反应完成时间这一目标的算法，增加储存时长优化目标的算法不仅能获得相同的反应完成时间，还能得到储存时长更短的结果。

Digital microfluidic biochip (DMFB) is an emerging technology which integrate conventional biological laboratory procedures on a small biochip with more accurate, less human labor, lower cost, and higher efficiency. With these advantages, DMFB has wide application prospects in the fields such as biochemical analysis, clinical diagnosis, and drug preparation. DMFBs will become larger in size with more applications in the coming years. We need software tools with higher quality to assist in the design automations. Fluid level synthesis tools of DMFBs can tell biochips how to control the droplets so that they can implement the desire bioassays. The synthesis process includes four steps: resource binding, operation scheduling, module placement, and droplet routing. Evolutionary algorithm (EA) is suitable for the complex combinatorial optimization problems in the synthesis process. The purpose of this study is to research the fluid level synthesis process of the digital microfluidic chip, and to design a better EA-based method for the first three steps of the synthesis flow. The combination of the first three steps of synthesis flow is called 3D module placement in this article.The purpose of the synthesis of the digital microfluidic biochips is to allow the biochemical assay to be legally executed on the chip with higher throughput. The assay completion time is a common optimization goal inside previous synthesis methods. But droplets need resources to be stored on the biochips when unable to perform the related operations during the execution of the assay. The results obtained by the previous algorithms often have too many storage operations, which lead to occupying extra space, activating extra electrodes, and making the module placement and droplet routing more complicated. In tackle with this problem, this study add a secondary goal to reduce the storage operations besides the assay completion time.Some previous scheduling methods and 3D placement methods are based on genetic algorithms (GA) or other metaheuristic algorithms. Those methods often contain a heuristic scheduling algorithm inside to generate legal solutions. The quality of the heuristic scheduling algorithm is an important factor that affects assay completion time. This study research on the previous heuristic scheduling algorithm and find that those algorithms cannot generate all legal solutions by themselves. So the previous GA-based scheduling methods perform poorly because of the small searching space limited by the inside heuristic algorithm. To tackle with this problem, a novel heuristic scheduling algorithm, order scheduling, is proposed. The performance of the proposed scheduling algorithm is verified by process on the colorimetric protein assay and in-vitro assay. The experimental results show that the genetic scheduler based on order scheduling is more effective than the genetic schedulers based on the previous heuristic scheduling methods.The individual scheduling methods cannot fully utilize the chip resources. The 3D module placement method which combine resource binding, operation scheduling and module placement together can solve this problem. The results obtained by the previous 3D module placement methods are often limited by the representation scheme of the layout. This study use a 3D matrix to control the electrode resources on the chip. Each electrode on the chip can be represented and allocated independently at every time step. This scheme can represent all the layout possibilities. It can also be intuitively and flexibly applied to various complex resource constraints.This article proposes a genetic algorithms-based 3D module placement algorithm, which use order schedule and 3D matrix to control chip resources. The proposed method can obtain legal results while optimizing the assay completion time and the total storage time. Experiments are performed using colorimetric protein assay and in-vitro assay. Compared with the previous 3D module placement method, the proposed algorithm can complete the same biochemical assay in a shorter time. In addition, compared with the algorithm which only consider the optimization goal of assay completion time, the algorithm which add the total storage time as a secondary goal can not only obtain the same assay completion time, but also obtain results with shorter storage time.

演化算法 数字微流控芯片 调度 模块布局

evolutionary algorithms digital microfluidic biochips scheduling module placement

中文

联合培养

南方科技大学

蒋陈. 基于演化算法的数字微流控芯片三维模块布局方法研究[D]. 深圳. 哈尔滨工业大学,2020.