王 鶴

(河南工程學(xué)院機(jī)械工程學(xué)院 河南 鄭州 451191)

0 引 言

數(shù)字微流控生物芯片的出現(xiàn)，使得生化分析檢測(cè)中樣品試劑的操作如分配、輸運(yùn)、混合、分離、存儲(chǔ)與檢測(cè)不再僅限于傳統(tǒng)的實(shí)驗(yàn)室完成。數(shù)字微流控生物芯片不僅可以輕松實(shí)現(xiàn)這些操作，而且逐漸使生化分析檢測(cè)的整體微型化、集成化、自動(dòng)化與便攜化成為可能。這種芯片消耗試劑小、制造成本低、檢測(cè)靈敏度高，而且可以重復(fù)使用，種種優(yōu)勢(shì)使其在生化醫(yī)學(xué)、藥物診斷、食品安全和環(huán)境監(jiān)測(cè)等多個(gè)領(lǐng)域應(yīng)用廣泛[1-2]。

介電濕潤(rùn)是數(shù)字微流控生物芯片最常見的液滴驅(qū)動(dòng)方式，通過(guò)對(duì)驅(qū)動(dòng)電極依次施加電壓，離散的微液滴可在電濕潤(rùn)力的作用下在二維陣列上完成各種操作。微液滴通常被分為同質(zhì)和異質(zhì)兩種。對(duì)于同質(zhì)液滴的尋址而言，只需對(duì)電極利用率和液滴到達(dá)目標(biāo)電極的時(shí)間進(jìn)行優(yōu)化即可。然而，異質(zhì)液滴的尋址除了優(yōu)化電極利用率和尋址時(shí)間以外，還要避免液滴間的污染。另外，數(shù)字微流控生物芯片通常都是通過(guò)直接尋址方式[3-5]來(lái)控制驅(qū)動(dòng)電極，即每個(gè)驅(qū)動(dòng)電極都通過(guò)一根引線連接到一個(gè)控制引腳，由控制引腳來(lái)控制對(duì)應(yīng)的驅(qū)動(dòng)電極的得失電，以此來(lái)控制液滴的運(yùn)動(dòng)。如果芯片是由M行、N列電極組成，那么就有M×N個(gè)控制引腳來(lái)控制這些電極，任意一個(gè)引腳都可以單獨(dú)激活，這種控制方式允許最大自由地操控液滴。對(duì)于設(shè)計(jì)簡(jiǎn)單的數(shù)字微流控生物芯片來(lái)說(shuō)，控制引腳與驅(qū)動(dòng)電極之間的引線布置比較容易，易于實(shí)現(xiàn)。然而，隨著生化分析對(duì)芯片的要求越來(lái)越高，需要更多的生化分析實(shí)驗(yàn)在同一個(gè)芯片并行操作執(zhí)行，這使得芯片設(shè)計(jì)越來(lái)越復(fù)雜，驅(qū)動(dòng)電極和控制引腳的數(shù)目越來(lái)越多，片上引線的布置也越來(lái)越困難，大大增加了芯片的制造成本，繼而出現(xiàn)了交叉尋址方式[6]的微流控芯片。這種驅(qū)動(dòng)電極控制方式有M+N個(gè)控制引腳，某行和某列的控制引腳同時(shí)激活，便可控制其交叉處的驅(qū)動(dòng)電極，大大減少了控制引腳數(shù)目，也簡(jiǎn)化了驅(qū)動(dòng)電極與控制引腳間引線的布置。但交叉尋址方式會(huì)引發(fā)電極干涉問(wèn)題，難以控制多個(gè)液滴的并行運(yùn)動(dòng)，為解決這一問(wèn)題，引腳受限的電極控制方式[7-9]被提出。本文基于引腳受限的電極控制方式，在最小化控制引腳的前提下，優(yōu)化并行運(yùn)動(dòng)的異質(zhì)液滴的運(yùn)動(dòng)路徑。

