序列組裝
序列組裝（Sequence assembly）是生物資訊學中的一種分析方法。此方法通過序列比對和序列合併等演算，將短片段的DNA建構成為較長的連續序列。此技術的創立，是因為被測序的核酸分子通常長度都遠大於目前存在的DNA測序技術。而此分析能試圖從有限長度的DNA測序結果，重建出原本被測序分子的樣貌。
序列組裝最常被使用在高通量測序資料的分析上（例如基因組霰彈槍定序，或者RNA轉錄體測序）。這一類的測序技術會產生大量的測序片段（read，複數reads），而這些片段的長度依照不同的技術，短為數十，長可至上萬個鹼基對（前者如Illumina的定序平台，後者如太平洋生物科學公司的SMRT-測序或奈米孔洞測序）[1]。而序列組裝旨在合併這些短片段來重建原本的分子序列。
我們可將序列組裝想像成從大量片段的文字中拼湊出一整篇文章的過程：被測序的分子就是那篇文章，而測序片段就是那段文章中，隨機切取出來的句子。其中一種重建出這段文章的方式，就是找到句子中重疊的部分，因為一旦找到夠多重疊的部分，我們就有機會將每個句子連接到一起，進而得到原始的文章。不難想像，此過程的困難不僅僅在於需要進行大量的片段比對，還會因原本文章的複雜度而製造更多問題：例如原本的文章可能有許多重復的段落，而帶有這些重複段落的文句可能會重疊在一起；又或者我們所拿到的句子中若有錯別字，亦會增加尋找重疊片段的難度。同樣的問題也同樣存在於生物資訊的序列組裝分析裏。
方法
依照參考序列的有無，序列組裝可分為[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.
