Toward almost closed genomes with GapFiller.

Boetzer M, Pirovano W. · 2012

Read Toward almost closed genomes with GapFiller. by Boetzer M, Pirovano W. (2012) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc3446322.txt.

Introduction

Boetzer and Pirovano described GapFiller in 2012, a program that closes the holes left inside genome assemblies. Sequencing projects aim to puzzle millions of short reads into one complete genome, but drafts usually end as scaffolds riddled with gaps. Their automated strategy uses paired reads, sequenced from both ends of a DNA fragment, to bridge each gap.

Tested on bacterial and larger eukaryotic datasets, the method closed gaps reliably with only a few errors slipping through. Every gap shut in software is one less round of costly laboratory finishing work. The authors report the wet-lab burden needed to finish a genome drops drastically as a result. The free tool targets the least glamorous, most expensive step of genome projects.

Catalog record

CREATORBoetzer M, Pirovano W.
YEAR2012
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC3446322

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Toward almost closed genomes with GapFiller By Marten Boetzer, Walter Pirovano Published in: Genome Biology DOI: 10.1186/gb-2012-13-6-r56 ABSTRACT Abstract De novo assembly is a commonly used application of next-generation sequencing experiments. The ultimate goal is to puzzle millions of reads into one complete genome, although draft assemblies usually result in a number of gapped scaffold sequences. In this paper we propose an automated strategy, called GapFiller, to reliably close gaps within scaffolds using paired reads. The method shows good results on both bacterial and eukaryotic datasets, allowing only few errors. As a consequence, the amount of additional wetlab work needed to close a genome is drastically reduced. The software is available at http://www.baseclear.com/bioinformatics-tools/. BACKGROUND De novo sequencing of unknown species and variants has become a major application of next-generation sequencing (NGS) technologies. As a consequence, there is a high demand for de novo assembly tools that can reconstruct the genomic sequence from millions of short reads. At present a vast number of tools is available to create a draft assembly that represents the genome in a number of contiguous sequences (contigs), such as Velvet [1], ABySS [2], and SOAPdenovo [3]. Nonetheless, the full closure of a complete genome remains a challenging and often expensive task. Generally, problems reside in the assembly of low-coverage areas and repetitive elements. Even though the distance information of paired-read sequences can help to bridge these difficult areas by linking the contigs into larger scaffolds [4,5], scaffolding does not solve the inherent problem of low-coverage and repetitive elements: it does not add novel sequence information to the draft assembly. At present, two strategies have been proposed to automatically close draft assemblies: Li et al. [3] included a gap closure routine to their SOAPdenovo assembly software, whereas more recently Tsai et al. [6] introduced the IMAGE algorithm. Both methods use De Bruijn graphs to create a local assembly and seek to fill the gaps with the resulting contigs. A drawback of these strategies is that no prior knowledge of the estimated gap size is taken into account. Therefore, the local assembly might not reflect the true genomic situation. Also, the practical usability of these methods by a broad audience requires additional development. As a consequence, at present, most genome assemblies are still incomplete after scaffolding and would ideally require accurate gap closure. Given that manual closure of incomplete regions with Sanger sequencing is expensive, genome assemblies submitted to sequence databases often lack a significant number of nucleotides, especially in the case of larger eukaryotes. Importantly, the missing repetitive or low-coverage regions may contain essential functions for the organism studied. In this study we aim to reduce the number of undefined nucleotides by automatically filling in the gapped regions within scaffolds. For this purpose, paired reads are (re)used. In brief, our GapFiller method seeks to find read pairs of which one member matches within a sequence region and the second member falls (partially) within the gap. The latter reads are then used to close the gap through sequence (k-mer) overlap. Gaps are entirely closed only if the size of the sequence insertion corresponds closely to the estimated gap size after scaffolding, which is based on the alignment of paired reads to the contigs. The process is iteratively repeated until no further gaps can be closed. We demonstrate that GapFiller gives promising results both on bacterial and eukaryotic datasets and accurately closes most of the gaps. From a comparative analysis with IMAGE and SOAPdenovo we show that our algorithm provides the most reliable outcomes. Finally, we investigate the nature of the closed regions in the human genome and show that these contain important coding and non-coding information. The software is designed to be accessible to a broad audience given its user-friendly design and limited memory usage. GapFiller can be downloaded from [7]. RESULTS Findings on the bacterial datasets GapFiller was evaluated on four distinct bacterial datasets that are characterized by different genome sizes, levels of complexity and short-read sequence input. Also, the assembly strategy underlying the construction of the scaffolds varies and provides some good practical examples of draft assemblies (see Materials and methods for more information). Quality assessment was performed through comparison with the known (closed) reference genome and error types were classified into three categories - SNPs, indels and misjunctions - according to [8]. A first observation on these datasets is that automated gap closure can indeed be an important step in finishing (bacterial) genomes. In Table 1 we show that all methods can effectively close a significant amount of gaps and also that the total gap length is drastically reduced. However, from the Escherichia coli and Streptomyces coelicolor datasets it is apparent that the IMAGE strategy clearly underperforms the other two strategies on most quality measurements: the total gap length is reduced at most by 60% even though the number of errors increases significantly. This is partly due to the fact that IMAGE can not handle multiple libraries (nor mate pair libraries), and therefore the analysis was performed using only the library with the shortest insert size. In contrast, SOAPdenovo and GapFiller show more promising results: in E. coli the number of gaps (gap count) can be reduced by 97% and 98%, respectively; in S. coelicolor these numbers are 62% and 85%, respectively. Overall, the results indicate GapFiller closes a larger amount of gaps while making significantly less errors than the other methods. Arguably, the total gap length is shorter after gap closure with SOAPdenovo, but apparently at the cost of an increased number of misassemblies. The latter two tendencies are more pronounced in the Staphylococcus aureus and Rhodobacter sphaeroides datasets. A likely explanation resides in the fact that the raw input FASTQ reads are heavily filtered with Quake [9], leading to a relatively low genome coverage. For comparison purposes we reran our GapFiller algorithm with less stringent settings (GapFiller-LC: min coverage o = 1, ratio r = 0.5) to yield a more similar gap length to SOAPdenovo. We observe that applying less conservative settings leads (obviously) to more errors, but that these are still significantly less than those made with SOAPdenovo (regardless of the error type). [Table: Gap closure results obtained on the bacterial datasets] Another interesting observation concerns the computational resources needed to run the software. Figure 1 shows a comparative analysis between the runtimes and memory usage of SOAPdenovo and GapFiller based on one iterative cycle. Apparently SOAPdenovo can complete the process faster if the number of input reads is very low or high, but for intermediate data sizes (10 to 20 million reads) GapFiller needs somewhat less time. Differences are more pronounced when comparing the memory usage of both methods: SOAPdenovo requires an increasing amount of memory to analyze larger input datasets (up to 3.8 GB for S. coelicolor and 6.0 GB for human) whereas GapFiller shows stable memory usage of approximately 0.1 GB. This is because GapFiller seeks to store the intermediate output temporarily rather than maintaining it in the memory. As a consequence the method is well suited for computing systems with smaller amounts of memory. [Figure: Time and memory consumption of gap closure software. Comparative analysis of the runtime and memory usage per dataset based on a single iteration.

Read the complete text