交錯參考微流體晶片的統合液滴操作演算法

Abstract

由於生物微機電系統(bio-MEMS)的迅速發展，數位微流體生物晶片(digital microfluidic biochips)的規模和設計的複雜性，預計在不久的將來會有爆炸性的成長。因此電腦輔助設計強有力的支持，將在生物晶片的未來發展中扮演重要的角色。而在數位微流體生物晶片的多層設計階段中，液滴繞線是一項關鍵的挑戰。繞線必須安排每一個液滴的運動軌跡和考量其間的時間順序，因此具有極高的複雜性且對生物晶片性能具有重大的影響。在此篇論文中，我們提出了第一個交錯參考(cross-referencing)微流體晶片上的統合液滴操作演算法，能夠同時在液滴混合和液滴澆線問題上作最佳化處理。此演算法以創新的元件活化圖(cell-activation graph)為基礎，可以在真實世界的生物晶片上同時執行液滴行動和液滴澆線，並且保證其生物反應的正確性。此外，演算法比之最先進的繞線演算法只有一半的運行時間並進一步提高繞線性能。在規模更大、複雜度更高的測試中，我們的繞線演算法更展現出高度的可擴展性和可繞性。

From rapid development in bio-MEMS, the scale of a digital microfluidic biochip and the design complexity are expected to explode in the near future, thus requiring strong CAD support as VLSI industry has taken for granted. Among multiple synthesis stages of a digital microfluidic biochip, droplet routing which schedules the droplet movements in a time-multiplexed manner is a critical challenge due to the complex control constraints on different biochip architectures. We propose the first unified droplet manipulation algorithm to cope with the droplet manipulation problem on cross-referencing microfluidic biochips. Based on a novel graph model called cell-activation graph (CAG), the proposed method simultaneously performs droplet operations and droplet routing and guarantee the functional correctness of bioassays. It further improves the routing performance by 15% with only half of the runtime as compared with the state-of-the-art router. Experimental results on real-life benchmarks show that our algorithm achieves higher routability and scalability than previous droplet routing methods.