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]	Cai Huayang, Huang Xing, Liu Genggeng. Control Logic Routing for Continuous-Flow Microfluidic Biochips Using Deep Reinforcement Learning[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440034
[2]	Deng Xinguo, Zhang Xinhong, Chen Jiarui, Liu Qinghai, Chen Chuandong. A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440069
[3]	He Xiaowei, Yue Daheng, Guo Wei, Sui Bingcai, Deng Quan. Promoting Frequency Method for Our Own High Performance Processor Physical Design[J]. Journal of Computer Research and Development, 2024, 61(6): 1429-1435. DOI: 10.7544/issn1000-1239.202330942
[4]	Liu Jingsen, Yuan Mengmeng, Li Yu. Robot Path Planning Based on Improved Salp Swarm Algorithm[J]. Journal of Computer Research and Development, 2022, 59(6): 1297-1314. DOI: 10.7544/issn1000-1239.20201016
[5]	Zheng Bolong, Ming Lingfeng, Hu Qi, Fang Yixiang, Zheng Kai, Li Guohui. Dynamic Ride-Hailing Route Planning Based on Deep Reinforcement Learning[J]. Journal of Computer Research and Development, 2022, 59(2): 329-341. DOI: 10.7544/issn1000-1239.20210905
[6]	Liu Bingtao, Wang Da, Ye Xiaochun, Fan Dongrui, Zhang Zhimin, Tang Zhimin. The Data-Flow Block Based Spatial Instruction Scheduling Method[J]. Journal of Computer Research and Development, 2017, 54(4): 750-763. DOI: 10.7544/issn1000-1239.2017.20160138
[7]	Feng Xiang, Ma Meiyi, Shi Yin, and Yu Huiqun. Path Planning for Mobile Robots Based on Social Group Search Algorithm[J]. Journal of Computer Research and Development, 2013, 50(12): 2543-2553.
[8]	Shao Jie, Yang Jingyu, Wan Minghua, and Huang Chuanbo. Research on Cnvergence of Multi-Robots Path Planning Based on Learning Classifier System[J]. Journal of Computer Research and Development, 2010, 47(5): 948-955.
[9]	Li Hongjun, Bu Yanlong, Xue Han, Li Xun, and Ma Hongxu. Path Planning for Mobile Anchor Node in Localization for Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2009, 46(1): 129-136.
[10]	Yu Kun, Wu Guoxin, Xu Libo, Wu Peng. Optimal Path Based Geographic Routing in Ad Hoc Networks[J]. Journal of Computer Research and Development, 2007, 44(12): 2004-2011.