基于DBG策略序列拼接算法的构件组装研究

作     者：吴刚 

作者单位：江西师范大学 

学位级别：硕士

导师姓名：石海鹤

授予年度：2021年

学科分类：0711[理学-系统科学] 07[理学] 

主      题：序列拼接 产生式编程 领域特征建模 PAR方法 软件重构 

摘      要：第二代高通量测序技术和第三代单分子测序技术的快速发展,加速了人类科学家对基因组及其所携带的信息进行分析的整个进程,基因测序成本也随着高通量测序技术和单分子测序技术的发展而不断降低,包括基因组学、转录组学等在内的多组学科的生物数据不断累积,给生物信息学提供了海量的数据资源,如何高效、精准地处理这些生物信息学数据,已经成为了限制测序技术发展和生物信息学发展的瓶颈。基于DBG(De Bruijn Graph)策略的序列拼接算法是生物信息学中的一个关键算法,广泛地应用于基因序列拼接领域。但是在当今的序列拼接算法领域中,已有的研究工作都是满足特定需求而被研究的,极少有人从序列拼接领域层次来对算法开展研究,导致整个序列拼接领域缺少一个可以应用于各种场景的算法框架。在一定程度上导致了序列拼接算法的冗余性和人为选择算法可能导致的计算误差等问题。通过深入分析基于DBG策略的序列拼接算法(DBG Strategy-based Assembly algorithm,DBGSA)领域,将基于DBG策略的序列拼接算法划分为误差去除、构建De Bruijn图、去除操作、contigs、scaffolds五个大步骤,继而根据产生式编程方法对DBGSA进行领域特征建模和算法构件交互设计,在PAR平台的支持下,形式化实现DBGSA算法构件库,进一步使用DBGSA构件库装配生成具体算法。本文将装配出的基因序列拼接算法与现在主流的Velvet、SOAPdenovo两种基因序列拼接算法进行比较,结果表明,本文装配出的基因序列拼接算法具有很高的实用性。本文从领域层次开展的序列拼接算法研究工作,保证了算法开发的高效性和装配结果算法的可靠性,同时也为解决序列拼接领域问题提供了有价值的参考。另外,为更好地支持算法构件组装工作,本文重构生物序列比对算法构件组装平台的同时,对其进行了功能改善和扩充,将基因序列拼接算法组装功能也加入到平台中,获得新的生物序列算法构件组装平台版本。该版本软件质量得到大幅度改善,代码结构更加清晰,提高了实用性和可维护性。使用该平台,用户无需过多了解算法的实现细节,只需通过可视化界面进行选择符合约束的构件,即可装配出所需的生物序列算法,这样极大程度的提高了用户的体验感。