The de Bruijn Graph algorithm (DBG) as one of the cornerstones algorithms in short read assembly has extended with the rapid advancement of the Next Generation Sequencing (NGS) technologies and low-cost production of millions of high-quality short reads. Erroneous reads, non-uniform coverage, and genomic repeats are three major problems that influence the performance of short read assemblers. To encounter these problems, the iterative DBG algorithm applies multiple $k$ -mers instead of a single $k$ -mer, by iterating the DBG graph over a range of $k$ -mer sizes from the minimum to the maximum. However, the iteration paradigm of iterative DBG deals with complex graphs from the beginning of the algorithm and therefore, causes more potential errors and computational time for resolving various unreal branches. In this research, we propose the Reverse Modified Iterative DBG graph (named RMI-DBG) for short read assembly. RMI-DBG utilizes the DBG algorithm and String graph to achieve the advantages of both algorithms. We present that RMI-DBG performs faster with comparable results in comparison to iterative DBG. Additionally, the quality of the proposed algorithm in terms of continuity and accuracy is evaluated with some commonly-used assemblers via several real datasets of the GAGE-B benchmark.

Keywords:

References

1. Forouzan E, Maleki MSM, Karkhane AA, Yakhchali B, Evaluation of nine popular de novo assemblers in microbial genome assembly, J Microbiol Meth 143(October): 32–37, 2017, https://doi.org/10.1016/j.mimet.2017.09.008. Crossref, Medline, Google Scholar
2. Li Z, Chen Y, Mu D, Yuan J, Shi Y, Zhang H, Gan J, Li N, Hu X, Liu B, Yang B, Fan W, Comparison of the two major classes of assembly algorithms: Overlap-layout-consensus and de-Bruijn-graph, Brief Funct Genomics, 11(1): 25–37, 2012, https://doi.org/10.1093/bfgp/elr035. Crossref, Medline, Google Scholar
3. Miller JR, Koren S, Sutton G, Assembly algorithms for next-generation sequencing data, Genomics, 95(6): 315–327, 2010, https://doi.org/10.1016/j.ygeno.2010.03.001. Crossref, Medline, Google Scholar
4. Marijon P, Chikhi R, Varré J-S, Graph analysis of fragmented long-read bacterial genome assemblies, Bioinformatics, 35(21): 4239–4246 , 2019, https://doi.org/10.1093/bioinformatics/btz219. Crossref, Medline, Google Scholar
5. Huang YT, Liao CF, Integration of string and de Bruijn graphs for genome assembly, Bioinformatics, 32(9): 1301–1307, 2016, https://doi.org/10.1093/bioinformatics/btw011. Crossref, Medline, Google Scholar
6. Rizzi R, Beretta S, Patterson M, Pirola Y, Previtali M, Della Vedova G, Bonizzoni P, Overlap graphs and de Bruijn graphs: Data structures for de novo genome assembly in the big data era, Quant. Biol. 7(4): 278–292, 2019, https://doi.org/10.1007/s40484-019-0181-x. Crossref, Google Scholar
7. Gonnella G, Kurtz S, Readjoiner: A fast and memory efficient string graph-based sequence assembler, BMC Bioinform. 13(1): 82, 2012, https://doi.org/10.1186/1471-2105-13-82. Crossref, Medline, Google Scholar
8. Rahman MM, Sharker R, Biswas S, Rahman MS, HaVec: An efficient de Bruijn graph construction algorithm for genome assembly, Int. J. Genomics 2017: 6120980, 2017, https://doi.org/10.1155/2017/6120980. Medline, Google Scholar
9. Zerbino DR, Birney E, Velvet: Algorithms for de novo short read assembly using de Bruijn graphs, Genome Res. 18(5): 821–829, 2008, https://doi.org/10.1101/gr.074492.107. Crossref, Medline, Google Scholar
10. Butler J, MacCallum I, Kleber M, Shlyakhter IA, Belmonte MK, Lander ES, Nusbaum C, Jaffe DB, ALLPATHS: De novo assembly of whole-genome shotgun microreads, Genome Res. 18(5): 810–820, 2008, https://doi.org/10.1101/gr.7337908. Crossref, Medline, Google Scholar
11. Simpson JT, Wong K, Jackman SD, Schein JE, Jones SJM, Birol I, ABySS: A parallel assembler for short read sequence data, Genome Res. 19(6): 1117–1123, 2009, https://doi.org/10.1101/gr.089532.108. Crossref, Medline, Google Scholar
12. Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z, Li Y, Li S, Shan G, Kristiansen K, Li S, Yang H, Wang J, Wang J, De novo assembly of human genomes with massively parallel short read sequencing, Genome Res 20(2): 265–272, 2010, https://doi.org/10.1101/gr.097261.109. Crossref, Medline, Google Scholar
13. Luo R, Liu B, Xie Y, Li Z, Huang W, Yuan J, He G, Chen Y, Pan Q, Liu Y, Tang J, Wu G, Zhang H, Shi Y, Liu Y, Yu C, Wang B, Lu Y, Han C, Cheung DW, Yiu SM, Peng S, Xiaoqian Z, Liu G, Liao X, Li Y, Yang H, Wang J, Lam TW, Wang J, Erratum to SOAPdenovo2: An empirically improved memory-efficient short-read de novo assembler [GigaScience, (2012), 1, 18], Gigascience 4(1) :1, 2015, https://doi.org/10.1186/s13742-015-0069-2. Crossref, Medline, Google Scholar
14. Boisvert S, Laviolette F, Corbeil JR, Simultaneous assembly of reads from a mix of high-throughput sequencing technologies, J. Comput. Biol. 17(11) :1401–1415, 2010, https://doi.org/10.1089/cmb.2009.0238. Crossref, Google Scholar
15. Zimin AV, Marçais G, Puiu D, Roberts M, Salzberg SL, Yorke JA, The MaSuRCA genome assembler, Bioinformatics 29(21): 2669–2677, 2013, https://doi.org/10.1093/bioinformatics/btt476. Crossref, Medline, Google Scholar
16. Zimin AV, Puiu D, Luo MC, Zhu T, Koren S, Marçais G, Yorke JA, Dvořák J, Salzberg SL, Hybrid assembly of the large and highly repetitive genome of Aegilops Tauschii, a progenitor of bread wheat, with the MaSuRCA Mega-Reads algorithm, Genome Res 27(5): 787–792, 2017, https://doi.org/10.1101/gr.213405.116. Crossref, Medline, Google Scholar
17. Peng Y, Leung HCM, Yiu SM, Chin FYL, IDBA – A practical iterative De Bruijn graph de novo assembler, Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics) 6044 LNBI :426–440, 2010, https://doi.org/10.1007/978-3-642-12683-3_28. Google Scholar
18. Chin FYL, Leung HCM, Yiu SM, Sequence assembly using next generation sequencing data—challenges and solutions, Sci. China Life Sci. 57(11): 1140–1148, 2014, https://doi.org/10.1007/s11427-014-4752-9. Crossref, Medline, Google Scholar
19. Peng Y, Leung HCM, Yiu SM, Chin FYL, IDBA-UD: A de Novo assembler for single-cell and metagenomic sequencing data with highly uneven depth, Bioinformatics 28(11): 1420–1428, 2012, https://doi.org/10.1093/bioinformatics/bts174. Crossref, Medline, Google Scholar
20. Bankevich A, Nurk S, Antipov D, Gurevich AA, Dvorkin M, Kulikov AS, Lesin VM, Nikolenko SI, Pham S, Prjibelski AD, Pyshkin AV, Sirotkin AV, Vyahhi N, Tesler G, Alekseyev MA, Pevzner PA, SPAdes: A new genome assembly algorithm and its applications to single-cell sequencing, J. Comput. Biol. 19(5): 455–477, 2012, https://doi.org/10.1089/cmb.2012.0021. Crossref, Medline, Google Scholar
21. Li D, Luo R, Liu CM, Leung CM, Ting HF, Sadakane K, Yamashita H, Lam TW, MEGAHIT v1.0: A fast and scalable metagenome assembler driven by advanced methodologies and community practices, Methods, 102: 3–11, 2016, https://doi.org/10.1016/j.ymeth.2016.02.020. Crossref, Medline, Google Scholar
22. Mahadik K, Wright C, Kulkarni M, Bagchi S, Chaterji S, Scalable genome assembly through parallel de Bruijn graph construction for multiple K-Mers, Sci. Rep. 9(1): 1–15, 2019, https://doi.org/10.1038/s41598-019-51284-9. Crossref, Medline, Google Scholar
23. Lin Y, Pevzner PA, Manifold de Bruijn graphs, Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics) 8701 LNBI: 296–310, 2014, https://doi.org/10.1007/978-3-662-44753-6_22. Google Scholar
24. Boucher C, Bowe A, Gagie T, Puglisi SJ, Sadakane K, Variable-order de Bruijn graphs, Data Compress. Conf. Proc. 2015( July): 383–392, 2015, https://doi.org/10.1109/DCC.2015.70. Google Scholar
25. Cazaux B, Sacomoto G, Rivals E, Superstring graph: A new approach for genome assembly, Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics) 9778 :39–52, 2016, https://doi.org/10.1007/978-3-319-41168-24. Google Scholar
26. Das AK, Koppa PK, Goswami S, Platania R, Park SJ, Large-scale parallel genome assembler over cloud computing environment, J. Bioinform. Comput. Biol. 15(3) :1–21, 2017, https://doi.org/10.1142/S0219720017400030. Link, Google Scholar
27. Magoc T, Pabinger S, Canzar S, Liu X, Su Q, Puiu D, Tallon LJ, Salzberg SL, GAGE-B: An evaluation of genome assemblers for bacterial organisms, Bioinformatics 29(14) :1718–1725, 2013, https://doi.org/10.1093/bioinformatics/btt273. Crossref, Medline, Google Scholar
28. Forouzan E, Shariati P, Mousavi Maleki MS, Karkhane AA, Yakhchali B, Practical evaluation of 11 de novo assemblers in metagenome assembly, J Microbiol Meth 151 :99–105, 2018, https://doi.org/10.1016/j.mimet.2018.06.007. Crossref, Medline, Google Scholar
29. Heydari M, Miclotte G, Demeester P, Van de Peer Y, Fostier J, Evaluation of the impact of illumina error correction tools on de novo genome assembly, BMC Bioinform 18(1) :1–13, 2017, https://doi.org/10.1186/s12859-017-1784-8. Crossref, Medline, Google Scholar
30. Allam A, Kalnis P, Solovyev V, Karect: Accurate correction of substitution, insertion and deletion errors for next-generation sequencing data, Bioinformatics 31(21): 3421–3428, 2015, https://doi.org/10.1093/bioinformatics/btv415. Crossref, Medline, Google Scholar
31. Chitsaz H, Yee-Greenbaum JL, Tesler G, Lombardo MJ, Dupont CL, Badger JH, Novotny M, Rusch DB, Fraser LJ, Gormley NA, Schulz-Trieglaff O, Smith GP, Evers DJ, Pevzner PA, Lasken RS, Efficient de novo assembly of single-cell bacterial genomes from short-read data sets, Nat Biotechnol 29(10) :915–922, 2011, https://doi.org/10.1038/nbt.1966. Crossref, Medline, Google Scholar
32. Marçais G, Delcher AL, Phillippy AM, Coston R, Salzberg SL, Zimin A, MUMmer4: A fast and versatile genome alignment system, PLoS Comput Biol 14(1) :1–14, 2018, https://doi.org/10.1371/journal.pcbi.1005944. Crossref, Google Scholar
33. Simpson JT, Durbin R, Efficient de novo assembly of large genomes using compressed data structures, Genome Res 22(3): 549–556, 2012, https://doi.org/10.1101/gr.126953.111. Crossref, Medline, Google Scholar
34. Li H, Durbin R, Fast and accurate short read alignment with burrows-wheeler transform, Bioinformatics 25(14): 1754–1760, 2009, https://doi.org/10.1093/bioinformatics/btp324. Crossref, Medline, Google Scholar
35. Bushnell, B. (2014). BBMap: A Fast, Accurate, Splice-Aware Aligner. Lawrence Berkeley National Laboratory. LBNL Report #: LBNL-7065E. Retrieved from https://escholarship.org/uc/item/1h3515gn. Google Scholar
36. Boetzer M, Henkel CV, Jansen HJ, Butler D, Pirovano W, Scaffolding pre-assembled contigs using SSPACE, Bioinformatics 27(4): 578–579, 2011, https://doi.org/10.1093/bioinformatics/btq683. Crossref, Medline, Google Scholar
37. Gurevich A, Saveliev V, Vyahhi N, Tesler G, QUAST: Quality assessment tool for genome assemblies, Bioinformatics, 29(8): 1072–1075, 2013, https://doi.org/10.1093/bioinformatics/btt086. Crossref, Medline, Google Scholar
38. Fourment M, Gillings MR, A comparison of common programming languages used in bioinformatics, BMC Bioinform 9: 1–9, 2008, https://doi.org/10.1186/1471-2105-9-82. Crossref, Medline, Google Scholar
39. Abu-Doleh A, Catalyurek UV, Spaler: Spark and GraphX based de novo genome assembler, Proc 2015 IEEE Int Conf Big Data, IEEE Big Data 2015, pp. 1013–1018, 2015, https://doi.org/10.1109/BigData.2015.7363853. Crossref, Google Scholar
40. Yan D, Chen H, Cheng J, Cai Z, Shao B, Scalable de novo genome assembly using pregel, Proc IEEE 34th Int Conf Data Eng ICDE 2018, pp. 1220–1223, 2018, https://doi.org/10.1109/ICDE.2018.00114. Crossref, Google Scholar
41. Guo G, Chen H, Yan D, Cheng J, Chen J, Chong Z, Scalable de novo genome assembly using a pregel-like graph-parallel system, IEEE/ACM Trans. Comput. Biol. Bioinform. PP(c): 1–1, 2019, https://doi.org/10.1109/tcbb.2019.2920912. Crossref, Google Scholar