歐拉路徑算法

歐拉路徑算法最開始有Pevzner於1989年提出，基本思想是把DNA序列拼接問題轉化成求歐拉路問題。

基本介紹

• 中文名：歐拉路徑算法
• 提出者：Pevzner
• 提出時間：1989年
• 適用領域：計算機

基本介紹

歐拉路徑算法

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等。