引脚约束的数字微流控生物芯片在线并行测试

许川佩 陈春艳 汪杰君

1 引言

微流控芯片实验室又称微流控芯片、芯片实验室（Lab-on-a-Chip, LoC）或生物微机电系统（bio-MEMS），而基于离散流体的微流控生物芯片又称为数字微流控生物芯片（Digital MicroFluidic Biochips,DMFBs）[1]，它代替了笨重和昂贵的实验室设备，在高通量测序、并行的免疫分析、蛋白质结晶、血液的临床化学诊断和环境的毒性检测等生化领域得到了广泛的应用[2]，这些领域对可靠性的要求非常严格，因此在数字微流控生物芯片工作时，对其进行有效的测试是确保芯片可靠工作不可缺少的重要手段。

数字微流控生物芯片依照引脚的控制方式不同分为直接寻址和引脚受限两种。直接寻址生物芯片的每个电极对应一个控制引脚，任意一个引脚都能够单独激活，因此这种方法允许最大自由操纵液滴，但是引入了过多的控制引脚，显著增加产品的制造成本。引脚受限的数字微流控生物芯片的多个引脚共用一个电极[35]-，因此可有效降低制造成本。由于引脚受限的芯片电极间存在共用引脚的情况，相比直接寻址的芯片，操纵液滴的自由度受到限制，测试难度更大。本文主要研究引脚受限的数字微流控生物芯片在线测试方法，以保证芯片工作的稳定可靠。

2 DMFBs测试研究进展

随着技术的不断发展，数字微流控生物芯片越来越复杂，各种生产故障和物理故障都可能出现在芯片中。针对生产故障，文献[6]指出可通过带电的控制和跟踪液滴的移动来确定故障的位置。但是由于在实验中也会产生故障，因此，文献[7]针对实验中出现的突变性故障提出了一个数字微流控阵列的突变性故障检测优化方法，该方法首先把数字微流控生物阵列转化为图论模型，再把图论模型中的问题用汉密尔顿路径公式化，但是该方法却无法检测到电极短路的故障。因此为测试该类故障，文献[8]提出了基于欧拉回路的测试方法，该方法可有效地检测到电极短路的故障。Xu等人[9]提出了一种并行扫描式的测试方法，即多液滴并行的遍历微流控阵列来实现故障检测，虽能有效地减少测试时间，但是在线测试时，该方法由于测试路线一定，测试过程中存在的干扰会使测试时间大量增加，降低测试效率。张玲等人[10,11]针对DMFBs在线测试进行了研究，借鉴文献[12]中的并行测试方法，将芯片阵列分为相同大小的子阵列，在与实验液滴互不干扰的情况下，对电极阵列进行测试，提高了测试效率。

上述提到的测试方案都是针对直接寻址芯片阵列单元进行遍历，然而对有引脚约束的芯片却没有开展研究。因此，本文提出一种针对引脚约束芯片的在线并行测试方案。鉴于最大最小蚁群算法（MMAS）是对传统蚁群算法的一种改进，是解决TSP, MTSP等问题最好的蚁群优化算法之一[13]，本文将芯片阵列转换为 TSP或 MTSP模型[14]，将MMAS用于引脚约束数字微流控生物芯片在线并行测试，以获得最短路径，提高测试效率。

3 DMFBs测试

3.1 DMFBs工作原理

数字微流控生物芯片利用介电润湿的原理在 2维的电极阵列中操纵和移动纳升级的离散液滴[15]。如图1所示，数字微流控生物芯片的基本单元包括两个平板和夹在平板中间的填充（硅油），液滴在填充介质内运行。底板包含一个单独可控的电极阵列，顶板覆盖了一层连续的地线。通过改变沿着电极的一个线性阵列的电势，液滴可以沿着电极的一条线移动。可以通过调整控制电压（0～90 V）来控制液滴的速度，液滴最高能够以20 cm/s的速度移动。基于这一原理，液滴能够很自由地移动到2维阵列的任何位置而不需要微型泵和微型阀。

图1 芯片的工作原理

3.2 DMFBs测试模型

