序列組裝

序列組裝（Sequence assembly）是生物資訊學中的一種分析方法。此方法通過序列比對和序列合併等演算，將短片段的DNA建構成為較長的連續序列。此技術的創立，是因為被測序的核酸分子通常長度都遠大於目前存在的DNA測序技術。而此分析能試圖從有限長度的DNA測序結果，重建出原本被測序分子的樣貌。

序列組裝最常被使用在高通量測序資料的分析上（例如基因組霰彈槍定序，或者RNA轉錄體測序）。這一類的測序技術會產生大量的測序片段（read，複數reads），而這些片段的長度依照不同的技術，短為數十，長可至上萬個鹼基對（前者如因美納（Illumina）的定序平台，後者如PacBio的單分子即時測序或奈米孔洞測序）。而序列組裝旨在合併這些短片段來重建原本的分子序列。

我們可將序列組裝想像成從大量片段的文字中拼湊出一整篇文章的過程：被測序的分子就是那篇文章，而測序片段就是那段文章中，隨機切取出來的句子。其中一種重建出這段文章的方式，就是找到句子中重疊的部分，因為一旦找到夠多重疊的部分，我們就有機會將每個句子連接到一起，進而得到原始的文章。不難想像，此過程的困難不僅僅在於需要進行大量的片段比對，還會因原本文章的複雜度而製造更多問題：例如原本的文章可能有許多重復的段落，而帶有這些重複段落的文句可能會重疊在一起；又或者我們所拿到的句子中若有錯別字，亦會增加尋找重疊片段的難度。同樣的問題也同樣存在於生物資訊的序列組裝分析裡。

<image>

## 方法

依照參考序列的有無，序列組裝可分為：

- De-novo 組裝（拉丁語：de novo意指「新的」）：在沒有參考序列的情況下，僅使用序列片段所提供的資訊來組裝的方法。
- Mapping 組裝：在有參考序列的情況下，將測序片段比對至參考序列上，以取得組裝結果。
- 引導式組裝（guided assembly）：介於de-novo組裝與mapping組裝之間 ——在有參考序列的情況下，以其作為引導，並結合使用序列片段本身的資訊進行組裝。

舉例來說，在進行全基因組測序分析時，de-novo組裝可能被使用在非模式物種基因組的分析上，因為其沒有臨進物種的基因組提供參考。相反的，如果有有鄰近或相同物種的基因組可做參考，則可使用mapping組裝或引導式組裝（genome guided assembly）。

De-novo 組裝又可分為三種演演算法：

- Overlap - Layout - Consensus（OLC）法：即文章前段所舉的例子。此演演算法分為三個步驟（圖一）。首先找出測序片段中「重疊」的部分，接著「配置」出這些片段可能的順序，最後從這些片段中找出「保守」的序列，組裝得到原始序列。此方法雖然直觀，但其電腦演算量較大，故通常被使用在組裝資料量不大而測序長度較長的資料上（例如Pac-Bio的測序結果）。
- De-Bruijn（DBG）法：此方法使用數學圖論中De-Bruijn 圖的概念，先將每個測序片段拆解成k-mer（一個字串中所有長度為k的可能字串子集合）。接著從這些k-mer重疊的區段建構出De-Bruijn圖，再利用演演算法解出De-Bruijn圖的結構並取得組裝結果（圖二）。此方法雖不如OLC法直觀，但在電腦演算需求上較OLC法小，故通常被用於資料量大而片段短的分析上（例如Illumina的測序結果）。
- 貪婪演演算法

<image>

<image>

## 應用

- 全基因組組裝：組裝一個生物的基因組序列，可被應用於基因表現分析、個體間基因體差異比對、基因體層級的疾病研究等。
- RNA轉錄組組裝：從RNA測序並組裝，取得表現的基因的序列與表現量資料
- EST組裝

## 序列組裝程式

最早的序列組裝程式大約在1980至1990年代初期被發明。其雛形是序列比對分析的程式。隨著定序技術的進步以及被定序生物複雜度的增加（從小的病毒在質體至細菌和最後真核生物），序列組裝程式所採用的演演算法也越趨複雜。基本上，組裝程式都至少要能應付下面三大問題：

