Pebble and Rock Band: Heuristic Resolution of Repeats and Scaffolding in the Velvet Short-read De Novo Assembler

Overview

Journal PLoS One

Specialties General Medicine
Science

Date 2009 Dec 23

PMID 20027311

Citations 117

Authors

Daniel R Zerbino

Gayle K McEwen

Elliott H Margulies

Ewan Birney

Affiliations

Soon will be listed here.

Abstract

Background: Despite the short length of their reads, micro-read sequencing technologies have shown their usefulness for de novo sequencing. However, especially in eukaryotic genomes, complex repeat patterns are an obstacle to large assemblies.

Principal Findings: We present a novel heuristic algorithm, Pebble, which uses paired-end read information to resolve repeats and scaffold contigs to produce large-scale assemblies. In simulations, we can achieve weighted median scaffold lengths (N50) of above 1 Mbp in Bacteria and above 100 kbp in more complex organisms. Using real datasets we obtained a 96 kbp N50 in Pseudomonas syringae and a unique 147 kbp scaffold of a ferret BAC clone. We also present an efficient algorithm called Rock Band for the resolution of repeats in the case of mixed length assemblies, where different sequencing platforms are combined to obtain a cost-effective assembly.

Conclusions: These algorithms extend the utility of short read only assemblies into large complex genomes. They have been implemented and made available within the open-source Velvet short-read de novo assembler.

Citing Articles

Comparative genomic analysis and optimization of astaxanthin production of Rhodotorula paludigena TL35-5 and Rhodotorula sampaioana PL61-2.

Hoondee P, Phuengjayaem S, Kingkaew E, Rojsitthisak P, Sritularak B, Thompho S PLoS One. 2024; 19(7):e0304699.

PMID: 38995888 PMC: 11244826. DOI: 10.1371/journal.pone.0304699.

Genomic and biological insights of bacteriophages JNUWH1 and JNUWD in the arms race against bacterial resistance.

Zhang H, You J, Pan X, Hu Y, Zhang Z, Zhang X Front Microbiol. 2024; 15:1407039.

PMID: 38989022 PMC: 11233448. DOI: 10.3389/fmicb.2024.1407039.

Isolation and identification of specific phage C-3 and G21-7 against Avian pathogenic and its application to one-day-old geese.

Wang T, Zhang L, Zhang Y, Tong P, Ma W, Wang Y Front Microbiol. 2024; 15:1385860.

PMID: 38962142 PMC: 11221357. DOI: 10.3389/fmicb.2024.1385860.

Applications of de Bruijn graphs in microbiome research.

Dufault-Thompson K, Jiang X Imeta. 2024; 1(1):e4.

PMID: 38867733 PMC: 10989854. DOI: 10.1002/imt2.4.

Draft genome sequence and morphological data of PLACP1, a thermophilic chloramphenicol-resistant bacterium isolated from thermophilic sludge.

Tseng H, Matsutani M, Fujimoto N, Ohnishi A Data Brief. 2024; 54:110447.

PMID: 38708301 PMC: 11068547. DOI: 10.1016/j.dib.2024.110447.

References

Chaisson M, Pevzner P . Short read fragment assembly of bacterial genomes. Genome Res. 2007; 18(2):324-30. PMC: 2203630. DOI: 10.1101/gr.7088808. View

Pevzner P, Tang H . Fragment assembly with double-barreled data. Bioinformatics. 2001; 17 Suppl 1:S225-33. DOI: 10.1093/bioinformatics/17.suppl_1.s225. View

Wheeler D, Srinivasan M, Egholm M, Shen Y, Chen L, McGuire A . The complete genome of an individual by massively parallel DNA sequencing. Nature. 2008; 452(7189):872-6. DOI: 10.1038/nature06884. View

Myers E . The fragment assembly string graph. Bioinformatics. 2005; 21 Suppl 2:ii79-85. DOI: 10.1093/bioinformatics/bti1114. View

