蚁群算法的数字微流控生物芯片污染故障清除*

许川佩, 刘磊振, 万春霆

(1.桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004；2.广西自动检测技术与仪器重点实验室，广西 桂林 541004)

蚁群算法的数字微流控生物芯片污染故障清除*

许川佩1,2, 刘磊振1,2, 万春霆1,2

(1.桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004；2.广西自动检测技术与仪器重点实验室，广西 桂林 541004)

数字微流控生物芯片在生物化学分析中有良好的应用前景，为保证复杂生化实验分析结果的准确性，需对污染故障进行清除。提出了基于最大最小蚁群算法的污染故障清除策略，对清洗液滴清洗路径进行路径寻优。针对数字微流控生物芯片污染故障建立多旅行商问题(MTSP)模型，建立了基于流体和时间约束的禁忌判断策略、蚁群算法的选择策略，实现了优化清洗液滴路径规划、清除污染故障的目的。实验结果表明：该方案能有效地减少清洗时间，能够有效减少阵列单元使用数目。

数字微流控生物芯片； 污染故障； 最大最小蚁群算法

0 引 言

数字微流控制芯片又称为片上实验室(lab-on-a-chip，LoC)[1]，能在一个开放性平面上实现对纳米大小液滴的操作，已经成为生物化学自动化中的一项革命性技术。与传统的桌面实验相比，数字微流控制芯片极大地缩短了分析时间，减少了样品和试剂的消耗。数字微流控生物芯片(digital microfluidic biochips，DMFBs)已经应用在诸如酶的测定、DNA测序、基于细胞的分析及免疫测定法等生物化学的分析中[2]，但是，在对某些大分子物质(如蛋白质)进行检测时，这些分子在移动过程中会吸附在疏水表面产生污染，污染的产生会影响检测结果准确性，并可能导致严重的后果。因此，对污染故障进行清除对于保证生化实验检测分析结果的准确性至关重要。

1 数字微流控生物芯片相关研究

数字微流控生物芯片由2维微流体阵列、分液池和光学探测器三部分组成[3]，如图1(a)所示。2维微流体阵列由包含一组基本单元的两个平行玻璃板组成，底部包含独立可控的形成阵列的电极，顶部包括连续的接地电极，在两个平行玻璃板之间填充介质，液滴在电压控制的电极单元移动，如图1(b)、(c)所示。通常在数字微流控生物芯片上主要对液滴进行移动、分发、混合以及检测等操作。

在数字微流控生物芯片上进行的生化实验，由于生物分子在运动时会吸附在疏水面导致液滴残留在电极单元[4]，当另一种不同的液滴再次经过该单元时，会受到残留液滴的影响而被污染。人们首先利用表面张力低的硅油作为填充介质，来防止液滴的挥发以及减少表面污染。但是，仍存在一些大分子结构物质(如，脂类，蛋白质，脱氧核糖核酸，肽等)，因此，不能采用这种方式防止污染。

图1 数字微流控生物芯片

Pranab Roy等人在芯片设计时，通过避免液滴在芯片上的移动路径产生交叉，来避免交叉污染[5～8]。这种方法在简单的生化分析实验中有效，随着芯片设计复杂度的提高，越来越多的生物实验检测都在同一个数字微流控生物芯片中进行，要想找到互不相交的路径异常困难，而且也会导致占用大量单元，造成浪费。因此，必须要采用清洗液滴清洗污染单元[9]。

Zhao Y 等人[8,10,11]提出在芯片设计时，先用算法优化液滴路径降低污染单元的数目，然后采用清洗液清洗污染单元。但是，在两个连续的实验阶段之间进行污染单元清除操作会增加实验的执行时间。Huang Tsung-wei等人[3]对两个连续的实验阶段采用超前预测算法确定相邻阶段的污染单元，在当前阶段清洗下个阶段中由当前阶段的液滴残留引起的污染，同时把污染单元清除问题转化成旅行商问题(traveling salesman problem，TSP)，采用最小代价循环(minimum cost circulation，MCC)算法策略获得多清洗液滴对污染单元清除的路径规划,可有效减少阵列单元的使用数目以及清洗时间。