DMFBs故障主要分为永久性故障和参数故障[6]，其中永久性故障会造成DMFBs系统液滴无法移动，因此可根据测试液滴能否移动判断是否存在故障，即利用测试液滴从液滴源出发，在电极阵列单元上移动，如果液滴停留在某单元上不能移动，则该单元为故障单元[6]。因此，DMFBs的永久性故障可以通过液滴遍历电极阵列单元来检测，这种遍历问题可转换为网络问题，即将阵列单元结构抽象为图论中的图模型。将数字微流控生物芯片的电极阵列单元看成一个无向图（,）G V E，其中V表示微流控阵列单元，E表示两个直接邻近单元之间所构成的边，以此规则构造的5×5的微流控电极阵列转换图如图2所示。

图2 5×5的芯片电极转换图

在数字微流控生物芯片测试中，测试目标是在带权有向图G中（这里的权值指的是两条边的距离），寻找从液滴源出发，测试完所有的边E后到达废液池的最短测试路径，即最短测试时间。用m个液滴对数字微流控生物芯片的电极阵列进行测试，电极阵列的所有单元都应当至少被访问1次，表示为

其中， xi表示阵列单元，n表示芯片总的单元数。

由于DMFBs相邻流体之间存在干扰，共用电极引脚之间存在约束，m个液滴同时对DMFBs进行测试的过程中存在起点和终点、静态和动态流体约束以及共用电极引脚约束。

（1）起点和终点约束： 在每次测试中，液滴从液滴源s出发，且s只能被访问1次。液滴完成测试后到达废液池d，且d只能被访问1次，可表示为

（2）静态和动态流体约束： 当两个液滴相邻时，液滴之间会相互融合，产生干扰，静态约束表示两液滴不能处于直接邻近或对角邻近的阵列单元位置。动态约束表示一个液滴下一步所走的单元不能邻近另一个液滴，否则会导致另一个液滴附近产生多于一个的激活单元，影响液滴的下一步操作。

定义 Al

t1, Blt1分别为液滴l1在时间t时所在的单元的行与列， Alt2, Blt

2分别为液滴l2在时间t时所在单元的行与列。

则静态流体约束表示为

动态流体约束表示为

（3）共用电极引脚约束： 图3是一个典型的存在引脚约束的聚合酶链反应的芯片[3]。当实验液滴和测试液滴在图3中所示位置时，实验液滴所在的电极由引脚11控制，当该电极被激活时，测试液滴邻近由引脚11控制的电极也被激活，此时测试液滴就不能向引脚11控制的电极移动。

因此，为避免共用引脚影响液滴的移动，定义Nkt为测试液滴k在t时刻所在单元的电极引脚编号， Net为实验液滴e在t时刻所在单元的电极引脚编号，则

根据式（5）来避免共用电极引脚对测试液滴的影响。

图3 共用电极干扰示例

4 基于改进MMAS的引脚约束DMFB在线并行测试

为提高实验效率，数字微流控生物芯片一般包含多对起始节点（液滴源）和目标节点（废液池），因此，本文采用MMAS安排多个蚂蚁同时从起始节点出发，对整个芯片进行并行搜索，以此减少测试时间。同时，为避免算法在求解大规模复杂问题时出现早熟、停滞现象，采用改进MMAS自适应地调整信息素的残留系数提高算法的全局搜索能力。在此基础上为保证解的多样性，对算法的选择策略进行改进，增加伪随机比例原则。对芯片的引脚约束和液滴之间的约束，采用禁忌判断策略实现。

4.1 并行测试策略

当芯片的测试问题转换成MTSP模型后，采用MMAS对转换的模型进行测试，即有a组蚂蚁（每组蚂蚁有m只）同时从a个不同的起始点出发，访问所有的边后到达目标节点。当a组蚂蚁遍历完阵列单元所有边后，遍历完成，蚂蚁停止搜索。迭代过程中每组蚂蚁都可以生成一组最优解，并行测试的最优时间是a组遍历时间的最大值，目标函数如式（6）和式（7）所示：

式（6）表示每组m只蚂蚁在迭代完成后的最优时间，指的是所有蚂蚁对芯片遍历完成后用时之和的最小值，其中 tk表示第k只蚂蚁的遍历时间，Ti表示第i组蚂蚁的最优测试时间。式（7）表示a组蚂蚁并行搜索的最优时间。

4.2 选择策略的改进

