| Digital microfluidic biochip(DMFB)is an emerging technology which integrate conventional biological laboratory procedures on a small biochip with more accurate,less human labor,lower cost,and higher efficiency.With these advantages,DMFB has wide application prospects in the fields such as biochemical analysis,clinical diagnosis,and drug preparation.DMFBs will become larger in size with more applications in the coming years.We need software tools with higher quality to assist in the design automations.Fluid level synthesis tools of DMFBs can tell biochips how to control the droplets so that they can implement the desire bioassays.The synthesis process includes four steps: resource binding,operation scheduling,module placement,and droplet routing.Evolutionary algorithm(EA)is suitable for the complex combinatorial optimization problems in the synthesis process.The purpose of this study is to research the fluid level synthesis process of the digital microfluidic chip,and to design a better EA-based method for the first three steps of the synthesis flow.The combination of the first three steps of synthesis flow is called 3D module placement in this article.The purpose of the synthesis of the digital microfluidic biochips is to allow the biochemical assay to be legally executed on the chip with higher throughput.The assay completion time is a common optimization goal inside previous synthesis methods.But droplets need resources to be stored on the biochips when unable to perform the related operations during the execution of the assay.The results obtained by the previous algorithms often have too many storage operations,which lead to occupying extra space,activating extra electrodes,and making the module placement and droplet routing more complicated.In tackle with this problem,this study add a secondary goal to reduce the storage operations besides the assay completion time.Some previous scheduling methods and 3D placement methods are based on genetic algorithms(GA)or other metaheuristic algorithms.Those methods often contain a heuristic scheduling algorithm inside to generate legal solutions.The quality of the heuristic scheduling algorithm is an important factor that affects assay completion time.This study research on the previous heuristic scheduling algorithm and find that those algorithms cannot generate all legal solutions by themselves.So the previous GA-based scheduling methods perform poorly because of the small searching space limited by the inside heuristic algorithm.To tackle with this problem,a novel heuristic scheduling algorithm,order scheduling,is proposed.The performance of the proposed scheduling algorithm is verified by process on the colorimetric protein assay and in-vitro assay.The experimental results show that the genetic scheduler based on order scheduling is more effective than the genetic schedulers based on the previous heuristic scheduling methods.The individual scheduling methods cannot fully utilize the chip resources.The 3D module placement method which combine resource binding,operation scheduling and module placement together can solve this problem.The results obtained by the previous 3D module placement methods are often limited by the representation scheme of the layout.This study use a 3D matrix to control the electrode resources on the chip.Each electrode on the chip can be represented and allocated independently at every time step.This scheme can represent all the layout possibilities.It can also be intuitively and flexibly applied to various complex resource constraints.This article proposes a genetic algorithms-based 3D module placement algorithm,which use order schedule and 3D matrix to control chip resources.The proposed method can obtain legal results while optimizing the assay completion time and the total storage time.Experiments are performed using colorimetric protein assay and in-vitro assay.Compared with the previous 3D module placement method,the proposed algorithm can complete the same biochemical assay in a shorter time.In addition,compared with the algorithm which only consider the optimization goal of assay completion time,the algorithm which add the total storage time as a secondary goal can not only obtain the same assay completion time,but also obtain results with shorter storage time. |
