原文為《Sparc： a sparsitybased consensus algorithm for long erroneous sequencing reads》，鑒于PeerJ期刊2016年6月8日（影響因子為2.183，投稿命中率為52.22%，在各類SCI期刊中屬于比較普通的水準）
摘要：
Sparc軟體通過高效的線性複雜度一緻性算法，将目标基因組區域的序列建構k聚體圖，幫助基因組的從頭組裝。權重最大的路徑最近似于基因組真實序列，通過稀疏分解誘導的算法對序列圖譜不斷重新調整權重，進而得到一緻性序列。Sparc 能夠支援同時使用NGS和3GS資料，極大改善成本和計算方法有效性。
使用測序深度為30× 的PacBio 資料，Sparc能夠達到錯誤率低于0.5%；使用更具有挑戰性的OxfordNanopore 資料，Sparc能夠達到和NGS資料相似的錯誤率。與現行方法相比，Sparc對于一緻序列的計算更加準确，并且節省80%的記憶體和時間。
前言：
與前面幾代測序技術相比，三代測序技術在每個片段能夠提供5-120kb的讀長。然而，根據2012年和2015年兩篇文獻的介紹，Pac Bio測序錯誤率大約為15%（2012年），OxfordNanopore 測序的錯誤率高達40%（2015年），高的測序錯誤率為使用3GS測序進行基因組拼接提出了很大的挑戰。
使用三代測序資料進行基因組的從頭組裝，主要需克服三個瓶頸：1）找到重複序列；2）序列對比；3）序列優化/序列糾錯。高效地糾正這些長錯誤序列是個重大的難題，下圖顯示這三個主要挑戰，其中最後一步是這篇文獻的主要解決的問題：
一緻性算法對于基因組拼接非常關鍵，有以下幾個原因：1）一緻性算法是彙程式設計式産生高品質輸出結果的必要部分。2）糾錯程式提高了輸入序列的準确 度。每個組裝重疊序列（或者稱為主幹序列-backbone）作為靶序列，每次測序結果作為查詢序列（query sequences）與靶序列對比。另一種情形，每個長錯誤測序結果作為靶序列，NGS或者3GS序列作為查詢序列；通過同時使用NGS資料和3GS資料，即混合組裝方法，是廣泛采用的組裝方法。由于NGS短序列的成本更低、準确率更高，是以将兩種資料結合可以降低成本，并且緩解整個管線的計算壓力。3）最後一個步驟占用了大部分的計算時間，是以，高效的一緻性算法極大地加速了基因組組裝過程。
我們借助了着名的de Bruijn/k聚體圖，針對3GS資料設計了一種更簡便的方 法。在我們的sparc算法中，每個節點是一個k聚體，為節省記憶體，同一位置的k聚體進行合并，k聚體之間的連接配接的得分代表連接配接的可靠性，是以，最終得分 最高的路徑是最近似于一緻序列。Sparc可以在低記憶體的條件下提供極好的結果，而不用使用其他作圖簡化技術。由于技術的簡便性，此算法相比較主流的 3GS測序項目PBdagcon，速度加快五倍，記憶體也節省五倍。此外，由于主流NGS測序資料的準确性（>99%）更高，是以利用成本更低的NGS代替部分高成本的3GS資料是值得的，在混合情形下，Sparc能夠提供高品質的結果。
實驗方法：
1、搭建原始圖
首先搭建一個原始的k聚體圖，稱為backbone（骨 架），即靶序列，k聚體是位置特異的，不同的位置互相獨立。将k聚體配置設定到每個位置占用大量記憶體，特别是在下一個實驗步驟。為了節省記憶體，我們建構一個稀疏k聚體圖，在每g個堿基存儲一個k聚體，進而減少高達1/g的記憶體消耗。同時我們記錄k聚體節點之間的連接配接，連接配接的得分代表相應路徑的置信度。在原始圖 中，連接配接的多樣性是1，是以連接配接的得分是1。
2、與靶序列對比，建立全景圖
（i） 如果查詢序列顯示新的路徑，我們建立一個 分支，配置設定新的k聚體節點和連接配接。如下圖3b中顯示，當我們将Seq1的最後六個堿基與靶序列對照時，兩個新的連接配接ACC和AAA 的複雜性是1，配置設定一 個k聚體節點。（ii） 如果查詢序列和現有序列完美契合，我們不配置設定新的節點，而是增加連接配接的得分，我們也可以從下圖3b中看出，當我們對照Seq1序 列的前五個堿基時，節點AC， GG和連接配接 TGG 和原靶序列重合，并且連接配接得分增加1分。當我們和現有圖對照Seq2的最後六個堿基時，節點和連接配接與 Seq1重合，連接配接得分增加1分。這個構圖過程和de Bruijn做圖方法相似，但是我們區分了節點以及他們的位置。
3、調整圖的權重得分通 過上一步驟，得分最高的路徑具有最高的置信度，也就是最接近于真實的序列。然而，直接使用這個結果可能導緻錯誤，一個簡單的例子是長的插入錯誤，為了避免這種情況的發生，我們将連接配接得分減去一部分，減去的這部分取決于覆寫率。同時引入參數b增加可靠連接配接的權重（b=5~10）。
4、輸出結果
實驗結果：
Sparc已經在多種資料集上進行了測試，我們的實驗是基于對PacBio資料集和OxfordNanopore資料集的測試。Sparc是一個堿基水準的一緻性算 法，公平起見，我們用我們的程式和最相似的項目PBdagcon（主要用在HGAP和MHAP管線用來糾正序列）做了對比。
兩個程式都輸入一樣的資料，得到組裝骨架和用DBG2OLC收集每一個骨架有關聯的序列。Blasr用來序列對比，最後的一緻錯誤率通過MUMmer3裡的ednadiff方程來計算。所有的實驗都在一個用AMD Opteron2425HE CPUs的工作站（800MHz）。在一些實驗中，我們提供二代和三代測序資料，在這些混合的組合中，50XIllumina彙編重疊群也包含在内，邊界權重增長b=5~10。測序深度為 50X的Illumina提供中等的覆寫度進而允許現成的基于deBruijn圖譜的彙程式設計式來彙編高品質重疊群。
在PacBio資料集，我們設定k=1，g=1，并運作一緻算法四輪。每一個堿基的錯誤率在1/2/4輪次後在表1和2中分别報告為ERR1，ERR2和ERR4。在第一個實驗中，我們使用大腸杆菌PacBio資料集和用不同的覆寫度測試其準确性。DBG2OLC用10X/30X的測序深度得到的最長骨架分别是1.3Mb和4.6Mb。 一個重要的彙編情境就是當我們既有二代又有三代測序資料時，我們發現Sparc可以實作混合彙編，而且使它們都有很高的計算效率和很好的成本效率。兩輪之後，Sparc在混合資料處理方面隻用10X的測序深度就可以達到0.09%的錯誤率，相比PBdagcon的0.64%的錯誤率是一個明顯的飛躍。當用30X的測序深度時，結果正如預期一樣更好（0.02%）。算法運作兩輪以上結果将更加改善，表1和表2中有其各自運作兩輪的時間。
Sparc對大量資料的測序表現更好，我們展示了Sparc和PBdagcon在一個更大的20X的PacBio A.thaliana 資料集 （基因組大小：120 Mbp）。DBG2OLC得到的最長骨架是7.1Mbp。Sparc跑完用了PBdagcon五分之一的時間和記憶體，但卻産生了更精确的結果。這裡我們用一個由MHAP得到的純PacBio全基因用作參考系來計算錯誤率。
在Oxford Nanopore資料集中，考慮到較高的誤碼率我們設定k=2，g=2，運作一緻算法四輪。每一個堿基的錯誤率在1/2/4輪次後在表3中被報告為ERR1/2/4。第一、二行為僅使用Oxford Nanopore（ON）的資料，第三、四行為使用混合資料的結果。
即使原始錯碼率可能高達40％，我們程式的測試錯碼率都低于0.5%。與此相反，非混合資料得到的結果則不那麼有用。在本次測試中最長的骨架是4.6 MBP。兩個程式運作四輪的時間報告在表3中。
Sparc對不同參數相對不是很敏感，是以即使對初用者來說也很容易使用。我們在第二輪變換了參數，隻用PacBio資料。表4中報告了不同k、g相對應的記憶體、時間和結果品質。使用稍大尺寸的k聚體會增加每個堿基測序的準确性，這個效應對多倍基因組更明顯。但是，這也增加了記憶體的使用，因為支鍊節點也相應産生。設定一個大一點的g可以幫助我們減少記憶體的消耗，不同的權重增加的對二代測序資料在混合一緻資料中的影響可以在表5中得見。經驗得出，在不影響準确性的前提下，這個參數被設定為b=5~15比較安全。實踐中，我們将它設為一個比較低的值（b=5~10），進而更好地使用三代測序資料。
實驗結論：
一緻模型是一個重疊-布局-一緻彙程式設計式架構的關鍵組成部分。随着三代測序技術的引入，它的重要性在進一步提高。在這項工作中，我們驗證了一個簡單但是高效的一緻算法：使用k聚體作為基礎子產品和從位點特異的k聚體圖譜可以産出高品質一緻序列，它支援混合測序這一點使得成本效率和計算效率大大提高。該方法可望顯着擴大其在測序糾錯和變異發現方面的應用。一緻測序品質也可以通過平台特異性、信号資訊的整合進一步得到提高。