在基本蚁群算法中，t时刻位于单元i的蚂蚁根据式（8）选择下一个单元j。式中α和β是决定信息素和可见性的两个重要参数。 a ln表示蚂蚁下一步所选的单元， ηij（t）为启发函数，在本文定义 ηij（t） = 1 /dij，其中 dij表示节点i和节点j之间的距离，τij（t）表示在t时刻单元i到单元j上的信息素强度。

为避免蚂蚁在开始搜索时以较大的概率集中在当前最优路径上，本文采用伪随机比例原则选择路径。因此，可以让蚂蚁根据式（9）从单元i选择下一个单元j。

式中 q0∈ （ 0,1）, q是均匀分布在（0,1）的随机数，J是根据式（8）所选择的节点。这样，在开始就增加蚂蚁的选择单元，确保路径的多样性。

4.3 禁忌判断策略

在线测试的时候，会存在 3.2节描述的液滴静态和动态的干扰，以及引脚约束的干扰。为了避免干扰出现，首先建立液滴测试禁忌表，把实验液滴及其下一步所走单元、实验液滴周围的对角邻近和非对角邻近单元、当前时间实验液滴所在电极引脚编号存放到禁忌表中，实验液滴每走一步更改一次禁忌表。测试液滴在测试的过程中每走一步就要判断其是否在禁忌表中，如果不在禁忌表中，液滴可以继续进行测试；如果在禁忌表中，当测试液滴等待时间加上测试液滴运行到这条边上的权值小于其它边的权值时，测试液滴选择等待，反之，选择向其它权值小的边运行，等待时间为实验液滴从一个电极运行到另一个电极的时间。

4.4 信息素更新策略的改进

MMAS只允许其中最优路径更新信息素。更新规则为

其中， ρ 表示信息素残留系数； Δ τbij= 1 /f（ sb）,f（ sb）表示为第i次迭代的最优路径sib的长度，或全局最优路径 sgb的长度。

但当测试规模较大时，信息素残留系数ρ的存在，使得那些没有被搜索到的路径上的信息量逐渐减少，降低算法搜索的全局性。本文通过自适应地调整ρ的大小来解决这一问题，改进方法如式（11）所示。

4.5 信息素限制和初始化

在一次迭代完成后将各条路径上的信息素限制在[τmin,τmax]之间，超出范围的值将按照式（12）进行判断来避免算法过早地收敛于全局最优解。

信息素初始化中，设定 τ （0）=τmax来增加蚂蚁在初始阶段探索新解的能力。其中τmin和τmax定义为

4.6 算法流程

根据上文对算法的描述，基于改进MMAS的引脚约束 DMFB在线并行测试的算法流程如图 4所示。

5 实验结果与分析

图4 MMAS在线并行测试

本文以文献[3]的引脚约束生物芯片为例验证本文方法的有效性。如图5所示，多功能生物鉴定和聚合酶链反应（PCR）分别映射到一个15×15的数字微流控生物芯片上。图 5（a）中，多功能生物鉴定包含一个葡萄糖阵列和一个乳酸盐阵列，两组样本（S1,S2）和试剂（R1, R2）被分发到阵列中。其中 S1和 R1为葡萄糖检测实验液滴，S1中含有葡萄糖，R1中含有氧化酶等反应试剂；S2和R2为乳酸盐检测实验液滴，S2中含有乳酸，R2含有氧化酶等反应试剂。有4 对液滴即（S1, R1）, （S2, R1）, （S1, R2）, （S2, R2）分别进行混合操作（M1-M4），混合后的液滴路由到检测位置（D1-D4）进行分析检测。多功能生物鉴定的具体操作流程如图 6（a）所示。图 5（b）所示的 PCR 鉴定用于检测特定 DNA链酶的快速扩增，主要是通过温度变化控制 DNA的变性和复性，并设计引物做启动子，加入 DNA聚合酶实现特定基因的体外复制。PCR鉴定通过DNA模板解链，引物与模板结合，DNA聚合酶催化新生DNA合成3个步骤完成一个循环，多次循环后，目的 DNA可得以迅速扩增，具体检测流程如图6（b）所示。

图5 15×15的电极阵列

