序列組裝

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

序列組裝最常被使用在高通量測序資料的分析上（例如基因組霰彈槍定序，或者RNA轉錄體測序）。這一類的測序技術會產生大量的測序片段（read，複數reads），而這些片段的長度依照不同的技術，短為數十，長可至上萬個鹼基對（前者如Illumina的定序平台，後者如太平洋生物科學公司（英語：Pacific Biosciences）的SMRT-測序（英語：Single molecule real time sequencing）或奈米孔洞測序）^[1]。而序列組裝旨在合併這些短片段來重建原本的分子序列。

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

重複片段(repeats)的問題：假設黑色序列是原來被測序分子，我們可難到這段序列中有兩次CGGAGAGG的重複。如果我們今天只能拿到較短的測序片段（上方，粉紅色），那麼我們會無法斷定CGGAGAGG這個序列來自分子的何處。相反的，較長的測序片段（下方，綠、紅、藍色）則可解決這個問題。

方法

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

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

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

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

• Overlap - Layout - Consensus（OLC）法：即文章前段所舉的例子。此演算法分為三個步驟（圖一）。首先找出測序片段中「重疊」的部分，接著「配置」出這些片段可能的順序，最後從這些片段中找出「保守」的序列，組裝得到原始序列。此方法雖然直觀，但其電腦演算量較大，故通常被使用在組裝資料量不大而測序長度較長的資料上（例如Pac-Bio的測序結果）^[3]。

• De-Bruijn（英語：De-Bruijn graph）（DBG）法：此方法使用數學圖論中De-Bruijn 圖（英語：De-Bruijn Graph）的概念，先將每個測序片段拆解成k-mer（英語：k-mer）（一個字串中所有長度為k的可能字串子集合）。接著從這些k-mer重疊的區段建構出De-Bruijn圖，再利用演算法解出De-Bruijn圖的結構並取得組裝結果（圖二）。此方法雖不如OLC法直觀，但在電腦演算需求上較OLC法小，故通常被用於資料量大而片段短的分析上（例如Illumina的測序結果）^[3]。

• 貪婪演算法

圖一．OLC法示意圖

圖二．DBG法示意圖

應用

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

序列組裝程式

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

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

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

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

程式名稱	應用	適用測序技術	作者	發表年份	使用權限*	連結
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 Archive.is的存檔，存檔日期2013-08-21
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.[9]	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.[10]	2011	OS	https://github.com/trinityrnaseq/trinityrnaseq/wiki （頁面存檔備份，存於網際網路檔案館）
Ray[11]	基因組	Illumina, mix of Illumina and 454, paired or not	Sébastien Boisvert, François Laviolette & Jacques Corbeil.	2010	OS [GNU General Public License]	link Portuguese Web Archive的存檔，存檔日期2016-05-23
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 美國國會圖書館的存檔，存檔日期2011-05-12
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

參考文獻

1. Mardis, ER. DNA sequencing technologies: 2006–2016. Nature Protocols. 2017, 12: 213–218 [2017-06-09]. doi:10.1038/nprot.2016.182. （原始內容存檔於2017-06-02）.
2. Miller, JR., Koren, S., Sutton, G. Assembly algorithms for next-generation sequencing data. Genomics. 2010, 95 (6): 315–327 [2017-06-09]. doi:10.1016/j.ygeno.2010.03.001. （原始內容存檔於2016-01-20）.
3. Ekblom, R., Wolf, J. A field guide to whole-genome sequencing, assembly and annotation. Evolutionary Applications. 2014, 7 (9): 1026–1042 [2017-06-09]. doi:10.1111/eva.12178. （原始內容存檔於2017-08-02）.
4. Sharman, A. The many uses of a genome sequence. Genome Biology. 2001, 2 (6): 4013.1–4013.4.
5. Myers, E. W.; Sutton, GG; Delcher, AL; Dew, IM; Fasulo, DP; Flanigan, MJ; Kravitz, SA; Mobarry, CM; et al. A whole-genome assembly of Drosophila. Science. March 2000, 287 (5461): 2196–204. Bibcode:2000Sci...287.2196M. PMID 10731133. doi:10.1126/science.287.5461.2196.
6. Batzoglou, S.; Jaffe, DB; Stanley, K; Butler, J; Gnerre, S; Mauceli, E; Berger, B; Mesirov, JP; Lander, ES. ARACHNE: a whole-genome shotgun assembler. Genome Research. January 2002, 12 (1): 177–89. PMC 155255 . PMID 11779843. doi:10.1101/gr.208902.
7. AMOS page （頁面存檔備份，存於網際網路檔案館） with links to various papers
8. list of software including mapping assemblers in the SeqAnswers discussion forum.. [2017-06-06]. （原始內容存檔於2017-07-14）.
9. Kamath, Govinda M.; Shomorony, Ilan; Xia, Fei; Courtade, Thomas; Tse, David N. HINGE: Long-Read Assembly Achieves Optimal Repeat Resolution. Genome Research. 1 August 2016: gr.216465.116. doi:10.1101/gr.216465.116.
10. Grabherr, Manfred G.; Haas, Brian J.; Yassour, Moran; Levin, Joshua Z.; Thompson, Dawn A.; Amit, Ido; Adiconis, Xian; Fan, Lin; Raychowdhury, Raktima. Full-length transcriptome assembly from RNA-Seq data without a reference genome. Nature Biotechnology. 2011-07-01, 29 (7): 644–652 [2017-06-06]. ISSN 1087-0156. PMC 3571712 . PMID 21572440. doi:10.1038/nbt.1883. （原始內容存檔於2016-10-31） （英語）.
11. Boisvert, Sébastien; Laviolette, François; Corbeil, Jacques. Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies. Journal of Computational Biology. October 2010, 17 (11): 1519–33. PMC 3119603 . PMID 20958248. doi:10.1089/cmb.2009.0238.