1 問(wèn)題描述

液滴尋址就是在滿足所有要求的前提條件下，在數(shù)字微流控芯片的二維電極陣列中為多個(gè)并行運(yùn)動(dòng)的液滴尋找到使其從源電極運(yùn)動(dòng)到目標(biāo)電極的最佳路徑。這里將一個(gè)液滴在兩個(gè)功能模塊之間或功能模塊和儲(chǔ)液池之間的移動(dòng)稱為一個(gè)路徑網(wǎng)絡(luò)。在一個(gè)路徑網(wǎng)絡(luò)中，只有一個(gè)液滴從其源電極移動(dòng)到目標(biāo)電極，這種路徑網(wǎng)絡(luò)被稱為雙針網(wǎng)絡(luò)；當(dāng)有兩個(gè)液滴分別從各自的源電極出發(fā)，移動(dòng)至混合點(diǎn)，再移至目標(biāo)電極，這種路徑網(wǎng)絡(luò)有兩個(gè)源電極、一個(gè)目標(biāo)電極，因此被稱為三針網(wǎng)絡(luò)，如圖1所示。圖1中，S、M和T分別表示液滴在其路徑上的源電極、混合電極和目標(biāo)電極。對(duì)于液滴尋址來(lái)說(shuō)，要想獲取有效的液滴路徑，并行運(yùn)動(dòng)的液滴之間必須有足夠的空間(通常至少一個(gè)電極距離)，以避免液滴的意外混合。而對(duì)于三針或多針網(wǎng)絡(luò)而言，需要在精確的位置合并液滴，這些位置稱為混合器，屬于功能模塊。功能模塊是一種虛擬設(shè)備，由若干個(gè)電極組成，具有液滴存儲(chǔ)、混合和稀釋等功能。在液滴尋址過(guò)程中，這些功能模塊被視為障礙物，液滴運(yùn)動(dòng)路徑必須繞過(guò)片上這些功能模塊。因此，為了避免液滴路徑和用于液滴混合、稀釋、存儲(chǔ)等分析操作的功能模塊之間的沖突以及意外混合，在功能模塊的外圍往往需要設(shè)置一個(gè)能夠完全包圍該功能模塊的隔離區(qū)，如圖2(a)所示，網(wǎng)格區(qū)域就是一個(gè)隔離區(qū)，由若干隔離電極組成。這就是所謂的流體約束，即當(dāng)時(shí)刻t某液滴位于電極單元(x,y)時(shí)，在該時(shí)刻t到下一時(shí)刻t+1期間，任何其他液滴不得進(jìn)入其周圍的8個(gè)電極，如圖2(b)所示。而時(shí)間約束是另外一個(gè)約束，它規(guī)定了所允許的最大液滴尋址時(shí)間。

圖1 路徑網(wǎng)絡(luò)圖

圖2 片上結(jié)構(gòu)簡(jiǎn)圖

基于以上分析，異質(zhì)液滴在引腳受限的數(shù)字微流控生物芯片上執(zhí)行并行運(yùn)動(dòng)時(shí)，其尋址的主要目標(biāo)就是在滿足流體約束和時(shí)間約束的前提條件下，對(duì)任一液滴的路徑規(guī)劃都要實(shí)現(xiàn)：① 最小化液滴最遲到達(dá)時(shí)間；② 最小化液滴尋址路徑上的所需電極數(shù)目；③ 最小化控制引腳數(shù)目；④ 避免液滴間的污染。因此，假設(shè)有n個(gè)液滴需要為其設(shè)置尋址路徑，則建立路徑網(wǎng)絡(luò)集合net={net1,net2,…,netn}，其中任意液滴的路徑均表示為neti=(Si，Ti)，i=1,2,…,n，路徑長(zhǎng)度由該路徑上所用電極總數(shù)來(lái)表示，則有：

(1)

