序列组装
序列组装(Sequence assembly)是生物资讯学中的一种分析方法。此方法通过序列比对和序列合并等演算,将短片段的DNA建构成为较长的连续序列。此技术的创立,是因为被测序的核酸分子通常长度都远大于目前存在的DNA测序技术。而此分析能试图从有限长度的DNA测序结果,重建出原本被测序分子的样貌。
序列组装最常被使用在高通量测序资料的分析上(例如基因组霰弹枪定序,或者RNA转录体测序)。这一类的测序技术会产生大量的测序片段(read,复数reads),而这些片段的长度依照不同的技术,短为数十,长可至上万个碱基对(前者如Illumina的定序平台,后者如太平洋生物科学公司的SMRT-测序或奈米孔洞测序)[1]。而序列组装旨在合并这些短片段来重建原本的分子序列。
我们可将序列组装想像成从大量片段的文字中拼凑出一整篇文章的过程:被测序的分子就是那篇文章,而测序片段就是那段文章中,随机切取出来的句子。其中一种重建出这段文章的方式,就是找到句子中重叠的部分,因为一旦找到够多重叠的部分,我们就有机会将每个句子连接到一起,进而得到原始的文章。不难想像,此过程的困难不仅仅在于需要进行大量的片段比对,还会因原本文章的复杂度而制造更多问题:例如原本的文章可能有许多重复的段落,而带有这些重复段落的文句可能会重叠在一起;又或者我们所拿到的句子中若有错别字,亦会增加寻找重叠片段的难度。同样的问题也同样存在于生物资讯的序列组装分析里。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/d/dd/Seqassemble.png/450px-Seqassemble.png)
方法
依照参考序列的有无,序列组装可分为[2]:
- De-novo 组装(拉丁语:de novo意指“新的”):在没有参考序列的情况下,仅使用序列片段所提供的资讯来组装的方法。
- Mapping 组装:在有参考序列的情况下,将测序片段比对至参考序列上,以取得组装结果。
- 引导式组装(guided assembly):介于de-novo组装与mapping组装之间 ——在有参考序列的情况下,以其作为引导,并结合使用序列片段本身的资讯进行组装。
举例来说,在进行全基因组测序分析时,de-novo组装可能被使用在非模式物种基因组的分析上,因为其没有临进物种的基因组提供参考。相反的,如果有有邻近或相同物种的基因组可做参考,则可使用mapping组装或引导式组装(genome guided assembly)。
De-novo 组装又可分为三种算法:
- Overlap - Layout - Consensus(OLC)法:即文章前段所举的例子。此算法分为三个步骤(图一)。首先找出测序片段中“重叠”的部分,接着“配置”出这些片段可能的顺序,最后从这些片段中找出“保守”的序列,组装得到原始序列。此方法虽然直观,但其电脑演算量较大,故通常被使用在组装资料量不大而测序长度较长的资料上(例如Pac-Bio的测序结果)[3]。
- De-Bruijn(DBG)法:此方法使用数学图论中De-Bruijn 图的概念,先将每个测序片段拆解成k-mer(一个字串中所有长度为k的可能字串子集合)。接着从这些k-mer重叠的区段建构出De-Bruijn图,再利用算法解出De-Bruijn图的结构并取得组装结果(图二)。此方法虽不如OLC法直观,但在电脑演算需求上较OLC法小,故通常被用于资料量大而片段短的分析上(例如Illumina的测序结果)[3]。
应用
序列组装程式
最早的序列组装程式大约在1980至1990年代初期被发明。其雏形是序列比对分析的程式。随着定序技术的进步以及被定序生物复杂度的增加(从小的病毒在质体至细菌和最后真核生物),序列组装程式所采用的算法也越趋复杂。基本上,组装程式都至少要能应付下面三大问题:
- 大量的原始数据:一次的高通量测序可能产出数百至上千GB 的测序资料。为了分析如此大量的资料,组装程式通常都需要在超级电脑或电脑丛集上运作。
- 重复片段:完全相同的或非常类似的序列会造成组装过程中的困难。我们难以判断重复的次数,重复片段的切确位置,甚至可能将两个原本不相连却都带有同样重复片段的序列误组在一起(mis-assembled)。
- 测序错误:测序错误可能产生自机器和技术本身的限制,而这样的错误增加了序列比对的难度。
基因组组装程式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 |
参考文献
- ^ 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).
- ^ 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.0 3.1 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).
- ^ Sharman, A. The many uses of a genome sequence. Genome Biology. 2001, 2 (6): 4013.1–4013.4.
- ^ 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.
- ^ 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.
- ^ AMOS page (页面存档备份,存于互联网档案馆) with links to various papers
- ^ list of software including mapping assemblers in the SeqAnswers discussion forum.. [2017-06-06]. (原始内容存档于2017-07-14).
- ^ 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.
- ^ 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) (英语).
- ^ 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.