综上所述，复杂生化实验中通过在芯片设计时，对液滴进行路径优化并不能完全避免污染单元的产生，增加清洗液滴应用算法获得清洗污染单元路径也需要对芯片重新设计。当用液滴的路径单元数目表示液滴运动的时间(液滴在同一阵列单元多停留一个时间单元看作经过两个相同阵列单元)时，那么用清洗液滴清除污染的过程，本质上就是寻找一组最短路径单元。因此，如何在满足液滴流体约束、时间约束的条件下获得最短的污染单元清洗时间属于NP难问题[12]。

2 污染故障清除数学模型描述

在每一个实验开始时刻，实验液滴与清洗液滴同时从不同分液池单元出发，在实验液滴工作时清洗液滴同时对污染单元进行清除操作。清洗液完成清洗操作后最后到达目标废液池(或一直处在分液池)。清洗液滴清洗路径为该清洗液滴到达废液池所经过的阵列单元集合。由于一个实验中的清洗液滴路由路径会影响下一个实验中污染单元的产生，进而影响下一阶段中的清洗操作。所以,把所有实验中清洗液滴路由所花费时间的最小值作为优化目标函数。

假设阵列单元为m行n列，L表示阵列单元集合，共有K个实验，Ck表示第k个实验中清洗液液滴集合，CSk表示第k个实验中的污染单元集合。定义xkci=1，表示第k个实验中第c滴清洗液经过i阵列单元。

目标函数为

(1)

约束条件为

1)第k个实验中污染单元必须被全部遍历，如式(2)所示

CSk⊂Q

(2)

式中 Q为清洗液所经过阵列单元集合，如式(3)所示

Q={q|q=i且xkci=1且i∈L,c∈Ck}

(3)

2)清洗液滴c到达污染单元的时刻必须在先后经过该污染单元的两个液滴时刻之间，如式(4)所示

Tearly

(4)

式中 Twash为清洗液滴c到达污染单元的时刻，Tearly与Tlate为液滴先后经过同一个污染单元的两个前后时刻。

3)流体约束是为了避免在两个液滴传输的过程中出现不期望的混合。当Xi，Yi表示i液滴所在行与列。

静态流体约束

(5)

动态流体约束

(6)

静态约束表述为：两个不同的液滴在任意的t时刻，两液滴不能处于直接邻近或对角邻近的阵列单元位置，它们之间必须至少有一个空单元的间隔。动态约束表述为：对液滴di操作的激活单元不能与液滴dj相邻，否则在液滴di和液滴dj之间会产生意外的混合。

3 数字微流控生物芯片污染故障清除策略

针对数字微流控生物芯片，设计基于蚁群算法的污染故障清除路径优化策略时，把数字微流控生物芯片污染单元及废液池转换二维无向带权图G(V,E)。蚁群算法路径清洗优化流程如图2所示。

图2 蚁群算法清洗路径优化流程图

3.1 数字微流控芯片污染单元清除模型转换

在满足时间约束以及流体约束的条件下，在实验液滴移动的同时，清洗液滴对污染单元清除并最终到达废液池。针对清洗液滴清除污染故障的过程，可把数字微流控生物芯片污染单元及废液池转换成一个二维无向带权图G(V,E)，如图3所示。其中，V表示污染单元，E表示两个污染单元之间的路径，边上的权值表示两者之间的距离。将得到的二维无向图G作为动态MTSP模型，在不影响实验液滴运行的同时寻找一条最优清洗路径。

图3 数字微流控生物芯片污染故障清除模型

3.2 动态禁忌表建立

流体约束禁忌表：为了不影响实验液滴以及清洗液滴正常进行，清洗液滴选择下一单元时必须满足流体约束条件，将不能选择的相邻单元放入禁忌表中。由于清洗液滴在不断移动，每一滴清洗液的禁忌表也随其移动不断更新。例如，第m滴清洗液在t时刻的禁忌表，主要包括t时刻以及t+1时刻实验液滴和其它清洗液滴所在单元及其相邻单元。实验液滴移动时间远远小于实验操作(混合，检测等)所需要的时间，在实验液滴移动时，实验反应区域范围不发生变化，所以，流体约束禁忌表还包括当前实验中实验液滴反应区单元。

污染单元禁忌表：在t时刻每滴清洗液至多选择一个污染单元，当某一污染单元被清洗液滴选择或者该污染单元被清洗，则将该污染单元放入禁忌表中，其它清洗液滴在t时刻不再对禁忌表中污染单元进行选择。在时刻t+1时首先，将未被清洗的污染单元禁忌表中移除，然后，对未清洗的污染单元重新选择。

