CPU和GPU混合体系结构上生物网络比对并行算法研究

The hybrid multi-core CPU and GPU architectures propose new challenges and offer new opportunity for the research and applications of high-performance parallel algorithms. Biological networks are one of complex network systems. The scale of biological data established by high-throughput experiment is huge. Biological networks alignment is one of the important issues in the biological data analysis field and it is a computation-intensive and combinatorial optimization problem. This project will present a two-layer computation method for CPU and GPU cooperatively parallel computing the scoring matrix of nodes similarity and topology similarity for biological networks in the wavefront and horizontal ways, propose the data partitioning approach in multiple level caches and the loads-balance scheduling strategies between CPU and GPU and among computing nodes in the heterogeneous cluster, and design and implement the efficient and scalable parallel algorithms for local alignment and global alignment of biological networks on the hybrid CPU and GPU architectures to obtain quickly the accurate alignment results. The research results are helpful to satisfy the requirments for large scale biological network analysis in post-genome era and promote the applications and development of new generation high-performance computer architectures and parallel algorithms in biological information computation research.

新型的多核CPU和GPU混合体系结构对高性能并行算法研究与应用提出了新挑战、提供了新机遇。生物网络是一类复杂网络系统，由高通量实验建立的生物数据规模十分庞大。生物网络比对计算问题是生物数据分析领域重要的研究课题之一。生物网络比对问题是计算密集型、组合优化问题。本项目研究提出多核CPU和GPU协同计算、波前式并行和水平并行计算生物网络结点相似度和拓扑相似度得分矩阵的两层并行计算方法，提出适用于生物网络比对问题并行计算的多级缓存数据分配方法、CPU与GPU之间以及异构机群计算节点之间负载均衡的任务调度策略，设计实现与CPU和GPU混合体系结构相适应的高效、可扩展的生物网络局部比对和全局比对并行算法，以快速获得准确的比对结果，满足后基因组时代大规模生物网络分析的应用需求，促进新一代高性能计算机体系结构及并行算法在生物信息计算研究中的应用与发展。

新型的多核CPU和GPU混合体系结构对高性能并行算法研究与应用提出了新挑战、提供了新机遇。生物网络是一类复杂网络系统，由高通量实验建立的生物数据规模十分庞大。生物网络比对计算问题是生物数据分析领域重要的研究课题之一。生物网络比对问题是计算密集型、组合优化问题。本项目研究设计多核CPU和GPU协同计算生物网络结点相似度和拓扑相似度得分矩阵的两层并行计算方法，提出适用于生物网络比对问题并行计算的多级缓存数据分配方法、CPU与GPU之间负载均衡的任务调度策略，设计与CPU和GPU混合体系结构相适应的高效可扩展、准确度高的生物网络局部和全局比对并行算法及生物序列比对并行算法；提出通过追踪原子团搜索生化网络以获得替代路径中包含特定化合物和反应的平均精度、敏感度和阳性预测值性能更好的代谢路径预测算法，利用生化反应二元关系比对大规模代谢路径以获得较高拓扑相似度的比对结果、发现同一进化分支物种代谢路径之间规模更大的生化相关区域的高效算法，通过功能模块映射比对生化网络多条代谢路径以获得更接近标准分类的系统发育树重构算法；设计融合信息量差异和聚类精炼以获得更高召回率和精度、识别出保守性高和匹配更多真实motif的生物网络多模体发现算法，通过离散傅里叶变换提取DNA序列特征、更准确地反映物种聚类特征的无需比对的DNA 序列相似度计算算法。结题时，研究工作成果发表15篇学术论文，其中SCI收录5篇论文，中文核心期刊/CSCD核心期刊论文10篇，发表的英文论文中有2篇被他人发表的SCI论文引用18次（其中1篇论文被他人发表的SCI论文引用17次），发表的中文论文中有4篇被他人发表的中文期刊论文和博士硕士学位论文引用12次；申请了2项中国发明专利。本项目的研究成果有助于顺应后基因组时代大规模生物网络分析的应用需求、促进新一代高性能计算机体系结构及并行算法在生物信息计算研究中的应用与发展。