- 大量的原始數據：一次的高通量測序可能產出數百至上千GB 的測序資料。為了分析如此大量的資料，組裝程式通常都需要在超級電腦或電腦叢集上運作。
- 重複片段：完全相同的或非常類似的序列會造成組裝過程中的困難。我們難以判斷重複的次數，重複片段的切確位置，甚至可能將兩個原本不相連卻都帶有同樣重複片段的序列誤組在一起（mis-assembled）。
- 測序錯誤：測序錯誤可能產生自機器和技術本身的限制，而這樣的錯誤增加了序列比對的難度。

基因組組裝程式Celera 和Arachne 在2000年被研發出來——當時科學家試著組裝第一個較大型真核生物的基因組（果蠅），緊接著是隔年的人類基因組計畫。這兩個程式能處理約100至300億個鹼基對的基因組。隨後，更大更複雜的組裝程式也被發明，例如阿莫斯組裝程式（AMOS, A Modular Open-source Assembler）等。

下表列出了部分能夠進行 de-novo 組裝的程式。

程式名稱｜應用｜適用測序技術｜作者｜發表年份｜使用權限、｜連結

ABySS｜（大型）基因組｜Solexa, SOLiD, Illumina｜Simpson, J. et al.｜2008｜NC-A｜ link

ALLPATHS-LG｜（大型）基因組｜Solexa, SOLiD｜Gnerre, S. et al.｜2011｜OS｜ link

AMOS｜基因組｜Sanger, 454｜Salzberg, S. et al.｜2002?｜OS｜ link

Arapan-M｜（中型）基因組 （例. 大腸桿菌）｜均適用｜Sahli, M. & Shibuya, T.｜2011｜OS｜ link

Arapan-S｜（小型）基因組（例. 病毒）｜均適用｜Sahli, M. & Shibuya, T.｜2011｜OS｜ link

Celera WGA Assembler / CABOG｜（大型）基因組｜Sanger, 454, Solexa｜Myers, G. et al.; Miller G. et al.｜2004｜OS｜ link

CLC Genomics Workbench & CLC Assembly Cell｜基因組｜Sanger, 454, Solexa, SOLiD, Illumina｜CLC bio｜2008｜C｜ link

Cortex｜基因組｜Solexa, SOLiD｜Iqbal, Z. et al.｜2011｜OS｜ link

DBG2OLC｜（大型）基因組｜Illumina, PacBio, Oxford Nanopore｜Ye, C. et al｜2014｜OS｜ link

DNA Baser Assembler｜（小型）基因組｜Sanger, 454｜Heracle BioSoft SRL｜2017｜C｜www.DnaBaser.com

DNA Dragon｜基因組｜Illumina, SOLiD, Complete Genomics, 454, Sanger｜SequentiX｜2011｜C｜ link

DNAnexus｜基因組｜Illumina, SOLiD, Complete Genomics｜DNAnexus｜2011｜C｜ link

DNASTAR Lasergene Genomics Suite｜（大型）基因組, 外顯子組（exome）, 轉錄組（Transcriptome）, 元基因組（metagenome）, 表現序列標籤（ESTs）｜Illumina, ABI SOLiD, Roche 454, Ion Torrent, Solexa, Sanger｜DNASTAR｜2007｜C｜ link

Edena｜基因組｜Illumina｜D. Hernandez, P. François, L. Farinelli, M. Osteras, and J. Schrenzel.｜2008｜OS｜ link

Euler｜基因組｜Sanger, 454 （,Solexa ?）｜Pevzner, P. et al.｜2001｜（C / NC-A?）｜ link

Euler-sr｜基因組｜454, Solexa｜Chaisson, MJ. et al.｜2008｜NC-A｜ link

Fermi｜（大型）基因組｜Illumina｜Li, H.｜2012｜OS｜ link

Forge｜（大型）基因組, 表現序列標籤（ESTs）, 元基因組（metagenome）｜454, Solexa, SOLID, Sanger｜Platt, DM, Evers, D.｜2010｜OS｜ link

Geneious｜基因組｜Sanger, 454, Solexa, Ion Torrent, Complete Genomics, PacBio, Oxford Nanopore, Illumina｜Biomatters Ltd｜2009｜C｜ link

Graph Constructor｜（大型）基因組｜Sanger, 454, Solexa, SOLiD｜Convey Computer Corporation｜2011｜C｜ link

