蟻群算法的數(shù)字微流控生物芯片污染故障清除*

許川佩, 劉磊振, 萬春霆

(1.桂林電子科技大學(xué) 電子工程與自動化學(xué)院，廣西 桂林 541004；2.廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

蟻群算法的數(shù)字微流控生物芯片污染故障清除*

許川佩1,2, 劉磊振1,2, 萬春霆1,2

(1.桂林電子科技大學(xué) 電子工程與自動化學(xué)院，廣西 桂林 541004；2.廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

數(shù)字微流控生物芯片在生物化學(xué)分析中有良好的應(yīng)用前景，為保證復(fù)雜生化實(shí)驗(yàn)分析結(jié)果的準(zhǔn)確性，需對污染故障進(jìn)行清除。提出了基于最大最小蟻群算法的污染故障清除策略，對清洗液滴清洗路徑進(jìn)行路徑尋優(yōu)。針對數(shù)字微流控生物芯片污染故障建立多旅行商問題(MTSP)模型，建立了基于流體和時(shí)間約束的禁忌判斷策略、蟻群算法的選擇策略，實(shí)現(xiàn)了優(yōu)化清洗液滴路徑規(guī)劃、清除污染故障的目的。實(shí)驗(yàn)結(jié)果表明：該方案能有效地減少清洗時(shí)間，能夠有效減少陣列單元使用數(shù)目。

數(shù)字微流控生物芯片； 污染故障； 最大最小蟻群算法

0 引 言

數(shù)字微流控制芯片又稱為片上實(shí)驗(yàn)室(lab-on-a-chip，LoC)[1]，能在一個(gè)開放性平面上實(shí)現(xiàn)對納米大小液滴的操作，已經(jīng)成為生物化學(xué)自動化中的一項(xiàng)革命性技術(shù)。與傳統(tǒng)的桌面實(shí)驗(yàn)相比，數(shù)字微流控制芯片極大地縮短了分析時(shí)間，減少了樣品和試劑的消耗。數(shù)字微流控生物芯片(digital microfluidic biochips，DMFBs)已經(jīng)應(yīng)用在諸如酶的測定、DNA測序、基于細(xì)胞的分析及免疫測定法等生物化學(xué)的分析中[2]，但是，在對某些大分子物質(zhì)(如蛋白質(zhì))進(jìn)行檢測時(shí)，這些分子在移動過程中會吸附在疏水表面產(chǎn)生污染，污染的產(chǎn)生會影響檢測結(jié)果準(zhǔn)確性，并可能導(dǎo)致嚴(yán)重的后果。因此，對污染故障進(jìn)行清除對于保證生化實(shí)驗(yàn)檢測分析結(jié)果的準(zhǔn)確性至關(guān)重要。

1 數(shù)字微流控生物芯片相關(guān)研究

數(shù)字微流控生物芯片由2維微流體陣列、分液池和光學(xué)探測器三部分組成[3]，如圖1(a)所示。2維微流體陣列由包含一組基本單元的兩個(gè)平行玻璃板組成，底部包含獨(dú)立可控的形成陣列的電極，頂部包括連續(xù)的接地電極，在兩個(gè)平行玻璃板之間填充介質(zhì)，液滴在電壓控制的電極單元移動，如圖1(b)、(c)所示。通常在數(shù)字微流控生物芯片上主要對液滴進(jìn)行移動、分發(fā)、混合以及檢測等操作。

在數(shù)字微流控生物芯片上進(jìn)行的生化實(shí)驗(yàn)，由于生物分子在運(yùn)動時(shí)會吸附在疏水面導(dǎo)致液滴殘留在電極單元[4]，當(dāng)另一種不同的液滴再次經(jīng)過該單元時(shí)，會受到殘留液滴的影響而被污染。人們首先利用表面張力低的硅油作為填充介質(zhì)，來防止液滴的揮發(fā)以及減少表面污染。但是，仍存在一些大分子結(jié)構(gòu)物質(zhì)(如，脂類，蛋白質(zhì)，脫氧核糖核酸，肽等)，因此，不能采用這種方式防止污染。

圖1 數(shù)字微流控生物芯片

Pranab Roy等人在芯片設(shè)計(jì)時(shí)，通過避免液滴在芯片上的移動路徑產(chǎn)生交叉，來避免交叉污染[5～8]。這種方法在簡單的生化分析實(shí)驗(yàn)中有效，隨著芯片設(shè)計(jì)復(fù)雜度的提高，越來越多的生物實(shí)驗(yàn)檢測都在同一個(gè)數(shù)字微流控生物芯片中進(jìn)行，要想找到互不相交的路徑異常困難，而且也會導(dǎo)致占用大量單元，造成浪費(fèi)。因此，必須要采用清洗液滴清洗污染單元[9]。

Zhao Y 等人[8,10,11]提出在芯片設(shè)計(jì)時(shí)，先用算法優(yōu)化液滴路徑降低污染單元的數(shù)目，然后采用清洗液清洗污染單元。但是，在兩個(gè)連續(xù)的實(shí)驗(yàn)階段之間進(jìn)行污染單元清除操作會增加實(shí)驗(yàn)的執(zhí)行時(shí)間。Huang Tsung-wei等人[3]對兩個(gè)連續(xù)的實(shí)驗(yàn)階段采用超前預(yù)測算法確定相鄰階段的污染單元，在當(dāng)前階段清洗下個(gè)階段中由當(dāng)前階段的液滴殘留引起的污染，同時(shí)把污染單元清除問題轉(zhuǎn)化成旅行商問題(traveling salesman problem，TSP)，采用最小代價(jià)循環(huán)(minimum cost circulation，MCC)算法策略獲得多清洗液滴對污染單元清除的路徑規(guī)劃,可有效減少陣列單元的使用數(shù)目以及清洗時(shí)間。

綜上所述，復(fù)雜生化實(shí)驗(yàn)中通過在芯片設(shè)計(jì)時(shí)，對液滴進(jìn)行路徑優(yōu)化并不能完全避免污染單元的產(chǎn)生，增加清洗液滴應(yīng)用算法獲得清洗污染單元路徑也需要對芯片重新設(shè)計(jì)。當(dāng)用液滴的路徑單元數(shù)目表示液滴運(yùn)動的時(shí)間(液滴在同一陣列單元多停留一個(gè)時(shí)間單元看作經(jīng)過兩個(gè)相同陣列單元)時(shí)，那么用清洗液滴清除污染的過程，本質(zhì)上就是尋找一組最短路徑單元。因此，如何在滿足液滴流體約束、時(shí)間約束的條件下獲得最短的污染單元清洗時(shí)間屬于NP難問題[12]。

2 污染故障清除數(shù)學(xué)模型描述

在每一個(gè)實(shí)驗(yàn)開始時(shí)刻，實(shí)驗(yàn)液滴與清洗液滴同時(shí)從不同分液池單元出發(fā)，在實(shí)驗(yàn)液滴工作時(shí)清洗液滴同時(shí)對污染單元進(jìn)行清除操作。清洗液完成清洗操作后最后到達(dá)目標(biāo)廢液池(或一直處在分液池)。清洗液滴清洗路徑為該清洗液滴到達(dá)廢液池所經(jīng)過的陣列單元集合。由于一個(gè)實(shí)驗(yàn)中的清洗液滴路由路徑會影響下一個(gè)實(shí)驗(yàn)中污染單元的產(chǎn)生，進(jìn)而影響下一階段中的清洗操作。所以,把所有實(shí)驗(yàn)中清洗液滴路由所花費(fèi)時(shí)間的最小值作為優(yōu)化目標(biāo)函數(shù)。

假設(shè)陣列單元為m行n列，L表示陣列單元集合，共有K個(gè)實(shí)驗(yàn)，Ck表示第k個(gè)實(shí)驗(yàn)中清洗液液滴集合，CSk表示第k個(gè)實(shí)驗(yàn)中的污染單元集合。定義xkci=1，表示第k個(gè)實(shí)驗(yàn)中第c滴清洗液經(jīng)過i陣列單元。

目標(biāo)函數(shù)為

(1)

約束條件為

1)第k個(gè)實(shí)驗(yàn)中污染單元必須被全部遍歷，如式(2)所示

CSk?Q

(2)

式中 Q為清洗液所經(jīng)過陣列單元集合，如式(3)所示

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

(3)

2)清洗液滴c到達(dá)污染單元的時(shí)刻必須在先后經(jīng)過該污染單元的兩個(gè)液滴時(shí)刻之間，如式(4)所示

