欧拉业话头含胶对路径算法最开始有Pevz来自ner于1989年提出，   基本思想是把DNA序列拼接问题转化成求欧拉路问题。

• 中文名称 欧拉路径算法
• 提出者 Pevzner
• 提出时间 1989年
• 适用领域 计算机

介绍

　　欧拉路径算法

　　Pevzner等人认为传来自统的交叠-排列-生成一致序列算法的思维模式导致了将拼减课固例多轻用盐接问题抽象成Hamilton路径问题，他们从另一种从来没有在实际测序工程中应用但是直接导致基因芯片工业的杂交测序方法SBH(Sequencing by Hybridiza360百科tion)得到启示，提出了在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等。