具有模組選擇能力之延遲最佳化數位微流體生物晶片合成技術

Abstract

數位微流體生物晶片是近年生醫電子領域的研發成果，可用以取代現行生化實驗所使用的大型分析儀器，以提升實驗效率和節省實驗成本。然而，要將各式各樣的生化反應轉移至生物晶片上進行，工程極為繁複，因此需要設計自動化工具的協助。縮短總反應時間是生物晶片合成程序最佳化的主要目標之一。為了進一步縮短反應時間，模組選擇的能力是不可或缺的。大多數現行具備模組選擇能力的合成方法皆為非決定性的方法，如基因演算法或禁忌搜尋演算法。然而，此類方法耗費過多的電腦執行時間而無法達到及時合成。本篇論文提出了一個具備模組選擇能力以達成延遲最佳化的數位微流體生物晶片合成方法，簡稱LOSMOS。此方法利用減少晶片上的儲存液滴的數量、並套用以系統延遲為標的的迭代重綁定過程，有效率地完成數位微流體晶片合成及降低總反應時間。根據實驗結果，LOSMOS比所有已知的合成方法更出色；包含目前最新的方法Path-scheduler，平均而言較其減少了18.22%的反應時間；且甚至超越了沒有模組選擇能力的整數線性規劃求得的最佳解─且僅需要極小的運算時間而已。

Digital microfluidic biochip (DMFB) is a latest development in biomedical electronics. DMFBs can replace traditional bench-top equipments, which are generally costly and bulky, to accelerate processes and save the costs of biochemical experiments. However, synthesis of various reactions on a biochip is a complicated work and thus needs the help of design automation tools. One of the major optimization goals of DMFB synthesis is latency minimization. To minimize the assay latency, module selection must be considered in synthesis flow. Most of current approaches with module selection capability adopt non-deterministic methods, such as genetic algorithms or Tabu searches. These methods may consume lots of runtime and thus make online (real-time) synthesis impossible. In this thesis, I propose an efficient latency-optimization synthesis with module selection ability, named LOSMOS. It minimizes assay latency by storage minimization and latency-driven iterative rebinding. Experimental results show that LOSMOS outperforms all the previous works, including the state-of-the-art Path-scheduler by 18.22% in terms of latency reduction; and even does better than an optimal ILP-based scheduler without module selection in most cases with very little runtime.