SuperLLEC：New Assembly and Error Correction Algorithm for Long Reads and Linked-Reads

doi:10.3778/j.issn.1002-8331.2008-0204

Abstract

Abstract: In order to solve the high error rate of the third-generation sequencing data and improve the accuracy of genome assembly, an assembly and error correction algorithm, called SuperLLEC, is designed for the long-read data of the PacBio based on the 10X Genomics linked-read sequencing data. Wtdbg2 is employed to assemble the PacBio long reads of a genome into scaffolds. Bowtie2 is used to align each linked-read to these scaffolds, and further assemble these scaffolds based on the barcodes of linked-reads. Fisher’s exact test is used to predict whether each mismatched alignment site is a single nucleotide polymorphism（SNP） or an error base sequenced by PacBio. Algorithm comparison experiments on the long-read and linked-read data from three groups of human cells show that SuperLLEC can significantly improve the accuracy of genome assembly, increase NG50 length, and recover more SNPs.

Key words: linked-reads, long-reads, scaffolds, assembly, error correction, Fisher’s exact test

摘要： 为了解决第三代测序数据较高的错误率和提高基因组组装精度，基于10X Genomics链读测序数据设计了一种针对PacBio长读数据的组装和纠错算法SuperLLEC。该算法使用Wtdbg2算法将PacBio长读测序数据拼接成支架序列，运用Bowtie2比对工具将链读序列比对到支架序列，并根据链读条码进一步组装支架序列；对不匹配的比对位点采用Fisher精确检验预测该位点为单核酸多态性或是PacBio测序错误的碱基。通过三组人类细胞的长读数据和链读数据的算法比较实验，证明该方法能够较明显地提高基因组组装的准确度、NG50长度和单核酸多态性位点预测精度。

关键词: 链读, 长读, 支架, 组装, 纠错, Fisher精确检验

CUI Yaxuan, ZHANG Shaoqiang. SuperLLEC：New Assembly and Error Correction Algorithm for Long Reads and Linked-Reads[J]. Computer Engineering and Applications, 2022, 58(3): 201-206.

崔雅轩, 张少强. SuperLLEC：全新的链读和长读测序组装纠错算法[J]. 计算机工程与应用, 2022, 58(3): 201-206.

References

[1] SANGER F，NICKLEN S，COULSON A R.DNA sequencing with chain-terminating inhibitors[J].Proceedings of the National Academy of Sciences of the United States of America，1977，74（12）：5463-5467.
[2] MCGINN S，GUT I G.DNA sequencing-spanning the generations[J].New Biotechnology，2013，30（4）：366-372.
[3] SLATKO B E，GARDNER A F，AUSUBEL F M.Overview of next-generation sequencing technologies[J].Current Protocols in Molecular Biology，2018，122（1）：e59.
[4] RHOADS A，AU K F.PacBio sequencing and its applications[J].Genomics Proteomics Bioinformatics，2015，13（5）：278-289.
[5] LU H，GIORDANO F，NING Z.Oxford nanopore MinION sequencing and genome assembly[J].Genomics Proteomics Bioinformatics，2016，14（5）：265-279.
[6] SUZUKI Y.Informatics for PacBio long reads[J].Adva-nces in Experimental Medicine and Biology，2019，1129：119-129.
[7] 李艳慧，张少强.DNA测序技术及其拼接算法综述[J].天津师范大学学报，2018，38（5）：1-9.
LI Y H，ZHANG S Q.Overview of DNA sequencing techniques and corresponding assembly algorithms[J].Journal of Tianjin Normal University，2018，38（5）：1-9.
[8] AMARASINGHE S L，SU S，DONG X，et al.Opportunities and challenges in long-read sequencing data analysis[J].Genome Biology，2020，21（1）：30.
[9] RUAN J，LI H.Fast and accurate long-read assembly with Wtdbg2[J].Nature Methods，2020，17（2）：155-158.
[10] CHIN C S，PELUSO P，SEDLAZECK F J，et al.Phased diploid genome assembly with single-molecule real-time sequencing[J].Nature Methods，2016，13（12）：1050-1054.
[11] KOREN S，WALENZ B P，BERLIN K，et al.Canu：scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation[J].Genome Research，2017，27（5）：722-736.
[12] WANG A，AU K F.Performance difference of graph-based and alignment-based hybrid error correction methods for error-prone long reads[J].Genome Biology，2020，21（1）：14.
[13] BAO E，XIE F，SONG C，et al.FLAS：fast and high- throughput algorithm for PacBio long-read self-correction[J].Bioinformatics，2019，35（20）：3953-3960.
[14] SALMELA L，RIVALS E.LoRDEC：accurate and efficient long read error correction[J].Bioinformatics，2014，30（24）：3506-3514.
[15] HACKL T，HEDRICH R，SCHULTZ J，et al.Proovread：large-scale high-accuracy PacBio correction through iterative short read consensus[J].Bioinformatics，2014，30：3004-3011.
[16] HAGHSHENAS E，HACH F，SAHINALP S C，et al.CoLoRMap：correcting long reads by mapping short reads[J].Bioinformatics，2016，32：545-551.
[17] WANG J R，HOLT J，MCMILLAN L，et al.FMLRC：hybrid long read error correction using an FM-index[J].BMC Bioinformatics，2018，19：50.
[18] DAS A K，GOSWAMI S，LEE K，et al.A hybrid and scalable error correction algorithm for indel and substitution errors of long reads[J].BMC Genomics，2019，20（Suppl 11）：948.
[19] KOREN S，SCHATZ M C，WALENZ B P，et al.Hybrid error correction and de novo assembly of single-molecule sequencing reads[J].Natural Biotechnology，2012，30（7）：693-700.
[20] REDIN D，BORGSTR?M E，HE M，et al.Droplet barcode sequencing for targeted linked-read haplotyping of single DNA molecules[J].Nucleic Acids Research，2017，45（13）：e125.
[21] EID J.Real-time DNA sequencing from single polymerase molecules[J].Science，2009，323（5910）：133-138.
[22] LOGSDON G A，VOLLGER M R，EICHLER E E.Long-read human genome sequencing and its applications[J].Nature Reviews Genetics，2020，5：1-18.
[23] ALTSCHUL S F，MADDEN T L，SCH?FFER A A，et al.Gapped BLAST and PSI-BLAST：a new generation of protein database search programs[J].Nucleic Acids Research，1997，25（17）：3389-3402.
[24] LANGMEAD B，SALZBERG S L.Fast gapped-read alignment with Bowtie 2[J].Natural Methods，2012，9（4）：357-359.