图7 是典型的多功能生物鉴定和PCR鉴定的引脚约束的芯片的设计[3]，多功能生物鉴定生物芯片由最初所需的59个电极减少到了25个电极，PCR鉴定生物芯片由最初所需的62个电极减少到14个电极，其中电极上的标号表示电极所用引脚标号，相同标号的电极表示它们共用一个控制引脚。对该生物芯片利用改进MMAS寻找多条并行测试路径，以实现液滴并行测试。经过多次实验，将实验参数设置为：两组蚂蚁（a = 2 ）同时进行测试，每组蚂蚁有25只（m = 2 5）, q0=0.9, α=1, β=2, ρ= 0 .95,ρmin= 0 .45, q= 0 .1, τmax= 4 20, τmin= 0 .42,NC= 2 000，在单液滴测试时设置蚂蚁数 m = 5 0。

（1）实验结果分析： 实验结果如图8所示，其中纵坐标表示芯片测试所花费的单位时间，这里的单位时间指的是液滴在16 Hz的变换频率、50 V驱动电压下从一个阵列单元移动到相邻的阵列单元所花费的时间，约62.5 ms[16]。对于有引脚约束的数字微流控生物芯片的多功能生物鉴定和PCR鉴定，单液滴离线测试时，由于不存在实验液滴，因此引脚约束对其无影响，两者测试都花费456个单位时间；单液滴在线测试时由于存在实验液滴和引脚约束的影响，多功能生物鉴定花费490个单位时间，PCR鉴定花费494个单位时间；多液滴并行测试多功能生物鉴定花费322个单位时间，相对于单液滴离线和在线测试分别减少 29%和 38%, PCR鉴定花费320个单位时间，相对于单液滴离线和在线测试分别减少30%和35%。由两种生物鉴定的测试结果可知，基于MMAS的多液滴并行在线测试可以有效地减少测试时间，提高测试效率。

图6 多功能生物鉴定与PCR鉴定具体操作流程

图7 DMFB引脚分配

图8 测试结果

（2）算法收敛性分析： 由于引脚受限多功能生物鉴定和PCR鉴定测芯片结构相似，本文根据多功能生物鉴定实验下的单液滴离线测试、单液滴在线测试、多液滴并行测试的迭代结果进行算法的收敛性分析。

如图9所示，横坐标表示算法迭代次数，纵坐标表示测试单位时间。最大最小蚁群算法初始阶段由于缺乏信息素的指引，其收敛速度较慢，但随着探索新路径的蚂蚁逐渐增加，各条边上的信息素值的差异逐渐变大，根据最大最小蚁群算法信息素值的限制，算法最终达到收敛状态。单液滴在线测试过程中，由于在线测试约束条件的存在，算法在运行到1310代时收敛，收敛速度比在1195代收敛的单液滴离线测试慢。多液滴并行测试中，虽然并行在线测试时也存在约束条件的限制，但是由于多组液滴同时对芯片进行测试，算法在运行646代时收敛，收敛速度要比单液滴在线测试和单液滴离线测试都快，验证了本文方法的有效性。

图9 改进MMAS收敛图

（3）算法效率分析 基于改进 MMAS的单组蚂蚁对芯片进行离线和在线测试的空间复杂度S（ n）=O（ n2），多组蚂蚁对芯片同时进行测试时，由于芯片总的单元数不变，多组蚂蚁遍历的单元总数与单组蚂蚁遍历的总数相同，所占的存储容量相同。因此，本文采用的多液滴并行测试方法的空间复杂度不变，即 S （ n ） = O （ n2） 。时间复杂度分析：基于改进MMAS的单组蚂蚁对芯片进行离线和在线测试的时间复杂度 T （ n ） = O （ n2） ，本文采用多组蚂蚁同时对芯片进行测试，算法的时间复杂度变为T（ n）=O（ n2）/a（这里的a指的是蚂蚁的分组数），缩短了算法运行时间。综上所述，在空间复杂度相同的情况下，本文方法降低了算法的时间复杂度，提高算法的运行速度。

6 结束语

引脚约束的数字微流控芯片在线并行测试，在禁忌判断约束下，通过改进MMAS选择策略，自适应地调整信息素的残留系数来寻找多液滴并行测试路径，加快算法的收敛速度。实验结果表明多液滴并行测试的时间相对单液滴在线测试的时间明显减少，甚至比单液滴离线测试时间还少。验证了本文方法适用于芯片的离线和在线测试，可有效地解决数字微流控生物芯片的在线测试问题。

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