2 控制引腳的優(yōu)化

對(duì)于單個(gè)液滴，通常需要3個(gè)控制引腳順序驅(qū)動(dòng)，以使其從源電極運(yùn)動(dòng)到目標(biāo)電極，這3個(gè)控制引腳是驅(qū)動(dòng)液滴運(yùn)動(dòng)的最低要求，引腳集regp=[p1,p2,p3]。如圖2所示，一個(gè)液滴從源電極S(2,1)移動(dòng)到目標(biāo)電極T(2,10)，首先電極(2,2)置高電壓，液滴移動(dòng)到(2,2)，此處需要一個(gè)控制引腳p1；若要繼續(xù)向右移動(dòng)的話，則需將電極(2,3)置高電壓，電極(2,2)接地，那么電極(2,3)需要另外一個(gè)控制引腳p2。同理，將電極(2,4)置高電壓，電極(2,3)接地，液滴則可繼續(xù)右行，但如果將引腳p1分配給電極(2,4)的話，p1同時(shí)將電極(2,2)和(2,4)置高電壓，液滴會(huì)發(fā)生變形，甚至分離，因此，必須為電極(2,4)分配另外一個(gè)引腳p3；此后，可按p1、p2和p3的順序依次將這三個(gè)控制引腳分配給后續(xù)的電極，液滴便可從源電極S運(yùn)動(dòng)到目標(biāo)電極T。因此，同一控制引腳可分配給不同的電極，但必須滿足由同一引腳控制的兩電極之間相隔一定的距離(用Δ表示)，該距離通常至少為兩個(gè)電極的距離，這樣才能保證液滴正常運(yùn)動(dòng)。當(dāng)兩液滴路徑有交叉時(shí)，如果還只用這3個(gè)控制引腳來(lái)對(duì)液滴進(jìn)行尋址的話，在交叉處往往會(huì)出現(xiàn)沖突，因此，在交叉處需要至少5個(gè)額外的控制引腳以實(shí)現(xiàn)對(duì)兩個(gè)液滴的準(zhǔn)確尋址，如圖2中十字交叉陰影所示。

3 異質(zhì)液滴尋址算法

對(duì)于單個(gè)液滴，從源電極出發(fā)至目標(biāo)電極，最多只有4個(gè)可通行方向，即向左、向右、向上、向下，如圖3中由源電極S3(6,2)移至目標(biāo)電極T3(10,4)的液滴。由于T3位于S3的右下方，因此液滴從S3出發(fā)只有沿向下或向右方向移動(dòng)，才有可能獲得最短尋址路徑，所以液滴從片上任意位置出發(fā)至目標(biāo)電極的路徑上只可能有兩個(gè)方向的路徑的曼哈頓距離最短。在運(yùn)動(dòng)過(guò)程中，當(dāng)液滴遇到障礙物時(shí)，以當(dāng)前運(yùn)動(dòng)方向?yàn)闇?zhǔn)，其可繼續(xù)運(yùn)動(dòng)的方向只有3個(gè)，即向左、向右和向后，其中向后運(yùn)動(dòng)會(huì)遠(yuǎn)離目標(biāo)電極，該方向不可取，至于向左還是向右取決于兩個(gè)方向的電極與目標(biāo)電極之間的曼哈頓距離；當(dāng)液滴遇到污染電極時(shí)，以當(dāng)前運(yùn)動(dòng)方向?yàn)闇?zhǔn)，其可繼續(xù)運(yùn)動(dòng)的方向可有4個(gè)，即向左、向右、向后和向前(通過(guò)污染電極)，同樣向后運(yùn)動(dòng)不可取，其余3個(gè)方向需要繼續(xù)尋址，通過(guò)比較后續(xù)路徑上無(wú)法避免的污染電極數(shù)目來(lái)進(jìn)行選擇。

圖3 控制引腳設(shè)置