Tearly

(4)

式中 Twash為清洗液滴c到達(dá)污染單元的時(shí)刻，Tearly與Tlate為液滴先后經(jīng)過同一個(gè)污染單元的兩個(gè)前后時(shí)刻。

3)流體約束是為了避免在兩個(gè)液滴傳輸?shù)倪^程中出現(xiàn)不期望的混合。當(dāng)Xi，Yi表示i液滴所在行與列。

靜態(tài)流體約束

(5)

動態(tài)流體約束

(6)

靜態(tài)約束表述為：兩個(gè)不同的液滴在任意的t時(shí)刻，兩液滴不能處于直接鄰近或?qū)青徑年嚵袉卧恢?，它們之間必須至少有一個(gè)空單元的間隔。動態(tài)約束表述為：對液滴di操作的激活單元不能與液滴dj相鄰，否則在液滴di和液滴dj之間會產(chǎn)生意外的混合。

3 數(shù)字微流控生物芯片污染故障清除策略

針對數(shù)字微流控生物芯片，設(shè)計(jì)基于蟻群算法的污染故障清除路徑優(yōu)化策略時(shí)，把數(shù)字微流控生物芯片污染單元及廢液池轉(zhuǎn)換二維無向帶權(quán)圖G(V,E)。蟻群算法路徑清洗優(yōu)化流程如圖2所示。

