Skip to content
naulon
Get started

No retraction, correction or concern found when last checked on Nov 1, 2026.

Scaffolding of long read assemblies using long range contact information

Jay Ghurye, Mihai Pop, Sergey Koren and 2 more

BMC Genomics · 2017 · CC BY

doi:10.1186/s12864-017-3879-z

Abstract

Background. Long read technologies have revolutionized de novo genome assembly by generating contigs orders of magnitude longer than that of short read assemblies. Although assembly contiguity has increased, it usually does not reconstruct a full chromosome or an arm of the chromosome, resulting in an unfinished chromosome level assembly. To increase the contiguity of the assembly to the chromosome level, different strategies are used which exploit long range contact information between chromosomes in the genome.

Methods. We develop a scalable and computationally efficient scaffolding method that can boost the assembly contiguity to a large extent using genome-wide chromatin interaction data such as Hi-C.

Results. we demonstrate an algorithm that uses Hi-C data for longer-range scaffolding of de novo long read genome assemblies. We tested our methods on the human and goat genome assemblies. We compare our scaffolds with the scaffolds generated by LACHESIS based on various metrics.

Conclusion. Our new algorithm SALSA produces more accurate scaffolds compared to the existing state of the art method LACHESIS.

Electronic supplementary material. The online version of this article (doi:10.1186/s12864-017-3879-z) contains supplementary material, which is available to authorized users.

