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

許川佩, 劉磊振, 萬春霆

(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