圖2 蟻群算法清洗路徑優(yōu)化流程圖

3.1 數(shù)字微流控芯片污染單元清除模型轉(zhuǎn)換

在滿足時(shí)間約束以及流體約束的條件下，在實(shí)驗(yàn)液滴移動的同時(shí)，清洗液滴對污染單元清除并最終到達(dá)廢液池。針對清洗液滴清除污染故障的過程，可把數(shù)字微流控生物芯片污染單元及廢液池轉(zhuǎn)換成一個(gè)二維無向帶權(quán)圖G(V,E)，如圖3所示。其中，V表示污染單元，E表示兩個(gè)污染單元之間的路徑，邊上的權(quán)值表示兩者之間的距離。將得到的二維無向圖G作為動態(tài)MTSP模型，在不影響實(shí)驗(yàn)液滴運(yùn)行的同時(shí)尋找一條最優(yōu)清洗路徑。

圖3 數(shù)字微流控生物芯片污染故障清除模型

3.2 動態(tài)禁忌表建立

流體約束禁忌表：為了不影響實(shí)驗(yàn)液滴以及清洗液滴正常進(jìn)行，清洗液滴選擇下一單元時(shí)必須滿足流體約束條件，將不能選擇的相鄰單元放入禁忌表中。由于清洗液滴在不斷移動，每一滴清洗液的禁忌表也隨其移動不斷更新。例如，第m滴清洗液在t時(shí)刻的禁忌表，主要包括t時(shí)刻以及t+1時(shí)刻實(shí)驗(yàn)液滴和其它清洗液滴所在單元及其相鄰單元。實(shí)驗(yàn)液滴移動時(shí)間遠(yuǎn)遠(yuǎn)小于實(shí)驗(yàn)操作(混合，檢測等)所需要的時(shí)間，在實(shí)驗(yàn)液滴移動時(shí)，實(shí)驗(yàn)反應(yīng)區(qū)域范圍不發(fā)生變化，所以，流體約束禁忌表還包括當(dāng)前實(shí)驗(yàn)中實(shí)驗(yàn)液滴反應(yīng)區(qū)單元。

污染單元禁忌表：在t時(shí)刻每滴清洗液至多選擇一個(gè)污染單元，當(dāng)某一污染單元被清洗液滴選擇或者該污染單元被清洗，則將該污染單元放入禁忌表中，其它清洗液滴在t時(shí)刻不再對禁忌表中污染單元進(jìn)行選擇。在時(shí)刻t+1時(shí)首先，將未被清洗的污染單元禁忌表中移除，然后，對未清洗的污染單元重新選擇。

3.3 概率選擇策略

數(shù)字微流控生物芯片污染故障清除過程中，污染單元的選擇策略采用偽隨機(jī)比例選擇規(guī)則，既可以利用關(guān)于問題的先驗(yàn)知識，即關(guān)于節(jié)點(diǎn)之間的距離長度的啟發(fā)信息以及信息素信息，又可以進(jìn)行有傾向性的探索，提高螞蟻探索新路徑以增加全局搜索的能力。清洗液選擇新的目標(biāo)污染單元j時(shí)，按式(7)選擇下一個(gè)目標(biāo)單元j，J是根據(jù)式(8)選擇的下一目標(biāo)單元。

(7)

式中α和β分別決定了信息素和啟發(fā)式信息的影響力，allowedm為可選污染單元集合,τij(t)為兩個(gè)目標(biāo)污染單元i，j之間路徑上的信息素濃度,ηij(t)為啟發(fā)函數(shù),q為均勻分布在區(qū)間[0,1]的一個(gè)隨機(jī)變量，參數(shù)q0決定算法對新路徑的探索能力(0≤q0≤1)

(9)

式中 dsj為t時(shí)刻螞蟻所在陣列單元s到下一目標(biāo)污染單元j的曼哈頓距離。

3.4 信息素更新策略

