序列組裝

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

序列組裝最常被使用在高通量測序資料的分析上(例如基因組霰彈槍定序,或者RNA轉錄體測序)。這一類的測序技術會產生大量的測序片段(read,複數reads),而這些片段的長度依照不同的技術,短為數十,長可至上萬個鹼基對(前者如Illumina的定序平台,後者如太平洋生物科學公司英語Pacific BiosciencesSMRT-測序英語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. ^ 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). 
  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.