應用于數字微流控生物芯片的異質液滴尋址算法

王 鶴

(河南工程學院機械工程學院 河南 鄭州 451191)

0 引 言

數字微流控生物芯片的出現，使得生化分析檢測中樣品試劑的操作如分配、輸運、混合、分離、存儲與檢測不再僅限于傳統的實驗室完成。數字微流控生物芯片不僅可以輕松實現這些操作，而且逐漸使生化分析檢測的整體微型化、集成化、自動化與便攜化成為可能。這種芯片消耗試劑小、制造成本低、檢測靈敏度高，而且可以重復使用，種種優勢使其在生化醫學、藥物診斷、食品安全和環境監測等多個領域應用廣泛[1-2]。

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

1 問題描述

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

圖1 路徑網絡圖

圖2 片上結構簡圖

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

(1)

2 控制引腳的優化

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

3 異質液滴尋址算法

對于單個液滴，從源電極出發至目標電極，最多只有4個可通行方向，即向左、向右、向上、向下，如圖3中由源電極S3(6,2)移至目標電極T3(10,4)的液滴。由于T3位于S3的右下方，因此液滴從S3出發只有沿向下或向右方向移動，才有可能獲得最短尋址路徑，所以液滴從片上任意位置出發至目標電極的路徑上只可能有兩個方向的路徑的曼哈頓距離最短。在運動過程中，當液滴遇到障礙物時，以當前運動方向為準，其可繼續運動的方向只有3個，即向左、向右和向后，其中向后運動會遠離目標電極，該方向不可取，至于向左還是向右取決于兩個方向的電極與目標電極之間的曼哈頓距離；當液滴遇到污染電極時，以當前運動方向為準，其可繼續運動的方向可有4個，即向左、向右、向后和向前(通過污染電極)，同樣向后運動不可取，其余3個方向需要繼續尋址，通過比較后續路徑上無法避免的污染電極數目來進行選擇。

圖3 控制引腳設置

本文通過啟發式估計函數[10]來規劃液滴路徑，該函數決定了當前液滴所在位置周圍的所有相鄰電極中哪一個即將被液滴遍歷。依據液滴已經遍歷的電極數Etn和候選電極與該液滴目標位置電極之間的曼哈頓距離EMP，該啟發式估計函數可評估出相鄰電極的適應度值Ef，函數表達式為：

Ef=Etn+EMP

(2)

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

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

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

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

構建列表FM，包含所有障礙物的坐標；

構建列表net，包含n個液滴路徑網絡的源電極(S)和目標電極(T)坐標；

for 所有路徑網絡i=1 ton

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

if (BCi1>BCi2) 選擇MPi2；

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

//MPi2上的障礙物和污染電極總數

初始化 當前電極=Si；

if (未分配控制引腳)

檢查和其他路徑網絡的距離；

if (Δ≥2)

從常規引腳集regp中依次選取引腳分配

給當前電極；

else 分配一個新的控制引腳分配給當前電極，

并更新newp[]；PN++；

while (未到達目標電極Ti)

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

按照選擇的MPi繼續移動；

else

{if (遇到障礙物)

{在障礙物的前一個電極創建節點；

計算節點電極周圍除障礙物以外的所有相鄰電極與目標電極Ti的曼哈頓距離EMP；

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

EN++；更新EN[];

}

else (遇到污染電極)

{在污染電極的前一個電極創建節點；

計算節點電極周圍所有相鄰電極與目標電極Ti的曼哈頓距離EMP；

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

if (Efmin

選擇Efmin對應的電極作為下一步移動的位置；

else 比較分別沿Efmin和Ecf移動的后續路徑上

污染電極數量以確定下一步移動位置；

EN++；更新EN[];

統計CN數目；

}

}

if (未分配控制引腳)

檢查和其他路徑網絡的距離；

if (Δ≥2)

從常規引腳集regp中依次選取引腳分配給當前電極；

else 分配一個新的控制引腳分配給當前電極，并更新newp[]；PN++；

}

更新LAT;

}

算法的實施過程如圖4所示。

圖4 液滴路徑算法的實施

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

4 實 驗

針對本文提出的液滴尋址算法和文獻[11]中的算法，通過體外Ⅰ、體外Ⅱ、蛋白Ⅰ和蛋白Ⅱ在內的4組生化檢驗[9]實驗，采用C語言在同一PC系統中對兩種算法分別進行模擬仿真。仿真結果如表1所示。

表1 兩種算法結果的比較

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

5 結 語

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