最大最小蟻群算法把各路徑上的信息素軌跡量的值域限制在[τmin,τmax]區(qū)間內(nèi)，避免了早熟收斂，增加了全局最優(yōu)解的搜索能力，同時(shí)對最優(yōu)解路徑進(jìn)行全局更新，保證最優(yōu)解的收斂速度。信息素更新方式如式(10)所示

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

(10)

(11)

式中Lbs為全局最優(yōu)路徑長度，ρ為信息素?fù)]發(fā)因子，τij(t)為t次迭代i，j污染單元之間的信息素濃度，實(shí)驗(yàn)液滴最大的路由時(shí)間為20個(gè)時(shí)間單元[4]。

信息素全局更新會導(dǎo)致搜索的停滯，信息素局部更新能夠減少螞蟻所選擇污染單元的信息素，提高選擇其它污染單元的能力，所以,同時(shí)采用信息素局部更新策略

(12)

4 實(shí)驗(yàn)結(jié)果與分析

以Trinder P等人的人體生理體液的多元體外診斷實(shí)驗(yàn)[13]為例，實(shí)現(xiàn)污染故障在線清除策略驗(yàn)證。圖4表示實(shí)驗(yàn)中樣品與試劑變化過程，該體外檢測分析實(shí)驗(yàn)共有3種人體生理體液(尿液、血漿、血清)樣品，檢測試劑分別為葡萄糖和乳酸，樣品與檢測試劑在電極作用下在數(shù)字微流控生物芯片上移動。

圖4 體外檢測實(shí)驗(yàn)樣品與試劑變化關(guān)系圖

數(shù)字微流控生物芯片陣列單元數(shù)為16×16。液滴在100 Hz的變換頻率下，從一個(gè)陣列單元到相鄰陣列單元的花費(fèi)時(shí)間約為10 ms，這里清洗時(shí)間用陣列單元個(gè)數(shù)表示。每次迭代有30組螞蟻，每組有8只螞蟻分別從不同的清洗液分液池同時(shí)出發(fā)。經(jīng)過多次實(shí)驗(yàn)蟻群算法初始化參數(shù)如下：

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

實(shí)驗(yàn)結(jié)果如圖5所示。蟻群算法的污染單元數(shù)目為25，與未采用算法實(shí)驗(yàn)相比污染單元數(shù)目減少了52.8 %；蟻群算法的液滴路由時(shí)間為187個(gè)時(shí)間單元，與未采用算法實(shí)驗(yàn)相比路由時(shí)間減少了16.8 %；蟻群算法使用單元數(shù)為315，與未采用算法實(shí)驗(yàn)相比減少了18.8 %。從實(shí)驗(yàn)結(jié)果可知：使用蟻群算法進(jìn)行污染故障清除，能夠在路由時(shí)間以及使用單元數(shù)上得到優(yōu)化。

圖5 數(shù)據(jù)結(jié)果

算法收斂過程如圖6所示，算法于第106次迭代達(dá)到清洗時(shí)間最小值。螞蟻在探索新路徑時(shí)由于時(shí)間約束，在探索新路徑時(shí)不能在規(guī)定時(shí)間內(nèi)完成污染單元清洗操作，會導(dǎo)致探索新路徑失敗。生化分析共有K個(gè)實(shí)驗(yàn)，每個(gè)階段污染單元數(shù)目為n，螞蟻數(shù)為m，算法的空間復(fù)雜度與時(shí)間復(fù)雜度分別為

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

(13)

圖6 算法測試收斂圖

5 結(jié) 論

本文針對數(shù)字微流控生物芯片污染故障，提出了基于最大最小蟻群算法污染故障清除方案。在不影響實(shí)驗(yàn)液滴運(yùn)行的同時(shí)進(jìn)行清洗操作，利用蟻群算法尋找合理的清洗污染單元路徑，保障污染單元能夠順利清除，獲得最短清洗時(shí)間。以人體生理體液的多元體外診斷實(shí)驗(yàn)為算法驗(yàn)證平臺，結(jié)果表明:該算法能夠減少清洗時(shí)間以及陣列單元使用數(shù)目，保障了實(shí)驗(yàn)分析結(jié)果的準(zhǔn)確性。

[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] 盧衛(wèi)紅,付 力,鄭 琦,等.生物芯片技術(shù)的應(yīng)用與展望[J].傳感器與微系統(tǒng),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-)，女，博士，教授，研究生導(dǎo)師，從事集成電路測試、自動測試總線與系統(tǒng)方向研究工作。

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

廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室2016年度主任基金資助項(xiàng)目(YQ16104)；國家自然科學(xué)基金資助項(xiàng)目(61540014,61671164)

TP 306

A

1000—9787(2017)04—0019—04