科创中国
双向多步De Bruijn图的突出端识别与去除方法
成果类型：: 发明专利
发布时间: 2022-10-27 08:50:28
科技成果产业化落地方案
方案提交机构：天津市滨海新区| 门松 | 2022-10-29 23:19:15
本发明公开一种双向多步De Bruijn图的突出端识别与去除方法，包括步骤，S1、读取测序数据源文件，并构造双向多步De Bruijn图；S2、设定所述双向多步De Bruijn图中的每个顶点u的数据结构，对所述双向多步De Bruijn图突出端双向边的识别；S3、对所述双向多步De Bruijn图突出端双向边的去除。本发明基于相关节点的结构信息以及边的相对丰度来判别该突出端是否可以被删除，本发明方法的判别方式比以前的方法更精细，考虑的De Bruijn图中的信息更多；可以有效的删除突出端双向边，从而可以一定程度上提高contigs的长度，同步提高contig的质量。
1.一种双向多步De Bruijn图的突出端识别与去除方法，其特征在于，包括步骤，S1、 读取测序数据源文件，并构造双向多步De Bruijn图；S2、 设定所述双向多步De Brui jn图中的每个顶点u的数据结构，对所述双向多步De Brui jn图突出端双向边的识别；S3、 对所述双向多步De Brui jn图突出端双向边的去除。
2.如权利要求1所述的突出端识别与去除方法，其特征在于，所述De Brui jn图构造步 骤为，S11、 读取一个序列s;S12、 将序列s用滑动窗口切割为多个片段t，选取一片段t其标志数为cur、并标记其前、 后的片段的标志数分别为pre、lat;S13、 若t的编码小于其互补片段编码，则交换pre，lat的值；S14、 在cur的正向位置映射表的相应bit位置1来表示指向pre的边；S15、 在cur的反向位置映射表的相应bit位置1来表示指向lat的边.
基因序列分析以算法与数学模型为核心，包括:基因数据的存储与获取、序列比对、测序与拼接、基因预测、生物进化与系统发育分析、蛋白质结构预测、RNA结构预测、分子设计与药物设计、代谢网络分析、基因芯片、DNA计算等。生物技术和计算机信息处理技术的紧密结合，加快了处理生物信息数据的速度，使得在尽短的时间内对生物学做出准确的诠释，加快生物信息学的发展。
基因序列分析是对海量基因序列数据进行分析，从而提取和挖据新的生物信息知识。涉及到计算机技术中的机器学习、模式识别、书籍分析与挖掘、组合数学、随机模型、字符串、图形算法、分布式计算、高性能计算、并行计算等。
基因是人类最基本的遗传密码，代表着每个人的生命信息。基因序列上存在着遗传位点的细微差异，这些遗传密码的多态性与人类的健康、致病机理、医学治疗有着相当密切的关系。
中国科学院深圳先进技术研究院提升了粤港地区及我国先进制造业和现代服务业的自主创新能力，推动我国自主知识产权新工业的建立，成为国际一流的工业研究院。 深圳先进院目前已初步构建了以科研为主的集科研、教育、产业、资本为一体的微型协同创新生态系统，由九个研究平台，国科大深圳先进技术学院，多个特色产业育成基地、多支产业发展基金、多个具有独立法人资质的新型专业科研机构等组成。开展先进技术研究，促进科技发展。信息、电子、通讯技术研究新材料、新能源技术研究高性能计算、自动化、精密机械研究生物医学与医疗仪器研究相关学历教育、博士后培养与学术交流。
本发明的有益效果包括:基于相关节点的结构信息以及边的相对丰度来判别该突出端是否可以被删除，本发明方法的判别方式比以前的方法更精细，考虑的De Brui jn图中的信息更多；可以有效的删除突出端双向边，从而可以一定程度上提高contigs的长度，同步提高contig的质量。依照长度原则和少数性原则，将长度小于2k的均去除;利用Tour Bus算法中的深度优先搜索策略合并bubble，最后利用覆盖度阈值法去除了 erroneous connect1n。该方法也充分利用了paired-end双端信息，进一步解决repeat问题，优化了组装效果。Velvet充分利用图的结构性质，简化了数据冗余，速度较之前的算法有了很大的改进。虽然它没有在预处理阶段对序列进行纠错，但是其对错误的预防机制，很大程度上的弥补了这方面的缺陷。这使得它更好的应用在大型基因组序列的组装中。
技术合作
本发明一实施例的突出端双向边的去除流程图。具体实施方式[〇〇44]下面结合附图和具体实施例对本发明作进一步详细说明。[〇〇45]本发明实施例提供一种双向多步De Brui jn图的突出端识别与去除方法，包括步骤，[〇〇46] S1、读取测序数据源文件，并构造双向多步De Brui jn图；[0〇47] S2、设定所述双向多步De Bruijn图中的每个顶点u的数据结构，对所述双向多步De Brui jn图突出端双向边的识别；[〇〇48] S3、对所述双向多步De Bruijn图突出端双向边的去除。
以上所述本发明的具体实施方式，并不构成对本发明保护范围的限定。任何根据本发明的技术构思所作出的各种其他相应的改变与变形，均应包含在本发明权利要求的保护范围内。
下载app