作者 施純傑

定序物種的基因組序列是瞭解物種
間差異的重要課題。因為基因組
的序列非常長（ 例如人類基因組有3
Giga 鹼基），必須利用超音波等相關技
術先將其打斷成碎片，然後用定序儀器
將ATGC 的序列一一讀出。接著這些片
段再利用基因組裝的電腦程式串接起來
（圖一）。傳統Sanger 定序的技術，每
條序列可以讀到約1000 鹼基長，但由
於相當耗費人力，定序成本非常高，而
且所需時間相當久，因此早期只能針對
幾種重要的模式物種進行定序。
近年來， 短序列定序技術的興起，像
是Illumina HiSeq 2000 等，能夠快速讀
出非常大量的序列資料，而且價格更遠
低於傳統Sanger 定序的費用。然而因為
序列的總數量相當龐大（一次可產生好
幾百Giga 的鹼基資料），而每條的序列
長度卻只有約100 到250 鹼基，使得利
用這種資料進行基因組重組的問題比起
利用Sanger 定序的方式更加困難。
Species DNA extraction Sequencer Millions of sequencing reads
ATGCGATGACGGATGAC
Genome Assembly Assembled genomic sequences
ATGCGATGACGGATGACG…GATGCGTGCAGAGTGCAGATGAAGTGAC
GGTGGTGATCAGTAGTA…GGTAGTAATATTAGTCGTACAGATGCA
TTAGATCGATCAGTCAGTATT…ATTATGTTTGCCAGATTATTT
:
:
:
:
CCCAGGTGACGATG….CAGGGAGTAGCAGA
目前主要短序基因組重組方法有兩大
類：extension-based 和 de Bruijn (or Eulerian)
graph-based。Extension-based 方
法主要先以某個短序開始尋找和它有重
疊的其他短序進行延伸。因為不用建
立所有短序間重疊的關係，因此計算時
間快速而所需記憶體也非常少。然而因
為鹼基的定序錯誤和基因組中重複的片
段，所以大都組裝出的序列都非常零
碎。
另一類的方法則是以de Bruijn graph
為基礎。這類方法首先將每個短序拆成
k 個連續但只差一個鹼基的更短序列（稱
為k-mer），每個k-mer 在graph 中代表
一個節點，在序列中連續兩個k-mers 的
關係則利用edge 將其連接起來。因此
掃瞄全部資料一次，就可以建立所有短
序使用的k-mers 和連接關係（稱為de
Bruijn graph），進而所有短序間的前後
關係就可以藉由分析共有(k-1)-mers 的
結果得到（圖二）。然而在graph 找出
基因組定序和組裝的基本流程
( 圖一)。

Jump
Extension
candidate
Rseed
Re
Rs
TGTACGTAGA
GTACGTAGAG
TAAGGAAGGAATTAAGGGGG GAGATAGGGC
ACCGGTTAAGGAAGGAATTA GTAGAGATAG
AGAATTAAGGGGGGCCGGTA
Remapping
TTGTACGTAGAGATAGGGCGTA
A successful
extension
SSE
S最佳路徑是一個 NP-complete 的問題， SE
因此只能利用heuristic 的方法來解決。
另外因為定序鹼基的錯誤會產生許多
false positive 的節點， 而且當k-mer 短
於重複片段的長度會造成多重路徑的問
題，也是諸多這類方法所極力解決的。
因為需要將完整的graph 儲存在記
憶體， 因此de Bruijn graph 的方法比
extension-based 的方法需要更多的記憶
體。為了要重組大型基因組，這類的方
法必須利用減少輸入序列數目和產生
graph 的大小（ 像是ALLPATHS-LG 和
SOAPdenov)，才能重組像人類這樣大型
的基因組。然而大多數這類工具在有限
的記憶體下，都無法處理大基因組的組
裝資料。雖然利用鹼基校正的方法，可
以降低graph 的大小，增加組裝正確性，
但執行時間仍然隨著短序列總數和長度
快速的增加。另外為了跨越多重出現的
片段，k-mer 的設定需要越來越接近序
列長度，然而k-mer 的長度增加，記憶
體的需求也會呈現指數增加。當k-mer
設定超過100 個鹼基後，暴增的記憶體
需求已經使得這類的重組程式遭遇極大
的瓶頸。因此，如何在組裝品質、記憶
體需求和執行時間之間取得最佳點仍是
目前基因組組裝的主要挑戰。
最近，我們的團隊開發出一套新的
extension-based 短序基因組組裝程式
（ 稱為JR-Assembler)。除了延續這類
方法具有快速而且節省記憶體的優點，
主要的概念是利用整個短序做延伸（稱
為跳躍），而不是一個鹼基一個鹼基做
延伸。這樣的做法除了可以加快執行速
度外，更可以跨過小於序列長度的重複
片段（圖三）。另外因為大多數的定序
錯誤都在序列的尾端，因此在無法延伸
時，我們的程式自動切除尾端的部分鹼
基，增加延伸的機會。最後我們會利用
其他短序來回貼延伸的序列，一方面可
以檢查延伸的正確性，另一方面也可檢
查是否有遇到大於序列長度的重複片
段，是否需要先被截斷，然後再利用其
他跨接的資訊接回。利用不同大小尺寸
基因組的定序及模擬資料，我們和其他
基因組組裝程式做比較。對於大型基因
組，JR-Assembler 的記憶體使用率和執
行時間都比其他基因組組裝程式更有效
率，而且組裝結果的品質也相當好。對
於小型和中型的基因組，JR-Assembler
組裝結果的品質，都比大多數的程式得
到的結果要來的好。這項成果已經發表
在Proceedings of the National Academy
of Sciences (Plus) 2013，而JR-Assembler
的完整工具可以在下面網址下載：http://
jr-assembler.iis.sinica.edu.tw/。本成果的
合作成員包括中研院生多中心李文雄院
士和國立成功大學生物資訊與訊息傳遞
研究所劉宗霖助理教授等。