[2] 杨敬松, 姚振静, 宋燕星, 等. 数字微流控生物芯片布局的拟人遗传组合算法[J]. 计算机工程与应用, 2012, 48（31）: 16-20.Yang Jing-song, Yao Zhen-jing, Song Yan-xing, et al..Personification and genetic combinational algorithm for placement problem of digital microfluidics-based biochips[J].Computer Engineering and Applications, 2012, 48（31）: 16-20.[3] Xu T and Chakrabarty K. Broadcast electrode-addressing and scheduling methods for pin-constrained digital microfluidic biochip[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30（7）:986-999.

[4] Luo Y and Chakrabarty K. Design of pin-constrained general-purpose digital microfluidic biochips[J]. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 2013, 32（9）: 1307-1320.

[5] Grissom D T, McDaniel J, and Brisk P. A low-cost fieldprogrammable pin constrained digital microfluidic biochip[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33（11）: 1657-1670.

[6] Su F, Ozev S, and Chakrabarty K. Testing of droplet-based microelectrofluidics systems[C]. Proceedings IEEE International Test Conference, Charlotte, 2003: 1192-1200.[7] Su F, Ozev S, and Chakrabarty K. Test planning and test resource optimization for droplet-based microfluidic systems[J]. Journal of Electronic Testing: Theory and Applications,2006, 22（2）: 199-210.

[8] Su F, Hwang W, Mukherjee A, et al.. Testing and diagnosis of realistic defects in digital microfluidic biochips[J]. Journal of Electronic Testing: Theory and Applications, 2007, 23（2/3）:219-233.

[9] Xu T and Chakrabarty K. Paralled scan-like test and multiple-defect diagnosis for digital microfluidic biochips[J].IEEE Transactions on Biomedical Circuits and Systtems,2007, 1（2）: 148-158.

[10] 张玲, 邝继顺, 林静, 等. 数字微流控生物芯片的并行在线测试[J]. 上海交通大学学报, 2013, 47（1）: 98-102.Zhang Ling, Kuang Ji-shun, Lin Jing, et al.. Parallel on-line testing for digital microfluidic biochip[J]. Jouranl of Shanghai Jiao Tong University, 2013, 47（1）: 98-102.

[11] 张玲, 邝继顺, 梅军进, 等. 数字微流控生物芯片测试诊断过程分析和优化[J]. 计算机工程与科学, 2014, 36（3）: 411-415.Zhang Ling, Kuang Ji-shun, Mei Jun-jin, et al.. Analysis and optimization of test and diagnosis process for digital microfluidic biochip[J]. Computer Engineering and Science,2014, 36（3）: 411-415.

[12] Su F, Ozev S, and Chakrabarty K. Concurrent testing of droplet-based microfluidic systems for multiplexed biomedical assays[C]. Proceedings IEEE International Test Conference, Charlotte, 2004: 883-892.

[13] 杨延庆, 李鹏飞, 何博. 求解 TSP问题的改进最大最小蚁群算法[J]. 西安工程大学学报, 2010, 24（6）: 818-821.Yang Yan-qing, Li Peng-fei, and He Bo. The solution of TSP based on the improved max-min ant colony algorithm[J].Journal of Xi’an Polytechnic University, 2010, 24（6）:818-821.

[14] 许川佩, 蔡震, 胡聪. 基于蚁群算法的数字微流控生物芯片在线测试路径优化[J]. 仪器仪表学报, 2014, 35（6）: 1417-1424.Xu Chuan-pei, Cai Zhen, and Hu Cong. On-line test path optimization for digital microfluidic biochips based on ant colony algorithm[J]. Chinese Journal of Scientific Instrument,2014, 35（6）: 1417-1424.

[15] Royal M W, Jokerst N M, and Fair R B. Droplet-based sensing: Optical microresonator sensors embedded in digital electrowetting microfluidics systems[J]. IEEE Sensors Journal, 2013, 13（12）: 4733-4742.

[16] Su F, Hwang W, Mukherjee A, et al.. Defect-oriented testing and diagnosis of digital microfluidics-based biochips[C].Proceedings IEEE International Test Conference, Austin,2005: 1-10.