代谢路径预测与相似性搜索算法研究

The prediction and similarity search of metabolic pathways are two closely related issues of importance in metabolic engineering. The prediction of metabolic pathways can help to provide insights into metabolisms and find new alternative pathways that synthetize compounds; the similarity search of metabolic pathways can help to reveal the relevance of the structure and the function of organisms through the similarity of metabolic pathways. This project focuses on studying the computing methods for prediction and similarity search of metabolic pathways: propose the graph-based path-finding method, which is capable of finding branched pathways in specific organisms, to accurately return the branched pathways with high accuracy and sensitivity; propose the linear-programming-based path-finding method using CPU and GPU cooperatively parallel computing to quickly obtain the resulting pathways of high accuracy and short length; propose the parallel metabolic pathway alignment method using heuristic graph-based model on the hybrid CPU and GPU architectures to quickly obtain the pathway alignment results with high accuracy of reaction matching; propose the metabolic pathway query algorithm based on topological and biological features of pathways, and present efficient extraction method of topological and biological features of pathways, and propose the pathway matching algorithm to quickly return the pathways that are similar to target pathways from the pathway databases. This study will promote the development of the analytical techniques for metabolic pathways and provide the algorithmic foundation for the analysis and the application of metabolic engineering.

代谢路径预测与相似性搜索是代谢工程中两个紧密相关的重要问题。代谢路径预测有助于深入理解新陈代谢并找出合成化合物的新路径；代谢路径相似性搜索则有助于通过代谢路径相似性发现生物体结构和功能相关性。本项目将对代谢路径预测与相似性搜索方法展开以下研究：提出能在特定物种中搜索包含原子团转移的分支路径的基于图论的代谢路径预测算法，以准确找出精度和敏感度高的带分支路径；提出CPU和GPU协同计算的基于线性规划的代谢路径预测算法，以快速获得精度高、长度短的路径预测结果；提出与CPU和GPU异构机群相适应的基于图模型的启发式代谢路径并行比对方法，以快速获得反应匹配度高的路径比对结果；提出基于路径拓扑特征和生物特征的代谢路径查询算法、高效的代谢路径生物特征和拓扑特征提取方法和路径匹配算法，以快速从路径数据库中找出与目标路径相似度高的路径。本研究将促进代谢路径分析技术的发展，为代谢工程的分析和应用提供算法基础。

代谢路径预测和相似性搜索计算问题是生物数据分析领域的重要研究课题之一。在国家自然科学基金(No.61862006)的资助下，本项目在代谢路径预测算法、生物网络功能模体检测算法等方面做了一些工作，发表标注国家自然科学基金(No.61862006)的论文10篇，其中SCI论文9篇，并获授权中国发明专利2项。本项目针对分支代谢路径发现方法存在的问题和缺陷进行了分析和研究，提出通过追踪原子团的移动轨迹来找到代谢网络中包含特定反应和化合物的精度、阳性预测值和敏感度更好的分支路径的方法；设计通过融合代谢路径关键反应段的信息熵与互信息对代谢路径预测结果进行评分和排序的模型以提高预测路径结果的生化相关性；提出将功能模体检测转化为节点颜色互异的子图枚举的生物（代谢）网络功能模体检测方法，以得到更高的功能模体检测精度和召回率；提出通过融合网络拓扑信息和多源异构数据实现更精确和鲁棒性更好的药物疾病关联预测的方法；基于基因连锁不平衡特征提出了准确性更高的单核苷酸多态性与（代谢）疾病关联的预测方法。本项目所取得的研究成果，有助于代谢组学分析技术的应用，促进代谢工程分析和应用的发展。