3.3 概率选择策略

数字微流控生物芯片污染故障清除过程中，污染单元的选择策略采用伪随机比例选择规则，既可以利用关于问题的先验知识，即关于节点之间的距离长度的启发信息以及信息素信息，又可以进行有倾向性的探索，提高蚂蚁探索新路径以增加全局搜索的能力。清洗液选择新的目标污染单元j时，按式(7)选择下一个目标单元j，J是根据式(8)选择的下一目标单元。

(7)

式中α和β分别决定了信息素和启发式信息的影响力，allowedm为可选污染单元集合,τij(t)为两个目标污染单元i，j之间路径上的信息素浓度,ηij(t)为启发函数,q为均匀分布在区间[0,1]的一个随机变量，参数q0决定算法对新路径的探索能力(0≤q0≤1)

(9)

式中 dsj为t时刻蚂蚁所在阵列单元s到下一目标污染单元j的曼哈顿距离。

3.4 信息素更新策略

最大最小蚁群算法把各路径上的信息素轨迹量的值域限制在[τmin,τmax]区间内，避免了早熟收敛，增加了全局最优解的搜索能力，同时对最优解路径进行全局更新，保证最优解的收敛速度。信息素更新方式如式(10)所示

τij(t+1)=(1-ρ)τij(t)+Δτij

(10)

(11)

式中Lbs为全局最优路径长度，ρ为信息素挥发因子，τij(t)为t次迭代i，j污染单元之间的信息素浓度，实验液滴最大的路由时间为20个时间单元[4]。

信息素全局更新会导致搜索的停滞，信息素局部更新能够减少蚂蚁所选择污染单元的信息素，提高选择其它污染单元的能力，所以,同时采用信息素局部更新策略

(12)

4 实验结果与分析

以Trinder P等人的人体生理体液的多元体外诊断实验[13]为例，实现污染故障在线清除策略验证。图4表示实验中样品与试剂变化过程，该体外检测分析实验共有3种人体生理体液(尿液、血浆、血清)样品，检测试剂分别为葡萄糖和乳酸，样品与检测试剂在电极作用下在数字微流控生物芯片上移动。

图4 体外检测实验样品与试剂变化关系图

数字微流控生物芯片阵列单元数为16×16。液滴在100 Hz的变换频率下，从一个阵列单元到相邻阵列单元的花费时间约为10 ms，这里清洗时间用阵列单元个数表示。每次迭代有30组蚂蚁，每组有8只蚂蚁分别从不同的清洗液分液池同时出发。经过多次实验蚁群算法初始化参数如下：

ρ=0.1,α=3,β=2,ξ=0.05,τ0=10,τmin=1,τmax=30,q0=0.9,NC=1 000。

实验结果如图5所示。蚁群算法的污染单元数目为25，与未采用算法实验相比污染单元数目减少了52.8 %；蚁群算法的液滴路由时间为187个时间单元，与未采用算法实验相比路由时间减少了16.8 %；蚁群算法使用单元数为315，与未采用算法实验相比减少了18.8 %。从实验结果可知：使用蚁群算法进行污染故障清除，能够在路由时间以及使用单元数上得到优化。

图5 数据结果

算法收敛过程如图6所示，算法于第106次迭代达到清洗时间最小值。蚂蚁在探索新路径时由于时间约束，在探索新路径时不能在规定时间内完成污染单元清洗操作，会导致探索新路径失败。生化分析共有K个实验，每个阶段污染单元数目为n，蚂蚁数为m，算法的空间复杂度与时间复杂度分别为

S(n)=O(n2)和T(n)=O(n2)。

(13)

图6 算法测试收敛图

5 结 论

本文针对数字微流控生物芯片污染故障，提出了基于最大最小蚁群算法污染故障清除方案。在不影响实验液滴运行的同时进行清洗操作，利用蚁群算法寻找合理的清洗污染单元路径，保障污染单元能够顺利清除，获得最短清洗时间。以人体生理体液的多元体外诊断实验为算法验证平台，结果表明:该算法能够减少清洗时间以及阵列单元使用数目，保障了实验分析结果的准确性。