本文通過(guò)啟發(fā)式估計(jì)函數(shù)[10]來(lái)規(guī)劃液滴路徑，該函數(shù)決定了當(dāng)前液滴所在位置周圍的所有相鄰電極中哪一個(gè)即將被液滴遍歷。依據(jù)液滴已經(jīng)遍歷的電極數(shù)Etn和候選電極與該液滴目標(biāo)位置電極之間的曼哈頓距離EMP，該啟發(fā)式估計(jì)函數(shù)可評(píng)估出相鄰電極的適應(yīng)度值Ef，函數(shù)表達(dá)式為：

Ef=Etn+EMP

(2)

因此，基于引腳受限的數(shù)字微流控生物芯片的異質(zhì)液滴尋址算法流程如下：

輸入：二維電極陣列(M×N)，n個(gè)液滴路徑網(wǎng)絡(luò)net，一組由片上功能模塊和液滴源電極、目標(biāo)電極組成的障礙物。

輸出：尋址路徑，液滴最遲達(dá)到目標(biāo)電極的時(shí)間(LAT)，污染電極數(shù)目(CN)，尋址路徑上所用電極數(shù)目(EN)及全部路徑所用電極集合EN[]，控制引腳使用數(shù)目(PN)，新控制引腳集合newp[]。

初始化：PN=3，LAT=0，CN=0，Etn=0，regp=[p1,p2,p3]，EN=0，EN[]=?，newp[]=?

構(gòu)建列表FM，包含所有障礙物的坐標(biāo)；

構(gòu)建列表net，包含n個(gè)液滴路徑網(wǎng)絡(luò)的源電極(S)和目標(biāo)電極(T)坐標(biāo)；

for 所有路徑網(wǎng)絡(luò)i=1 ton

