Any-Angle Routing Algorithm for Microfluidic Biochips Driven by Flow Path

Pan Youlin; Guo Shuai; Huang Xing; Liu Genggeng

doi:10.7544/issn1000-1239.202440058

Journal of Computer Research and Development > 2025 > Corrected proof > DOI: 10.7544/issn1000-1239.202440058 CSTR: 32373.14.issn1000-1239.202440058

Pan Youlin, Guo Shuai, Huang Xing, Liu Genggeng. Any-Angle Routing Algorithm for Microfluidic Biochips Driven by Flow Path[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440058

Citation:

PDF (1933 KB)

Any-Angle Routing Algorithm for Microfluidic Biochips Driven by Flow Path

Pan Youlin^{1, 2, 3,},
Guo Shuai^{1, 2, 3},
Huang Xing⁴,
Liu Genggeng^{1, 2, 3, ,}

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350116
2.
Engineering Research Center of Big Data Intelligence (Fuzhou University), Ministry of Education, Fuzhou 350116
3.
Fujian Key Laboratory of Network Computing and Intelligent Information Processing (Fuzhou University), Fuzhou 350116
4.
School of Computer Science, Northwestern Polytechnical University, Xi’an 710072

Funds: This work was supported by the National Natural Science Foundation of China (62372109) and the Fujian Science Foundation for Distinguished Young Scholars (2023J06017).

More Information

Author Bio:
Pan Youlin: born in 1996. PhD candidate. His main research interest includes design automation of microfluidic biochips

Guo Shuai: born in 1999. Master candidate. His main research interest includes design automation of microfluidic biochips

Huang Xing: born in 1991. PhD, professor, PhD supervisor. His main research interest includes design automation for microfluidic biochips and integrated circuits

Liu Genggeng: born in 1988. PhD, professor, PhD supervisor. Senior member of CCF. His main research interest includes design automation for microfluidic biochips and integrated circuits
Received Date: January 28, 2024
Revised Date: August 11, 2024
Accepted Date: September 02, 2024
Available Online: December 11, 2024

Graphical Abstract

Abstract

Abstract

Continuous-flow microfluidic biochips (CFMBs) have become a hot research topic in recent years due to their ability to perform biochemical assays automatically and efficiently. For the first time, PathDriver+ takes the requirements of the actual fluid transportation into account in the design process of CFMBs and implements the actual fluid transport and removal, and plans separate flow paths for each transport task, which have been neglected in previous work. However, PathDriver+ does not take full advantage of the flexibility of CFMBs routing because it only considers the optimization of flow channel length for the global routing in the mesh model, except for the detailed routing. In addition, PathDriver+ only considers the X architecture, while the existing work shows that the any-angle routing can utilize the routing resources more efficiently and shorten the flow channel length. To address the above issues, we propose a flow path-driven arbitrary angle routing algorithm, which can improve the utilization of routing resources and reduce the flow channel length while considering the actual fluid transportation requirements. The proposed algorithm constructs a search graph based on constrained Delaunay triangulation to improve the search efficiency of routing solutions while ensuring the routing quality. Then, a Dijkstra-based flow path routing method is used on the constructed search graph to generate a routing result with a short channel length quickly. In addition, in the routing process, channel reuse strategy and intersection optimization strategy are proposed for the flow path reuse and intersection number optimization problems, respectively, to further improve the quality of routing results. The experimental results show that compared with the latest work PathDriver+, the length of channels, the number of ports used, and the number of channel intersections are significantly reduced by 33.21%, 11.04%, and 44.79%, respectively, and the channel reuse rate is improved by 26.88% on average, and the total number of valves introduced at intersections is reduced by 42.01% on average, which demonstrates the effectiveness of the algorithm in this paper.
- continuous-flow microfluidic biochips,
- computer-aided design,
- physical design,
- any-angle routing,
- flow-path planning

FullText(HTML)

References (24)

References

[1]	张晓东,张朝昆,赵继军. 边缘智能研究进展[J]. 计算机研究与发展,2023,60(12):2749−2769 Zhang Xiaodong, Zhang Chaokun, Zhao Jijun. State-of-the-art survey on edge intelligence[J]. Journal of Computer Research and Development, 2023, 60(12): 2749−2769 (in Chinese)
[2]	Liu Genggeng, Liu Yufan, Pan Youlin, et al. Three-stage rapid physical design algorithm for continuous-flow microfluidic biochips considering actual fluid manipulations[J]. Electronics, 2024, 13(2): 332 doi: 10.3390/electronics13020332
[3]	Hu Xu, Chen Zhen, Chen Zhisheng, et al. Architectural synthesis of continuous-flow microfluidic biochips with connection pair optimization[J]. Electronics, 2024, 13(2): 247 doi: 10.3390/electronics13020247
[4]	Weigum S E, Floriano P N, Redding S W, et al. Nano-bio-chip sensor platform for examination of oral exfoliative cytology[J]. Cancer Prevention Research, 2010, 3(4): 518−528 doi: 10.1158/1940-6207.CAPR-09-0139
[5]	Watkins N N, Hassan U, Damhorst G, et al. Microfluidic CD4+ and CD8+ T lymphocyte counters for point-of-care HIV diagnostics using whole blood[J]. Science Translational Medicine, 2013, 5(214): 214ra170
[6]	Anderson M J, Hansen C L, Quake S R. Phase knowledge enables rational screens for protein crystallization[J]. Proceedings of the National Academy of Sciences, 2006, 103(45): 16746−16751 doi: 10.1073/pnas.0605293103
[7]	Kartalov E P, Zhong J F, Scherer A, et al. High-throughput multi-antigen microfluidic fluorescence immunoassays[J]. BioTechniques, 2006, 40(1): 85−90 doi: 10.2144/000112071
[8]	Huang Yanyi, Castrataro P, Lee C, et al. Solvent resistant microfluidic DNA synthesizer[J]. Lab on a Chip, 2007, 7(1): 24−26 doi: 10.1039/B613923J
[9]	王钦. 微流控生物芯片流体与控制协同物理设计算法研究[D]. 北京:清华大学,2018 Wang Qin. Research on control-fluidic physical codesign algorithm for microfluidic biochips[D]. Beijing: Tsinghua University, 2018 (in Chinese)
[10]	Thorsen T, Maerkl S J, Quake S R. Microfluidic large-scale integration[J]. Science, 2002, 298(5593): 580−584 doi: 10.1126/science.1076996
[11]	Chen Zhisheng, Huang Xing, Guo Wenzhong, et al. Physical synthesis of flow-based microfluidic biochips considering distributed channel storage[C]//Proc of the 22nd Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2019: 1525−1530
[12]	Tseng K, You S, Liou J, et al. A top-down synthesis methodology for flow-based microfluidic biochips considering valve-switching minimization[C]//Proc of the 22nd Int Symp on Physical Design. New York: ACM, 2013: 123−129
[13]	Wang Qin, Zou Hou, Yao Hailong, et al. Physical co-design of flow and control layers for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(6): 1157−1170
[14]	Grimmer A, Wang Qin, Yao Hailong, et al. Close-to-optimal placement and routing for continuous-flow microfluidic biochips[C]//Proc of the 22nd Asia and South Pacific Design Automation Conf. Piscataway, NJ: IEEE, 2017: 530−535
[15]	Huang Xing, Ho T, Guo Wenzhong, et al. MiniControl: Synthesis of continuous-flow microfluidics with strictly constrained control ports[C/OL]//Proc of the 56th Design Automation Conf. New York: ACM, 2019[2024-06-14]. https://ieeexplore.ieee.org/document/8806859
[16]	Huang Xing, Ho T, Chakrabarty K, et al. Timing-driven flow-channel network construction for continuous-flow microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(6): 1314−1327
[17]	Huang Xing, Guo Wenzhong, Chen Zhisheng, et al. Flow-based microfluidic biochips with distributed channel storage: Synthesis, physical design, and wash optimization[J]. IEEE Transactions on Computers, 2021, 71(2): 464−478
[18]	Huang Xing, Pan Youlin, Zhang G L, et al. PathDriver+: Enhanced path-driven architecture design for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(7): 2185−2198 doi: 10.1109/TCAD.2021.3103832
[19]	Lin C, Liu C, Chen I, et al. An efficient bi-criteria flow channel routing algorithm for flow-based microfluidic biochips[C/OL]//Proc of the 51st Design Automation Conf. New York: ACM, 2014[2024-06-14]. https://ieeexplore.ieee.org/document/6881468
[20]	Tseng T, Li Bing, Ho T, et al. Reliability-aware synthesis for flow-based microfluidic biochips by dynamic-device mapping[C/OL]//Proc of the 52nd Design Automation Conf. New York: ACM, 2015[2024-06-14]. https://ieeexplore.ieee.org/document/7167327
[21]	Yao Hailong, Ho T, Cai Yici. PACOR: Practical control-layer routing flow with length-matching constraint for flow-based microfluidic biochips[C/OL]//Proc of the 52nd Design Automation Conf. New York: ACM, 2015[2024-06-14]. https://ieeexplore.ieee.org/document/7167328
[22]	Yang Kailin, Yao Hailong, Ho T, et al. AARF: Any-angle routing for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(12): 3042−3055 doi: 10.1109/TCAD.2018.2789356
[23]	Chew L P. Constrained delaunay triangulations[C]//Proc of the 3rd Annual Symp on Computational Geometry. New York: ACM, 1987: 215–222
[24]	孔德慧,马春玲. 一种平面点集凸包与三角网格综合生成的算法[J]. 计算机研究与发展,2000,37(7):891−896 Kong Dehui, Ma Chunling. An algorithm for constructing the convex hull and the triangulation of a set of nodes in a plane[J]. Journal of Computer Research and Development, 2000, 37(7): 891−896 (in Chinese)

[1]	Peng Yingtao, Meng Xiaofeng, Du Zhijuan. Survey on Diversified Recommendation[J]. Journal of Computer Research and Development, 2025, 62(2): 285-313. DOI: 10.7544/issn1000-1239.202330600
[2]	MB-HGCN: A Hierarchical Graph Convolutional Network for Multi-behavior Recommendation“CCIR 2024推荐”[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440770
[3]	Zeng Weixin, Zhao Xiang, Tang Jiuyang, Tan Zhen, Wang Wei. Iterative Entity Alignment via Re-Ranking[J]. Journal of Computer Research and Development, 2020, 57(7): 1460-1471. DOI: 10.7544/issn1000-1239.2020.20190643
[4]	Dai Chenchao, Wang Hongyuan, Ni Tongguang, Chen Shoubing. Person Re-Identification Based on Deep Convolutional Generative Adversarial Network and Expanded Neighbor Reranking[J]. Journal of Computer Research and Development, 2019, 56(8): 1632-1641. DOI: 10.7544/issn1000-1239.2019.20190195
[5]	Gu Liang, Yang Peng, Dong Yongqiang. A Diversified Recommendation Method for UCL in Broadcast-Storage Network[J]. Journal of Computer Research and Development, 2017, 54(8): 1631-1643. DOI: 10.7544/issn1000-1239.2017.20170128
[6]	Meng Xiangfu, Bi Chongchun, Zhang Xiaoyan, Tang Xiaoliang, Tang Yanhuan. Web Database top-k Diverse Keyword Query Suggestion Approach[J]. Journal of Computer Research and Development, 2017, 54(7): 1577-1591. DOI: 10.7544/issn1000-1239.2017.20160005
[7]	Yu Wenzhe, Sha Chaofeng, He Xiaofeng, Zhang Rong. Review Selection Considering Opinion Diversity[J]. Journal of Computer Research and Development, 2015, 52(5): 1050-1060. DOI: 10.7544/issn1000-1239.2015.20131932
[8]	Wang Xianghai, Cong Zhihuan, Fang Lingling, Song Chuanming. HMM Training Model Using Blending Population Diversity Based Aaptive Genetic Algorithm Title[J]. Journal of Computer Research and Development, 2014, 51(8): 1833-1844. DOI: 10.7544/issn1000-1239.2014.20121211
[9]	Zhang Weiguo, Yin Xia, and Wu Jianping. A Computation Method of Path Diversity Based on AS Relationships[J]. Journal of Computer Research and Development, 2012, 49(1): 167-173.
[10]	Han Jianmin, Yu Juan, Yu Huiqun, Jia Jiong. A Multi-Level l-Diversity Model for Numerical Sensitive Attributes[J]. Journal of Computer Research and Development, 2011, 48(1): 147-158.

Cited By

Cited by

Periodical cited type(7)

1.	罗宇哲，李玲，侯朋朋，于佳耕，程丽敏，张常有，武延军，赵琛. 面向AIoT的协同智能综述. 计算机研究与发展. 2025(01): 179-206 . 本站查看
2.	王蕴，林霄，楼芝兰，李军，孙卫强. 面向边缘光算力网络的上行链路资源协同调度算法. 光通信技术. 2024(03): 45-51 .
3.	王铭源，王正国，李济顺，薛玉君. 层级式机械装备健康指数模型及管理系统构建. 金属矿山. 2024(09): 198-206 .
4.	王睿，王岩，尹朴，齐建鹏，孙叶桃，李倩，张易达，张梅奎. 面向边缘智能的协同训练研究进展. 工程科学学报. 2023(08): 1400-1416 .
5.	薛建强，史彦军，李波. 面向无人集群的边缘计算技术综述. 兵工学报. 2023(09): 2546-2555 .
6.	阴彦磊，王立华，廖伟智，张万达. 融合GRU-Attention与鲸鱼算法的流程制造工艺参数云边联动优化. 计算机集成制造系统. 2023(09): 2991-3005 .
7.	许浩，朱晓娟. SDN中基于模型划分的云边协同推理算法. 兰州工业学院学报. 2023(06): 31-37 .