Slater G, Birney E . Automated generation of heuristics for biological sequence comparison. BMC Bioinformatics. 2005; 6:31. PMC: 553969. DOI: 10.1186/1471-2105-6-31. View

Whiteford N, Haslam N, Weber G, Prugel-Bennett A, Essex J, Roach P . An analysis of the feasibility of short read sequencing. Nucleic Acids Res. 2005; 33(19):e171. PMC: 1278949. DOI: 10.1093/nar/gni170. View

Farrer R, Kemen E, Jones J, Studholme D . De novo assembly of the Pseudomonas syringae pv. syringae B728a genome using Illumina/Solexa short sequence reads. FEMS Microbiol Lett. 2008; 291(1):103-11. DOI: 10.1111/j.1574-6968.2008.01441.x. View

Bentley D . Whole-genome re-sequencing. Curr Opin Genet Dev. 2006; 16(6):545-52. DOI: 10.1016/j.gde.2006.10.009. View

Pop M, Kosack D, Salzberg S . Hierarchical scaffolding with Bambus. Genome Res. 2004; 14(1):149-59. PMC: 314292. DOI: 10.1101/gr.1536204. View

10.

Hossain M, Azimi N, Skiena S . Crystallizing short-read assemblies around seeds. BMC Bioinformatics. 2009; 10 Suppl 1:S16. PMC: 2648751. DOI: 10.1186/1471-2105-10-S1-S16. View

11.

Margulies M, Egholm M, Altman W, Attiya S, Bader J, Bemben L . Genome sequencing in microfabricated high-density picolitre reactors. Nature. 2005; 437(7057):376-80. PMC: 1464427. DOI: 10.1038/nature03959. View

12.

Pevzner P, Tang H, Waterman M . An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci U S A. 2001; 98(17):9748-53. PMC: 55524. DOI: 10.1073/pnas.171285098. View

13.

Batzoglou S, Jaffe D, Stanley K, Butler J, Gnerre S, Mauceli E . ARACHNE: a whole-genome shotgun assembler. Genome Res. 2002; 12(1):177-89. PMC: 155255. DOI: 10.1101/gr.208902. View

14.

Johnson D, Mortazavi A, Myers R, Wold B . Genome-wide mapping of in vivo protein-DNA interactions. Science. 2007; 316(5830):1497-502. DOI: 10.1126/science.1141319. View

15.

Butler J, MacCallum I, Kleber M, Shlyakhter I, Belmonte M, Lander E . ALLPATHS: de novo assembly of whole-genome shotgun microreads. Genome Res. 2008; 18(5):810-20. PMC: 2336810. DOI: 10.1101/gr.7337908. View

16.

Simpson J, Wong K, Jackman S, Schein J, Jones S, Birol I . ABySS: a parallel assembler for short read sequence data. Genome Res. 2009; 19(6):1117-23. PMC: 2694472. DOI: 10.1101/gr.089532.108. View

17.

Chaisson M, Brinza D, Pevzner P . De novo fragment assembly with short mate-paired reads: Does the read length matter?. Genome Res. 2008; 19(2):336-46. PMC: 2652199. DOI: 10.1101/gr.079053.108. View

18.

Warren R, Sutton G, Jones S, Holt R . Assembling millions of short DNA sequences using SSAKE. Bioinformatics. 2006; 23(4):500-1. PMC: 7109930. DOI: 10.1093/bioinformatics/btl629. View

19.

Dohm J, Lottaz C, Borodina T, Himmelbauer H . SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing. Genome Res. 2007; 17(11):1697-706. PMC: 2045152. DOI: 10.1101/gr.6435207. View

20.

Hillier L, Marth G, Quinlan A, Dooling D, Fewell G, Barnett D . Whole-genome sequencing and variant discovery in C. elegans. Nat Methods. 2008; 5(2):183-8. DOI: 10.1038/nmeth.1179. View