A Study of Computational Genome Assembly by Graph Theory

[1] A. Bankevich, S. Nurk, D. Antipov, A. A. Gurevich, M. Dvorkin, A. S. Kulikov, V. M. Lesin, S. I. Nikolenko, S. Pham, A. D. Prjibelski, A. V. Pyshkin, A. V. Sirotkin, N. Vyahhi, G. Tesler, M. A. Alekseyev, P. A. Pevzner, SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing, Journal of Computational Biology 19 (5) (2012), 455-477. Search in Google Scholar

[2] K. Behizadi, N. Jafarzadeh, A. Iranmanesh, Graph theoretical strategies in de novo assembly, IEEE Access 10 (2022), 9328-9339. Search in Google Scholar

[3] J. Blazewicz, M. Kasprzak, M. Kierzynka, W. Frohmberg, A. Swiercz, P. Wojciechowski, P. Zurkowski, Graph algorithms for DNA sequencing–origins, current models and the future, European Journal of Operational Research 264 (3) (2018), 799-812. Search in Google Scholar

[4] P. E. Compeau, P. A. Pevzner, G. Tesler, How to apply de Bruijn graphs to genome assembly, Nature Biotechnology 29 (11) (2011), 987-991. Search in Google Scholar

[5] P. Compeau, P. A. Pevzner, Bioinformatics Algorithms: An Active Learning Approach, Active Learning Publishers, 2015. Search in Google Scholar

[6] S. Gladman, An introduction to genome assembly (galaxy training materials), 18-10 (2022), URL: https://training.galaxyproject.org/training-material/topics/assembly/tutorials/general-introduction/tutorial.html, Accessed: 2022-10-21. Search in Google Scholar

[7] R. M. Idury, M. S. Waterman, A new algorithm for DNA sequence assembly, Journal of Computational Biology 2 (2) (1995), 291-306. Search in Google Scholar

[8] D. Li, C.M. Liu, R. Luo, K. Sadakane, T. W. Lam, MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph, Bioinformatics 31 (10) (2015), 1674-1676. Search in Google Scholar

[9] R. Luo, B. Liu, Y. Xie, Z. Li, W. Huang, J. Yuan, G. He, Y. Chen, Q. Pan, Y. Liu and others, SOAPdenovo2: an empirically improved memory-e cient short-read de novo assembler, Gigascience 1 (1) (2012), 2047-217X. Search in Google Scholar

[10] Iu. P. Lysov, V. L. Florent’ev, A. A. Khorlin, K. R. Khrapko, V. V. Shik, Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. A new method, Dokl Akad Nauk SSSR 303 (6) (1988), 1508-1511. Search in Google Scholar

[11] P. Medvedev, S. Pham, M. Chaisson, G. Tesler, P. A. Pevzner, Paired de bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers, Journal of Computational Biology 18 (11) (2011), 1625-1634. Search in Google Scholar

[12] E. W. Myers, G. G. Sutton, A. L. Delcher, I. M. Dew, D. P. Fasulo, M. J. Flanigan, S. A. Kravitz, C. M. Mobarry, K. H. Reinert, K. A. Remington, E. L. Anson, R. A. Bolanos, H. H. Chou, C. M. Jordan, A. L. Halpern, S. Lonardi, E. M. Beasley, R. C. Brandon, L. Chen, P. J. Dunn, Z. Lai, Y. Liang, D. R. Nusskern, M. Zhan, Q. Zhang, X. Zheng, G. M. Rubin, M. D. Adams, J. C. Venter, A whole-genome assembly of drosophila, Science 287 (5461) (2000), 2196-2204. Search in Google Scholar

[13] E. W. Myers Jr, A history of DNA sequence assembly, IT - Information Technology 58 (3) (2016), 126-132, URL: https://doi.org/10.1515/itit-2015-0047, Accessed: 2022-10-17. Search in Google Scholar

[14] Y. Peng, H. Leung, S. M. Yiu, F. Y. Chin, IDBA–a practical iterative de Bruijn graph de novo assembler, Annual International Conference on Research in Computational Molecular Biology, Springer, 2010, 426-440. Search in Google Scholar

[15] P. A. Pevzner, 1-Tuple DNA sequencing: computer analysis, Journal of Biomolecular Structure and Dynamics 7 (1) (1989), 63-73. Search in Google Scholar

[16] P. A. Pevzner, H. Tang, M. S. Waterman, An Eulerian path approach to DNA fragment assembly, Proceedings of the National Academy of Sciences 98 (17) (2001), 9748-9753. Search in Google Scholar

[17] J. E. Quiroz-Ibarra, G. M. Mallén-Fullerton, G. Fernández-Anaya, DNA paired fragment assembly using graph theory, Algorithms 10 (2) (2017), 36. Search in Google Scholar

[18] M. Rocha, P. G. Ferreira, Bioinformatics Algorithms: Design and Implementation in Python, Academic Press, 2018. Search in Google Scholar

[19] F. Sanger, S. Nicklen, A. R. Coulson, DNA sequencing with chain-terminating inhibitors, Proceedings of the National Academy of Sciences 74 (1977), 5463-5467. Search in Google Scholar

[20] F. Sanger, A. R. Coulson, G. F. Hong, D. F. Hill, G. B. Petersen, Nucleotide sequence of bacteriophage DNA, Journal of Molecular Biology 162 (4) (1982), 729-773. Search in Google Scholar

[21] J. I. Sohn, J. W. Nam, The present and future of de novo whole-genome assembly, Briefings in Bioinformatics 19 (1) (2018), 23-40. Search in Google Scholar

[22] E. Southern, Analyzing polynucleotide sequences, International patent application PCT/GB89/00460 (1988). Search in Google Scholar

[23] B. Wajid, E. Serpedin, Review of general algorithmic features for genome assemblers for next generation sequencers, Genomics, Proteomics and Bioinformatics 10 (2) (2012), 58-73. Search in Google Scholar

[24] D. R. Zerbino, E. Birney, Velvet: algorithms for de novo short read assembly using de Bruijn graphs, Genome Research 18 (5) (2008), 821-829. Search in Google Scholar

[25] W. Zhang, J. Chen, Y. Yang, Y. Tang, J. Shang, B. Shen, A practical comparison of de novo genome assembly software tools for next-generation sequencing technologies, PloS One 6 (3) (2011), e17915. Search in Google Scholar

[26] Galaxy, URL: https://usegalaxy.org/, Accessed: 2022-10-21. Search in Google Scholar

[27] Zenodo, URL: https://zenodo.org/record/582600#.Y1NvKUpBxN5, Accessed: 2022-10-21. Search in Google Scholar

[28] Assembly using Spades, URL: https://www.melbournebioinformatics.org.au/tutorials/tutorials/assembly/spades/, Accessed: 2022-10-21. Search in Google Scholar