基于多路径广度优先搜索算法的代谢通路设计与实现  

Design and Implementation of Metabolic Pathway Based on Multi-path Breadth-first Searching Algorithm

作　　者：黄祖成 沈梦圆 侯至丞 TOKUYASU Taku Andrew 蒙海林 HUANG Zucheng;SHEN Mengyuan;HOU Zhicheng;TOKUYASU Taku Andrew;MENG Hailin(Intelligent Robot&Equipment Research Center,Guangzhou Institute of Advanced Technology,Chinese Academy of Sciences,Guangzhou 511458,China;Bioengineering Research Center,Guangzhou Institute of Advanced Technology,Chinese Academy of Sciences,Guangzhou 511458,China;Guangdong Provincial Key Laboratory of Synthetic Genomics,CAS Key Laboratory of Quantitative Engineering Biology,Shenzhen Institute of Synthetic Biology,Shenzhen Institute of Advanced Technology,Chinese Academy of Sciences,Shenzhen 518055,China)

机构地区：[1]广州中国科学院先进技术研究所,机器人与智能装备研究中心,广州511458 [2]广州中国科学院先进技术研究所生物工程研究中心,广州511458 [3]中国科学院深圳先进技术研究院深圳合成生物学创新研究院,中国科学院定量工程生物学重点实验室,广东省合成基因组学重点实验室,深圳518055

出　　处：《集成技术》2021年第5期72-79,共8页Journal of Integration Technology

基　　金：国家重点研发计划项目(2018YFA0903200,2018YFA0902900);国家自然科学基金项目(31870776);广东省科技计划项目(2019B030316016,2017A030313149);广州市科技计划项目(201904010337);深圳市科技创新委员会项目(KQTD2015033117210153)。

摘　　要：寻找从底物到产物的可行代谢通路是代谢工程设计中的核心环节。针对复杂代谢网络中代谢通路不唯一的情况以及传统K条最短路径(K-Shortest Path,KSP)算法效率低的问题,该文通过对传统KSP算法的优化,引入关键边概念以减少非必要的重复计算;搭建代谢通路设计Web平台,使用并行计算方式提升了算法运算性能。最终,通过引入代谢网络图,对改进KSP算法的多路径搜索效率进行验证,结果显示较传统KSP算法有5~9倍的性能提升。To find possible reactions that exist in metabolic networks is essential for metabolic engineering.The K-shortest path(KSP)algorithm is a traditional method that is usually used to identify alternative metabolic pathways.To improve the computation efficiency of conventional KSP method,an efficient KSP-based searching method is proposed in this paper.The basic idea is to introduce the critical edge to reduce the redundant calculation.A web-platform is constructed to design metabolic pathways.The parallel computing technique is introduced to improve the computing efficiency.The proposed method is validated on the KEGG metabolic pathways map,and the results show that the proposed method improve the computation efficiency by 5-9 times,compared with the traditional KSP algorithm.

关 键 词：代谢通路 多路径搜索 合成生物学 算法 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]