An Envolutionary Algorhtm For Droplet Routing In Digital Microfluidic Biochips

Digital microfluidic biochip,as an innovative microfluidic technology,has the characteristics of miniaturization,automation,low cost and high efficiency,which make the biochemical detection and analysis more efficient.It has great application value in the fields of clinical diagnostics,environmental monitoring,and drug preparation.The droplet routing is an important design stage in the advanced synthesis of digital microfluidic biochip.It determines the routing paths for droplets and requires droplets to correctly perform the reaction process.During the movement of droplets,the routing algorithm should avoid possible accidental mixing between droplets,while satisfying the time constraint.Routing algorithms usually take minimizing the latest arrival time of a droplet and minimizing the number of cells used in the droplet movement process as the optimization objectives.In order to effectively solve droplet routing problem,we formulate the problem and clarify the input and output,the constraints and the optimization objectives.For four different mixing scenarios,we use four different methods to avoid possible accidental mixing.Further,we propose a droplet routing algorithm based on the evolutionary path priority,which includes an evolutionary algorithm and a path search algorithm.The evolutionary algorithm uses path priority as individual code to search for the optimal routing order.The path search algorithm is to obtain routing paths of all droplets under a given path priority.The path search algorithm is divided into two steps.The first step ignores the time sequence and makes droplets move one by one.At the same time,a cost function is introduced into the Dijkstra algorithm,so that the droplets tend to select better cells for moving;the second step considers time sequence,synthesizing all droplet paths together,so that the droplets can move at the same time while meeting constraints.The experiment includes two parts.The first part is single-objective experiment,and it takes minimizing the latest arrival time of a droplet as the optimization objective.The second part is multi-objective experiment which takes minimizing the latest arrival time of a droplet and the number of cells used as the optimization objectives.The proposed algorithm is tested on three benchmark suites,including a set of real assays.The experimental results show that in the case of only considering the completion time,compared with the baseline algorithms,the proposed algorithm achieves shorter completion time on the Benchmark Suite I and the Benchmark Suite II,and shorter average completion time on the Benchmark Suite III.In the case of considering two objectives,compared with the baseline algorithms,the proposed algorithm achieves shorter completion time and average completion time on three benchmark suites,and increases the number of cells used.In order to verify the correctness of routing algorithm and the legitimacy of droplet paths,we designed a tool to visualize the droplet's movement,and report conflicts between droplets.In addition,this tool provides a droplet routing solver based on our algorithm which allows users to customize test samples,parameters and select different optimization objectives.