发明名称 |
双向多步deBruijn图的压缩存储和构造方法 |
摘要 |
本发明涉及一种双向多步deBruijn图的压缩存储和构造方法,包括压缩存储步骤,和deBruijn图构造步骤。本发明提供的双向多步deBruijn图的压缩存储和构造方法,(1)结合DNA序列互补双螺旋结构的特点,对de Bruijn图结构进行结构优化,使用双向多步de Bruijn图,可以将需要存储的图的节点减半;(2)针对序列组装的原始de Bruijn图规模异常庞大,对内存造成存储压力等问题,使用双向多步de Bruijn图的压缩存储技术,使得存储双向多步de Bruijn图的内存消耗控制在参考序列大小的100倍以内;(3)构造双向多步de Bruijn图,可将DNA序列组装问题分解为边融合子问题,更适合并行计算。 |
申请公布号 |
CN103093121A |
申请公布日期 |
2013.05.08 |
申请号 |
CN201210587059.6 |
申请日期 |
2012.12.28 |
申请人 |
深圳先进技术研究院 |
发明人 |
孟金涛;魏彦杰;成杰峰;冯圣中 |
分类号 |
G06F19/22(2011.01)I |
主分类号 |
G06F19/22(2011.01)I |
代理机构 |
深圳市科进知识产权代理事务所(普通合伙) 44316 |
代理人 |
宋鹰武 |
主权项 |
一种双向多步deBruijn图的压缩存储和构造方法,其特征在于,包括压缩存储步骤,具体为S11、读取一个序列s;S12、将序列s用滑动窗口切割为多个片段t;S13、对每个片段t,使用核酸编码表进行编码,并表示为一个64位的整数a;S14、将片段t进行反转,使用对称互补表将反转的片段互补处理,得到互补片段v,并再次使用步骤S13中的核酸编码表将互补片段进行编码,并表示为一个64位的整数b;S15、取整数a和整数b的最大数,作为片段t和互补片段v的k分子的标志数;S16、重复步骤S11‑S15,直至所有序列完成;和deBruijn图构造步骤,具体为S21、读取一个序列s;S22、将序列s用滑动窗口切割为多个片段t,选取一片段t其标志数为cur、并标记其前、后的片段的标志数分别为pre、lat;S23、若t的编码小于其互补片段编码,则交换pre,lat的值;S24、在cur的正向位置映射表的相应bit位置1来表示指向pre的边;S25、在cur的反向位置映射表的相应bit位置1来表示指向lat的边;S26、重复步骤S22‑S25,处理序列s的其他片段t,直至完成序列s的全部片段t,执行步骤S27;S27、读取一个新的序列s,重复步骤S22‑S26;直至处理完所有的序列,执行步骤S28;S28、完成双向多步de Bruijn图的构造。 |
地址 |
518055 广东省深圳市南山区西丽大学城学苑大道1068号 |