欧拉路径算法

编辑:浅薄网互动百科 时间:2019-11-21 13:57:18
编辑 锁定
本词条缺少信息栏,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
欧拉路径算法最开始有Pevzner于1989年提出,基本思想是把DNA序列拼接问题转化成求欧拉路问题。

欧拉路径算法欧拉路径算法

编辑
Pevzner等人认为传统的交叠-排列-生成一致序列算法的思维模式导致了将拼接问题抽象成Hamilton路径问题,他们从另一种从来没有在实际测序工程中应用但是直接导致基因芯片工业的杂交测序方法SBH(Sequencing by Hybridization)得到启示,提出了在de Bruijin图中寻找欧拉路径拼接方法。

欧拉路径算法构造de Bruijin图算法步骤如下:

编辑
  1. 对于给定的read集合F={f1,f2,f3,…fn},将该集合中的每个read分割为k-mer,分割为图所示。如果read长度为L,k-mer长度K,那么该read将分割为L—K+1个k-mer,这些k-mer构成de Bruijin的顶点。
2. 对于两个k-mer u和v如果存在长度为k+1的子串t∈fi,且t的第一个长度为k的子串与u(或v)相同、最好一个长度为k的子串与v(或u)相同,则u和v之间存在一条边。
与传统的交叠-排列-生成一致算法相比,欧拉路径问题存在一个限行时间的欧拉路径算法,因此有更优的时间复杂度。基于欧拉路径思想的拼接算法有EULER、EULER-SR、Velvet、ALLPATHS等。
词条标签:
文化 出版物