没有合适的资源?快使用搜索试试~ 我知道了~
基于deBruijn图的算法概述.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 110 浏览量
2021-10-06
09:13:29
上传
评论
收藏 812KB DOC 举报
温馨提示
试读
29页
基于deBruijn图的算法概述.doc
资源推荐
资源详情
资源评论
- -
基于 de Bruijn 图的算法概述
de Bruijn 图简介
传统的 Sanger 测序的 reads 较长〔1000bp〕,数据量较少,精
度较高,所有的
组装算法都利用 reads 之间的重叠,通过公共路径的方法解决拼接
问题。而新一代
测序产生的数据 read 更短、覆盖度更高、序列精度较低,为此这
种―read 为中心‖
的方法面临海量计算的困境,似乎不可能找到恰当的启发式方法来
处理大量的重
叠。de Bruijn 图框架为处理高覆盖、短序列提供了很好思路,该
框架借鉴了 Pevzner
和 Waterman 等人针对传统的长 reads 提出的欧拉遍历方法
[37,38]
,并在此根底上针
对新一代测序数据的特点进展了改良要想以较低的本钱快速得到某
个新物种的 DNA 分子碱基序列,就要依靠新一
代的测序技术和从头测序拼接组装算法。目前新一
- - word.zl-
- -
代测序数据用于从头 测序的短序列 拼接组装算法 普遍采用 de
Bruijn 图数据构造。
在 de Bruijn 图上,每一个 k-mer 都构成图的节点,如果两个 k-
mer 在某一 read 中
相邻,那么这两个节点之间就有一条边。reads 集合中的每个 read
都对它所含的节点和边加权,这样 reads 集合产生一个节点和边都
具有权值的 de Bruijn 图。在存储
每一个 k-mer 时,往往要建一个无冲突的哈希表,以加快查找速度。
而建立哈希表
可能会消耗更多的存。但是,由于每个 k-mer 在哈希表中只存储一
次,不管该
k-mer 在 read 中出现了多少次,所以实际消耗的存小于存储所有
read 所需要的
空间。另外,基因组中的重复片段会在 de Bruijn 图中产生环路。
环路将在遍历 de
Bruijn 图时产生障碍。
目前的研究主要面临两个问题,一个是基因组中存在大量重
复片段,一个是测序错误。这两个问题相互影响,使问题变的更加
复杂。本文通
过仔细分析这两个问题,来改良以前基于 de Bruijn 图的算法,提
出一种新的 de
Bruijn 图,并且引入了决策表的概念,通过决策表里的信息来选取
- - word.zl-
- -
后继 k-mer,并在适当的时候更新决策表。
1 基因组中存在大量重复片段
重复片段问题可用如下方法解决:通过比对,可先将重复片段隔离
开来,较
高的覆盖度有利于重复片段的隔离,但是,较多的测序错误将不利
于该过程的进
行。因为错误的存在,严格的比对将导致一些重复片段未被发现,
而非严格的比
对会把一些不是重复片段的区域隔离开来,这不是本文所希望的。
如果重复片段
比 read 长,可利用 pared end read 来解决;如果重复片段比
read 短,那么该 read
又被称为 spanner,一个 spanner 就是一个重复片段两端再加几
个碱基组成。利用
spanner 解决重复片段问题需要如下两个信息:一是重复片段两端
配对的 read,这
两个 read 必须不一样;二是重复片段中的一个配对 read,只要知
道一个即可,另
一个配对 read 可以不在重复片段中
- - word.zl-
- -
2 测序过程中可能出现错误
现在主要有两种
纠错方法,一种基于多重比对,通过将多个 read 放在一起比对来
发现错误,如图
1-2 所示。
通过图中 4 条 read 比对,可发现 read 3 中的一个碱基错误(read
3 的第 5 个碱
基),该方法在 overlap 过程中比拟常用,而在 de Bruijn 图中,
所使用的纠错方法
是:假设当前 k-mer 在一条 read 中连续未出现恰好 k 次,可以认
为该 read 中存在一
个碱基错误。
2 基于 de Bruijn 图算法的一般步骤
1) 确定 k 值,建立 de Bruijn 图。这时需要扫描所有 read 数据,
将每一个长
为 L 的 read 拆分成 L-k+1 个 kmer,并用所有 read 的所有 k-
mer 来累加,建立节点
和边都加权的 de Bruijn 图;
2) 化简 de Bruijn 图,连续线性延伸节点合并为单一节点,产生一
- - word.zl-
- -
些碱基序列
更长的节点;
3) 错误校正,删去由于测序错误产生的尖端和泡状构造;
4) 通过 read 的配对末端 (pair-end)、环化配对(mate-pair)信息
伸展或者删去一
些环;
5) 依据环上节点和边的权值(覆盖深度信息)进一步伸展或者删去一
些环;
6) 遍历 de Bruijn 图产生 contig。
实际上,de Bruijn 图是一种特殊的加权
图,不仅图的结点上有权值,而且图的边上也有权值。化简 de
Bruijn 图是非常关
键的一个步骤,通过对 de Bruijn 图化简,可降低算法的时间复杂
性以及空间复杂
性,同时可以保证错误校正顺进展
拼接总体思路
假设所有满足上述条件〔1〕的 read 都已经存到了 read 库中,下
面就用这些
read 来构建 contig。给定 k 值后,长度为 k 的一个 DNA 片段称
- - word.zl-
剩余28页未读,继续阅读
资源评论
gjmm89
- 粉丝: 14
- 资源: 19万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功