SOPRA: Scaffolding algorithm for paired reads via statistical optimization
- PMID: 20576136
- PMCID: PMC2909219
- DOI: 10.1186/1471-2105-11-345
SOPRA: Scaffolding algorithm for paired reads via statistical optimization
Abstract
Background: High throughput sequencing (HTS) platforms produce gigabases of short read (<100 bp) data per run. While these short reads are adequate for resequencing applications, de novo assembly of moderate size genomes from such reads remains a significant challenge. These limitations could be partially overcome by utilizing mate pair technology, which provides pairs of short reads separated by a known distance along the genome.
Results: We have developed SOPRA, a tool designed to exploit the mate pair/paired-end information for assembly of short reads. The main focus of the algorithm is selecting a sufficiently large subset of simultaneously satisfiable mate pair constraints to achieve a balance between the size and the quality of the output scaffolds. Scaffold assembly is presented as an optimization problem for variables associated with vertices and with edges of the contig connectivity graph. Vertices of this graph are individual contigs with edges drawn between contigs connected by mate pairs. Similar graph problems have been invoked in the context of shotgun sequencing and scaffold building for previous generation of sequencing projects. However, given the error-prone nature of HTS data and the fundamental limitations from the shortness of the reads, the ad hoc greedy algorithms used in the earlier studies are likely to lead to poor quality results in the current context. SOPRA circumvents this problem by treating all the constraints on equal footing for solving the optimization problem, the solution itself indicating the problematic constraints (chimeric/repetitive contigs, etc.) to be removed. The process of solving and removing of constraints is iterated till one reaches a core set of consistent constraints. For SOLiD sequencer data, SOPRA uses a dynamic programming approach to robustly translate the color-space assembly to base-space. For assessing the quality of an assembly, we report the no-match/mismatch error rate as well as the rates of various rearrangement errors.
Conclusions: Applying SOPRA to real data from bacterial genomes, we were able to assemble contigs into scaffolds of significant length (N50 up to 200 Kb) with very few errors introduced in the process. In general, the methodology presented here will allow better scaffold assemblies of any type of mate pair sequencing data.
Figures
![Figure 1](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-1.gif)
![Figure 2](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-2.gif)
![Figure 3](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-3.gif)
![Figure 4](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-4.gif)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-i3.jpg)
![Figure 5](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-5.gif)
![Figure 6](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-6.gif)
![Figure 7](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-7.gif)
![Figure 8](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/2909219/bin/1471-2105-11-345-8.gif)
Similar articles
-
Assessing the benefits of using mate-pairs to resolve repeats in de novo short-read prokaryotic assemblies.BMC Bioinformatics. 2011 Apr 13;12:95. doi: 10.1186/1471-2105-12-95. BMC Bioinformatics. 2011. PMID: 21486487 Free PMC article.
-
GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies.Bioinformatics. 2012 Jun 1;28(11):1429-37. doi: 10.1093/bioinformatics/bts175. Epub 2012 Apr 6. Bioinformatics. 2012. PMID: 22492642
-
Benchmarking of de novo assembly algorithms for Nanopore data reveals optimal performance of OLC approaches.BMC Genomics. 2016 Aug 22;17 Suppl 7(Suppl 7):507. doi: 10.1186/s12864-016-2895-8. BMC Genomics. 2016. PMID: 27556636 Free PMC article.
-
Genome sequence assembly algorithms and misassembly identification methods.Mol Biol Rep. 2022 Nov;49(11):11133-11148. doi: 10.1007/s11033-022-07919-8. Epub 2022 Sep 23. Mol Biol Rep. 2022. PMID: 36151399 Review.
-
A comprehensive review of scaffolding methods in genome assembly.Brief Bioinform. 2021 Sep 2;22(5):bbab033. doi: 10.1093/bib/bbab033. Brief Bioinform. 2021. PMID: 33634311 Review.
Cited by
-
Maptcha: an efficient parallel workflow for hybrid genome scaffolding.BMC Bioinformatics. 2024 Aug 8;25(1):263. doi: 10.1186/s12859-024-05878-4. BMC Bioinformatics. 2024. PMID: 39118013 Free PMC article.
-
Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing.Cell Rep Methods. 2024 May 20;4(5):100754. doi: 10.1016/j.crmeth.2024.100754. Epub 2024 Apr 12. Cell Rep Methods. 2024. PMID: 38614089 Free PMC article.
-
RegScaf: a regression approach to scaffolding.Bioinformatics. 2022 May 13;38(10):2675-2682. doi: 10.1093/bioinformatics/btac174. Bioinformatics. 2022. PMID: 35561180 Free PMC article.
-
Characterization of Komagataeibacter Isolate Reveals New Prospects in Waste Stream Valorization for Bacterial Cellulose Production.Microorganisms. 2021 Oct 26;9(11):2230. doi: 10.3390/microorganisms9112230. Microorganisms. 2021. PMID: 34835356 Free PMC article.
-
SWALO: scaffolding with assembly likelihood optimization.Nucleic Acids Res. 2021 Nov 18;49(20):e117. doi: 10.1093/nar/gkab717. Nucleic Acids Res. 2021. PMID: 34417615 Free PMC article.
References
-
- MacLean D, Jones JD, Studholme DJ. Application of 'next-generation' sequencing technologies to microbial genetics. Nat Rev Microbiol. 2009;7(4):287–296. - PubMed
-
- Mardis ER. The impact of next-generation sequencing technology on genetics. Trends Genet. 2008;24(3):133–141. - PubMed
-
- Jones NC, Pevzner P. An introduction to bioinformatics algorithms. Cambridge, MA: MIT Press; 2004.
Publication types
MeSH terms
Grants and funding
LinkOut - more resources
Full Text Sources
Other Literature Sources