[1] Xu T, Chakrabarty K. Fault modeling and functional test methods for digital microfluidic biochips[J].IEEE Transactions on Biomedical Circuits & Systems,2009,3(4):241-253.

[2] 卢卫红,付 力,郑 琦,等.生物芯片技术的应用与展望[J].传感器与微系统,2006,25(2):1-4.

[3] Huang Tsung-Wei,Lin Chun-Hsien，Ho Tsung-Yi.A contamination aware droplet routing algorithm for the synthesis of digital microfluidic biochips[J].IEEE Transactions Computer-Aided Design of Integrated Circuit and System,2010,29(11):1682-1695.

[4] Maftei E,Pop P,Madsen J.Routing-based synthesis of digital microfluidic biochips[J].Design Automation for Embedded Systems,2012,16(1):19-44.

[5] Pranab Roy,Pampa Howladar,Rupam Bhattacharjee,et al.A new cross contamination aware routing method with intelligent path exploration in digital microfluidic biochips[C]∥8th International Conference on Design & Technology of Integrated System in Nanoscale Era,2013:50-55.

[6] Chakraborty S,Das C,Chakraborty S,et al.A novel two phase heuristic routing technique in digital microfluidic biochip[C]∥2015 19th International Symposium on VLSI Design and Test(VDAT),IEEE Computer Society,2015:1-6.

[7] Singha K,Samantam T,Rahaman H,et al.Method of droplet routing in digital microfluidic biochip[C]∥2010 IEEE/ASME International Conference on Mechatronics and Embedded Systems and Applications(MESA),2010:251-256.

[8] Yang Zhao,Chakrabarty K.Cross-contamination avoidance for droplet routing in digital microfluidic biochips[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2009,31(6):1290-1295.

[9] Indrajit Pan,Soumyajit Chatterjee,Tuhina Samanta.Droplet routing and wash droplet scheduling algorithm to remove cross-contamination in digital microfluidic biochip[C]∥12th International Conference on Intelligent Systems Design and Applications,2012:155-160.

[10] Mitra D,Ghoshal S,Rahaman H,et al.Offline washing schemes for residue removal in digital microfluidic biochips[J].ACM Transactions on Design Automation of Electronic Systems,2015,21(1):1-33.

[11] Pan I,Samanta T.A droplet clustering and residue removal technique for cross-contamination avoidance in digital microfluidic biochip[J].Mirlabs Org,2014,6:171-183.

[12] Huang T W,Lin C H,Ho T Y.A contamination aware droplet routing algorithm for the synthesis of digital microfluidic biochip-s[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2010,29(11):1682-1695.

[13] Trinder P.Determination of glucose in blood using glucose oxidase with an alternative oxygen acceptor[J].Annals of Clinical Biochemistry,1969,6(2):24-27.

许川佩 (1968-)，女，博士，教授，研究生导师，从事集成电路测试、自动测试总线与系统方向研究工作。

Contamination fault removal in digital microfluidic biochips based on ant colony algorithm*

XU Chuan-pei1,2, LIU Lei-zhen1,2, WAN Chun-ting1,2

(1.School of Electronic Engineering and Automation,Guilin University of Electronic Technology,Guilin 541004,China;2.Guangxi Key Laboratory of Automatic Detecting Technology and Instruments,Guilin 541004,China)

Digital microfluidic biochips in the process of biochemistry analysis has good promising applications,but cross-contamination will occur in detection process.In order to ensure the precision of complex biochemical experimental analysis results,the contamination should be cleaned.Contamination removal strategy based on max-min ant colony algorithm is proposed to realize optimizing wash droplets route.Establishing multiple travelling salesman problem(MTSP)model for digital microfluidic biochips contamination,establishing tabu judgement strategy based on fluid and time constraints and selection strategy of ant colony algorithm to achieve the purpose of optimizing the path planning of wash droplet and cleaning up contamination.Experimental results show that the scheme can reduce the time of clearning contamination and number of used array cells effectively.

digital microfluidic biochips; contamination fault; max-min ant colony algorithm

10.13873/J.1000—9787(2017)04—0019—04

2016—03—31

广西自动检测技术与仪器重点实验室2016年度主任基金资助项目(YQ16104)；国家自然科学基金资助项目(61540014,61671164)

TP 306

A

1000—9787(2017)04—0019—04