有勁的基因資訊

目前 De Novo 序列組裝演算法有兩種, 一種稱為 overlap-layout-consensus , 簡稱 OLC. 另一種則是 de-bruijn-graph , 簡稱 DBG.

OLC 方法較為直觀, 先是將所有的 reads 做兩兩比對( pair-wise alignment ), 找出 reads 重疊( overlap )的區域, 再以圖學( graph theory )的方式呈現( layout ) reads 之間的重疊的關係, 以節點( vertex )表示 read, 邊( edge )表示 read 之間的重疊, 見圖一.

最後, 我們要將圖轉為序列. 這個問題, 和一個古典的問題相同, 就是漢米爾頓路徑問題 ( Hamiltonian Path Problem ), 如何走過圖上每一個節點, 而且每一個節點只經過一次？

目前組裝以OLC演算法為基礎的軟體有 Arachne, CAP3, Phrap, Newbler 等.

圖一 (左)以漢米爾頓路徑表達 reads 之間的關係; 白色圈, 節點, 代表 read ; 黑色實線, 邊, 表示 reads 之間的關係 (右) reads 和實際基因體之間的關係, 紅色線表示 reads 之間有相似的區域 ( overlap ), 可能是 repeat 的區域.

資料來源: http://bfg.oxfordjournals.org/content/early/2011/12/18/bfgp.elr035.short?rss=1

                   http://www.cbcb.umd.edu/research/assembly_primer.shtml