References 44

  1. 1.

    Nagarajan N, Pop M. Parametric complexity of sequence assembly: theory and applications to next generation sequencing. J Comput Biol. 2009;16(7):897-908.

    Not in our library10.1089/cmb.2009.0005

  2. 2.

    Bresler G, Bresler M, Tse D. Optimal assembly for high throughput shotgun sequencing. BMC Bioinforma. 2013;14(5):1.

    Not in our library10.1186/1471-2105-14-s5-s18

  3. 3.

    Gnerre S, MacCallum I, Przybylski D, Ribeiro FJ, Burton JN, Walker BJ, Sharpe T, Hall G, Shea TP, Sykes S, et al. High-quality draft assemblies of mammalian genomes from massively parallel sequence data. Proc Natl Acad Sci. 2011;108(4):1513-18.

    Not in our library10.1073/pnas.1017351108

  4. 4.

    Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z, Li Y, Li S, Shan G, Kristiansen K, et al. De novo assembly of human genomes with massively parallel short read sequencing. Genome Res. 2010;20(2):265-72.

    Not in our library10.1101/gr.097261.109

  5. 5.

    Schatz MC, Delcher AL, Salzberg SL. Assembly of large genomes using second-generation sequencing. Genome Res. 2010;20(9):1165-73.

    Not in our library10.1101/gr.101360.109

  6. 6.

    Eid J, Fehr A, Gray J, Luong K, Lyle J, Otto G, Peluso P, Rank D, Baybayan P, Bettman B, et al. Real-time dna sequencing from single polymerase molecules. Science. 2009;323(5910):133-8.

    Not in our library10.1126/science.1162986

  7. 7.

    Lee H, Gurtowski J, Yoo S, Marcus S, McCombie WR, Schatz M. Error correction and assembly complexity of single molecule sequencing reads. BioRxiv. 2014;006395.

    Not in our library

  8. 8.

    Koren S, Schatz MC, Walenz BP, Martin J, Howard JT, Ganapathy G, Wang Z, Rasko DA, McCombie WR, Jarvis ED, et al. Hybrid error correction and de novo assembly of single-molecule sequencing reads. Nat Biotechnol. 2012;30(7):693-700.

    Not in our library10.1038/nbt.2280

  9. 9.

    Ono Y, Asai K, Hamada M. Pbsim: Pacbio reads simulator–toward accurate genome assembly. Bioinformatics. 2013;29(1):119-21.

    Not in our library10.1093/bioinformatics/bts649

  10. 10.

    Lam KK, Khalak A, Tse D. Near-optimal assembly for shotgun sequencing with noisy reads. BMC Bioinforma. 2014;15(Suppl 9):4.

    Not in our library10.1186/1471-2105-15-s9-s4

  11. 11.
    Reducing assembly complexity of microbial genomes with single-molecule sequencing · 2013
    No notice
  12. 12.

    Chin CS, Alexander DH, Marks P, Klammer AA, Drake J, Heiner C, Clum A, Copeland A, Huddleston J, Eichler EE, et al. Nonhybrid, finished microbial genome assemblies from long-read smrt sequencing data. Nat Methods. 2013;10(6):563-9.

    Not in our library10.1038/nmeth.2474

  13. 13.

    Ribeiro FJ, Przybylski D, Yin S, Sharpe T, Gnerre S, Abouelleil A, Berlin AM, Montmayeur A, Shea TP, Walker BJ, et al. Finished bacterial genomes from shotgun sequence data. Genome Res. 2012;22(11):2270-77.

    Not in our library10.1101/gr.141515.112

  14. 14.

    Berlin K, Koren S, Chin CS, Drake JP, Landolin JM, Phillippy AM. Assembling large genomes with single-molecule sequencing and locality-sensitive hashing. Nat Biotechnol. 2015;33(6):623-30.

    Not in our library10.1038/nbt.3238

  15. 15.

    Chinwalla AT, Cook LL, Delehaunty KD, Fewell GA, Fulton LA, Fulton RS, Graves TA, Hillier LW, Mardis ER, McPherson JD, et al. Initial sequencing and comparative analysis of the mouse genome. Nature. 2002;420(6915):520-62.

    Not in our library10.1038/nature01262

  16. 16.

    Schwartz DC, Li X, Hernandez LI, Ramnarain SP, Huff EJ, Wang YK. Ordered restriction maps of saccharomyces cerevisiae chromosomes constructed by optical mapping. Science. 1993;262(5130):110-4.

    Not in our library10.1126/science.8211116

  17. 17.

    Dong Y, Xie M, Jiang Y, Xiao N, Du X, Zhang W, Tosser-Klopp G, Wang J, Yang S, Liang J, et al. Sequencing and automated whole-genome optical mapping of the genome of a domestic goat (capra hircus). Nat Biotechnol. 2013;31(2):135-41.

    Not in our library10.1038/nbt.2478

  18. 18.

    Shelton JM, Coleman MC, Herndon N, Lu N, Lam ET, Anantharaman T, Sheth P, Brown SJ. Tools and pipelines for bionano data: molecule assembly pipeline and fasta super scaffolding tool. BMC Genomics. 2015;16(1):734.

    Not in our library10.1186/s12864-015-1911-8

  19. 19.
    Assessing structural variation in a personal genome—towards a human reference diploid genome · 2015
    No notice
  20. 20.

    Zheng GXY, Lau BT, Schnall-Levin M, Jarosz M, Bell JM, Hindson CM, Kyriazopoulou-Panagiotopoulou S, Masquelier DA, Merrill L, Terry JM, et al. Haplotyping germline and cancer genomes with high-throughput linked-read sequencing. Nat Biotechnol. 2016;34(3):303-11.

    Not in our library10.1038/nbt.3432

  21. 21.
    Extensive sequencing of seven human genomes to characterize benchmark reference materials · 2016
    No notice
  22. 22.
    Illumina TruSeq Synthetic Long-Reads Empower De Novo Assembly and Resolve Complex, Highly-Repetitive Transposable Elements · 2014
    No notice
  23. 23.

    Koren S, Phillippy AM. One chromosome, one contig: complete microbial genomes from long-read sequencing and assembly. Curr Opin Microbiol. 2015;23:110-20.

    Not in our library10.1016/j.mib.2014.11.014

  24. 24.
    Genome assembly using Nanopore-guided long and error-free DNA reads · 2015
    No notice
  25. 25.

    Lieberman-Aiden E, Van Berkum NL, Williams L, Imakaev M, Ragoczy T, Telling A, Amit I, Lajoie BR, Sabo PJ, Dorschner MO, et al. Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science. 2009;326(5950):289-93.

    Not in our library10.1126/science.1181369

  26. 26.

    Duan Z, Andronescu M, Schutz K, McIlwain S, Kim YJ, Lee C, Shendure J, Fields S, Blau CA, Noble WS. A three-dimensional model of the yeast genome. Nature. 2010;465(7296):363-7.

    Not in our library10.1038/nature08973

  27. 27.

    Burton JN, Adey A, Patwardhan RP, Qiu R, Kitzman JO, Shendure J. Chromosome-scale scaffolding of de novo genome assemblies based on chromatin interactions. Nat Biotechnol. 2013;31(12):1119-25.

    Not in our library10.1038/nbt.2727

  28. 28.

    Kaplan N, Dekker J. High-throughput genome scaffolding from in vivo dna interaction frequency. Nat Biotechnol. 2013;31(12):1143-7.

    Not in our library10.1038/nbt.2768

  29. 29.
    High-quality genome (re)assembly using chromosomal contact data · 2014
    No notice
  30. 30.

    Siva N. 1000 genomes project. Nat Biotechnol. 2008;26(3):256-6.

    Not in our library10.1038/nbt0308-256b

  31. 31.

    Pendleton M, Sebra R, Pang AWC, Chun AW, Ummat A, Franzen O, Rausch T, Stütz AM, Stedman W, Anantharaman T, Hastie A, et al. Assembly and diploid architecture of an individual human genome via single-molecule technologies. Nat Methods. 2015;12(8):780-6.

    Not in our library10.1038/nmeth.3454

  32. 32.

    Schneider VA, Lindsay TG, Howe K, Bouk N, Chen HC, Kitts PA, Murphy TD, Pruitt KD, Thibaud-Nissen F, Albracht D, Fulton RS, Kremitzki M, Magrini V, Markovic C, McGrath S, Steinberg KM, Auger K, Chow W, Collins J, Harden G, Hubbard T, Pelan S, Simpson JT, Threadgold G, Torrance J, Wood J, Clarke L, Koren S, Boitano M, Li H, Chin CS, Phillippy AM, Durbin R, Wilson RK, Flicek P, Church DM. Evaluation of grch38 and de novo haploid genome assemblies demonstrates the enduring quality of the reference assembly. bioRxiv. 2016. doi:10.1101/072116.

    Not in our library

  33. 33.

    Li H, Durbin R. Fast and accurate short read alignment with burrows–wheeler transform. Bioinformatics. 2009;25(14):1754-60.

    Not in our library10.1093/bioinformatics/btp324

  34. 34.

    Bickhart DM, Rosen BD, Koren S, Sayre BL, Hastie AR, Chan S, Lee J, Lam ET, Liachko I, Sullivan ST, Burton JN, Huson HJ, Kelley CM, Hutchison JL, Zhou Y, Sun J, Crisa A, Ponce de Leon FA, Schwartz JC, Hammond JA, Waldbieser GC, Schroeder SG, Liu GE, Dunham MJ, Shendure J, Sonstegard TS, Phillippy AM, Van Tassell CP, Smith TPL. Single-molecule sequencing and conformational capture enable de novo mammalian reference genomes. bioRxiv. 2016. doi:10.1101/064352.

    Not in our library

  35. 35.

    Delcher AL, Kasif S, Fleischmann RD, Peterson J, White O, Salzberg SL. Alignment of whole genomes. Nucleic Acids Res. 1999;27(11):2369-76.

    Not in our library10.1093/nar/27.11.2369

  36. 36.
    Genome assembly forensics: finding the elusive mis-assembly · 2008
    No notice
  37. 37.

    Kidd JM, Graves T, Newman TL, Fulton R, Hayden HS, Malig M, Kallicki J, Kaul R, Wilson RK, Eichler EE. A human genome structural variation sequencing resource reveals insights into mutational mechanisms. Cell. 2010;143(5):837-47.

    Not in our library10.1016/j.cell.2010.10.027

  38. 38.

    Du X, Womack J, Owens K, Elliott J, Sayre B, Bottcher P, Milan D, Podesta MG, Zhao S, Malek M. A whole-genome radiation hybrid panel for goat. Small Rumin Res. 2012;105(1):114-6.

    Not in our library10.1016/j.smallrumres.2011.11.023

  39. 39.

    Treangen TJ, Darling AE, Achaz G, Ragan MA, Messeguer X, Rocha EP. A novel heuristic for local multiple alignment of interspersed dna repeats. IEEE/ACM Trans Comput Biol Bioinforma (TCBB). 2009;6(2):180-9.

    Not in our library10.1109/tcbb.2009.9

  40. 40.
    Chromosome-scale shotgun assembly using an in vitro method for long-range linkage · 2016
    No notice
All 44 references

Cited by papers we hold 9

Reads

Read by people on this page

None yet.

Checked or read by AI through naulon

None yet.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.

Are you an author?

Is this your paper?

Claim it to add your note and be paid when agents cite it. Free.