Velvet 是 Daniel Zerbin 與 Ewan Birney 提出的一種應用在序列組裝 (assembly) 的演算法,這個演算法是利用一種特殊的序列索引 (De Bruijn graph) 來記錄各條互相配對 read 序列,並且在此索引上依照序列 depth 以及較長序列組裝路徑來處理定序誤差及 repeat 的情況。De Bruijn graph 索引結構的設計特別適合短序列並且索引結構本身並不容易受到 read 序列庫大小而增大,同時還可記錄序列上 repeat 的片段,因此此一演算法大多應用於 Solexa 所產生的序列庫。

新圖片.png  

Velvet 在組裝序列的過程中,先將 read 序列儲存於一張網絡結構 (De Bruijn graph) 以及一張查詢表格中(上圖節錄於原作論文中,是一張非常簡化的網絡)。此一網絡結構主要是將所有 read 片段以固定長度 (K-mer,像是一個 reading frame) 抓取序列下來,單一 read 序列由多個K-mer組成,並在網絡中以一個 base 位移相互並列在一起(也就是上圖傾斜排列的序列)。如果有遇到與其配對的 read,就會把配對的 K-mer 分離出(形成上圖中藍色的區塊),並且將原來鄰近的 K-mer 以一個箭頭連接起來。將 read 序列轉變成上圖的過程中也會將各 read 在 De Bruijn graph 起始位置以及與其它序列配對的資訊記錄在一個表格中。

另外為了解決反股序列配對的問題,在上圖中的各個藍色區塊下方記錄反股序列的訊息。

在建立網絡之後,在尋找連續 read 序列的過程中,Velvet 會依照 coverage 變化的差異將不合理的 K-mer 刪除,並且重新調整網絡的結構。

logo_121_55.png  

YourGene 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言