考虑流端口数量约束下的连续微流控生物芯片流路径规划算法

Flow-path Planning Algorithm for Continuous-flow Microfluidic Biochips with Strictly Constrained Flow Ports

连续微流控生物芯片通常需要构建复杂交错的流路径来支持样本/试剂的运输,也需要大量的流端口来推动液体的有序流动,这阻碍了生物芯片的进一步发展。因此,该文考虑了有限流端口驱动下的流路径规划问题,并提出一个流路径驱动下的连续微流控生物芯片的架构综合设计流程。首先采用基于列表调度算法实现操作的绑定与调度,通过时间窗对调度进行调整,从而满足给定的流端口数量约束;然后采用基于序列对表示的遗传算法求得芯片的布局设计,通过考虑并行任务之间的冲突以及组件之间的连接关系,进一步优化了布局解的质量;最后采用基于A^(*)寻路的优化布线算法规划所需的流路径,以有效减少流通道总长度和交叉点数量,生成具有高执行效率的芯片架构。实验结果表明,该方法在严格满足给定的流端口数量约束条件下,极大地避免了各种液体运输任务的冲突,同时也优化了流通道的总长度以及交叉点的数量,降低了芯片的构造成本。

Continuous-flow microfluidic biochips need usually to construct complex and interlaced flow paths to support the transportation of sample/reagent,and also require a large number of flow ports to promote the orderly fluids flow,thereby hinders the further development of the biochips.Therefore,the flow-path planning problem under strict constraints of flow ports is formulated,and a path-driven architecture synthesis flow for continuous-flow microfluidic biochips is proposed.Firstly,the list scheduling algorithm is used to realize the binding and scheduling of operations.To satisfy the constraints of a limited number of flow ports,a time window can be applied to adjust the final scheduling result.Then,the flow-layer placement is obtained by genetic algorithm based on sequence pair representation,and the quality of the layout solution is further optimized by considering the conflicts between parallel tasks and the connections between components.Finally,an A^(*)-based routing method is used to complete flow-path planning for reducing effectively the total flow-channel length and the number of intersections,thereby generating a biochip layout with high execution efficiency.The experimental results show that the proposed method greatly avoids the conflicts of various fluid transportation tasks under the condition of satisfying the given flow port constraints strictly,and optimizes the total length of flow channels and the number of intersections,thereby reducing the manufacturing cost of the chip.