序列组装

序列组装（Sequence assembly）是生物资讯学中的一种分析方法。此方法通过序列比对和序列合并等演算，将短片段的DNA建构成为较长的连续序列。此技术的创立，是因为被测序的核酸分子通常长度都远大于目前存在的DNA测序技术。而此分析能试图从有限长度的DNA测序结果，重建出原本被测序分子的样貌。

序列组装最常被使用在高通量测序资料的分析上（例如基因组霰弹枪定序，或者RNA转录体测序）。这一类的测序技术会产生大量的测序片段（read，复数reads），而这些片段的长度依照不同的技术，短为数十，长可至上万个碱基对（前者如因美纳（Illumina）的定序平台，后者如PacBio的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.today的存档，存档日期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