{for (Si,Ti) 建立兩條曼哈頓路徑MPi1，MPi2；

if (BCi1>BCi2) 選擇MPi2；

else 選擇MPi1； //BCi1、BCi2表示在路徑MPi1，

//MPi2上的障礙物和污染電極總數(shù)

初始化 當(dāng)前電極=Si；

if (未分配控制引腳)

檢查和其他路徑網(wǎng)絡(luò)的距離；

if (Δ≥2)

從常規(guī)引腳集regp中依次選取引腳分配

給當(dāng)前電極；

else 分配一個(gè)新的控制引腳分配給當(dāng)前電極，

并更新newp[]；PN++；

while (未到達(dá)目標(biāo)電極Ti)

{if (未遇到障礙物或污染電極)

按照選擇的MPi繼續(xù)移動(dòng)；

else

{if (遇到障礙物)

{在障礙物的前一個(gè)電極創(chuàng)建節(jié)點(diǎn)；

計(jì)算節(jié)點(diǎn)電極周圍除障礙物以外的所有相鄰電極與目標(biāo)電極Ti的曼哈頓距離EMP；

選擇Ef值最小的相鄰電極作為下一步移動(dòng)的位置；

EN++；更新EN[];

}

else (遇到污染電極)

{在污染電極的前一個(gè)電極創(chuàng)建節(jié)點(diǎn)；

計(jì)算節(jié)點(diǎn)電極周圍所有相鄰電極與目標(biāo)電極Ti的曼哈頓距離EMP；

除污染電極以外，比較其他相鄰電極的Ef值，選出最小值Efmin與污染電極的適應(yīng)度值Ecf相比較；

if (Efmin

選擇Efmin對(duì)應(yīng)的電極作為下一步移動(dòng)的位置；

else 比較分別沿Efmin和Ecf移動(dòng)的后續(xù)路徑上

污染電極數(shù)量以確定下一步移動(dòng)位置；

EN++；更新EN[];

統(tǒng)計(jì)CN數(shù)目；

}

}

if (未分配控制引腳)

檢查和其他路徑網(wǎng)絡(luò)的距離；

if (Δ≥2)

從常規(guī)引腳集regp中依次選取引腳分配給當(dāng)前電極；

else 分配一個(gè)新的控制引腳分配給當(dāng)前電極，并更新newp[]；PN++；

}

更新LAT;

}

算法的實(shí)施過(guò)程如圖4所示。

圖4 液滴路徑算法的實(shí)施

圖4中斜線陰影部分表示由功能模塊代表的障礙物。液滴1從S1運(yùn)動(dòng)到T1，液滴2從S2運(yùn)動(dòng)到T2，液滴3和液滴4分別由S3、S4出發(fā)，混合之后運(yùn)動(dòng)至T3處。

4 實(shí) 驗(yàn)

針對(duì)本文提出的液滴尋址算法和文獻(xiàn)[11]中的算法，通過(guò)體外Ⅰ、體外Ⅱ、蛋白Ⅰ和蛋白Ⅱ在內(nèi)的4組生化檢驗(yàn)[9]實(shí)驗(yàn)，采用C語(yǔ)言在同一PC系統(tǒng)中對(duì)兩種算法分別進(jìn)行模擬仿真。仿真結(jié)果如表1所示。

表1 兩種算法結(jié)果的比較

由表1可知，相對(duì)于文獻(xiàn)[11]的算法，本文算法使液滴到達(dá)目標(biāo)電極的運(yùn)動(dòng)時(shí)間至少減少了75.6%，最高達(dá)87%，而尋址路徑上所使用的電極數(shù)量、污染電極數(shù)量以及控制引腳數(shù)量分別至少減少了22.3%、20%和37.5%，甚至可以完全避免出現(xiàn)電極被污染的情況。另外，隨著芯片尺寸的增大或者網(wǎng)絡(luò)數(shù)量的減小，本文算法對(duì)液滴到達(dá)目標(biāo)電極的運(yùn)動(dòng)時(shí)間、尋址路徑上所使用的電極數(shù)量、污染電極數(shù)量以及控制引腳數(shù)量這四個(gè)目標(biāo)的優(yōu)化程度也越來(lái)越顯著。由上述分析可知，本文算法能夠大大減小生化分析中液滴到達(dá)目標(biāo)電極的運(yùn)動(dòng)時(shí)間，降低尋址路徑上所使用的電極數(shù)量以及控制引腳的數(shù)量，而且對(duì)于異質(zhì)液滴來(lái)說(shuō)，實(shí)驗(yàn)過(guò)程中污染電極的數(shù)量也有所減少。因此，本文提出的異質(zhì)液滴尋址算法與現(xiàn)有算法相比，具有一定的優(yōu)勢(shì)，可實(shí)現(xiàn)對(duì)生化分析檢驗(yàn)中的液滴運(yùn)動(dòng)時(shí)間、電極使用數(shù)量、污染電極數(shù)量以及控制引腳數(shù)量等多個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化，而且優(yōu)化效果較為顯著。

5 結(jié) 語(yǔ)

生化分析實(shí)驗(yàn)的高要求以及芯片設(shè)計(jì)的復(fù)雜性對(duì)異質(zhì)液滴在數(shù)字微流控生物芯片上的路徑規(guī)劃問(wèn)題提出了更高的挑戰(zhàn)。本文提出基于多目標(biāo)的異質(zhì)液滴尋址優(yōu)化啟發(fā)式算法，在液滴尋址時(shí)間、電極使用數(shù)量、控制引腳數(shù)量以及污染電極數(shù)量等多方面都表現(xiàn)出了明顯的優(yōu)勢(shì)，可減少數(shù)字微流控生物芯片的制造成本，盡可能地避免了生化分析檢驗(yàn)中異質(zhì)液滴之間的交叉污染。仿真結(jié)果驗(yàn)證了算法的有效性和可行性，其對(duì)數(shù)字微流控生化檢驗(yàn)過(guò)程中液滴尋址優(yōu)化具有一定的參考價(jià)值。