HINGE｜基因組｜PacBio/Oxford Nanopore｜Kamath, Shomorony, Xia et. al.｜2016｜OS｜ Software , Paper , Analyses

IDBA （Iterative De Bruijn graph short read Assembler）｜（大型）基因組｜Sanger,454,Solexa｜Yu Peng, Henry C. M. Leung, Siu-Ming Yiu, Francis Y. L. Chin｜2010｜（C / NC-A?）｜ link

LIGR Assembler （derived from TIGR Assembler）｜基因組｜Sanger｜2009｜OS｜ link

MaSuRCA （Maryland Super Read - Celera Assembler）｜（大型）基因組｜Sanger, Illumina, 454｜Aleksey Zimin, Guillaume Marçais, Daniela Puiu, Michael Roberts, Steven L. Salzberg, James A. Yorke｜2012｜OS｜ link

MIRA （Mimicking Intelligent Read Assembly）｜基因組, 表現序列標籤（ESTs）｜Sanger, 454, Solexa｜Chevreux, B.｜1998｜OS｜ link

NextGENe｜（小型）基因組｜454, Solexa, SOLiD｜Softgenetics｜2008｜C｜ link

Newbler｜基因組, 表現序列標籤（ESTs）｜454, Sanger｜454/Roche｜2004｜C｜ link

PADENA｜基因組｜454, Sanger｜454/Roche｜2010｜OS｜ link

PASHA｜（大型）基因組｜Illumina｜Liu, Schmidt, Maskell｜2011｜OS｜ link

Phrap｜基因組｜Sanger, 454, Solexa｜Green, P.｜1994｜C / NC-A｜ link

TIGR Assembler｜基因組｜Sanger｜1995｜OS｜ link

Trinity｜轉錄組（Transcriptome）｜Illumina, 454, Solid,...｜Grabher, MG et al.｜2011｜OS｜https://github.com/trinityrnaseq/trinityrnaseq/wiki

Ray｜基因組｜Illumina, mix of Illumina and 454, paired or not｜Sébastien Boisvert, François Laviolette & Jacques Corbeil.｜2010｜OS GNU General Public License｜ link

Sequencher｜基因組｜traditional and next generation sequence data｜Gene Codes Corporation｜1991｜C｜ link

SGA｜（大型）基因組｜Illumina, Sanger （Roche 454?, Ion Torrent?）｜Simpson, J.T. et al.｜2011｜OS｜ link

SHARCGS｜（大型）基因組｜Solexa｜Dohm et al.｜2007｜OS｜ link

SOPRA｜基因組｜Illumina, SOLiD, Sanger, 454｜Dayarian, A. et al.｜2010｜OS｜ link

SparseAssembler｜（大型）基因組｜Illumina, 454, Ion torrent｜Ye, C. et al.｜2012｜OS｜ link

SSAKE｜（小型）基因組｜Solexa （SOLiD? Helicos?）｜Warren, R. et al.｜2007｜OS｜ link

SOAPdenovo｜基因組｜Solexa, Illumina｜Luo, R. et al.｜2009｜OS｜ link

SPAdes｜（小型）基因組, 單細胞測序（single-cell sequencing）｜Illumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford Nanopore｜Bankevich, A et al.｜2012｜OS｜ link

Staden gap4 package｜細菌人工染色體定序（BACs）｜Sanger｜Staden et al.｜1991｜OS｜ link

Taipan｜（小型）基因組｜Illumina｜Schmidt, B. et al.｜2009｜OS｜ link

VCAKE｜（小型）基因組｜Solexa （SOLiD?, Helicos?）｜Jeck, W. et al.｜2007｜OS｜ link

Phusion assembler｜（大型）基因組｜Sanger｜Mullikin JC, et al.｜2003｜OS｜ link

Quality Value Guided SRA （QSRA）｜基因組｜Sanger, Solexa｜Bryant DW, et al.｜2009｜OS｜ link

Velvet｜（小型）基因組｜Sanger, 454, Solexa, SOLiD｜Zerbino, D. et al.｜2007｜OS｜ link

使用許可*：OS = 開放原始碼（免費）; C = 商業（付費）; C / NC-A = 商業使用需付費，但非商業使用與學術研究用免費; 括弧 = 不明但可能是 C / NC-A