序列组装

序列组装（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