Change search
ReferencesLink to record
Permanent link

Direct link
GapFiller: a de novo assembly approach to fill the gap within paired reads
KTH, Centres, Science for Life Laboratory, SciLifeLab.
2012 (English)In: BMC Bioinformatics, ISSN 1471-2105, Vol. 13, S8- p.Article in journal (Refereed) Published
Abstract [en]

Background: Next Generation Sequencing technologies are able to provide high genome coverages at a relatively low cost. However, due to limited reads' length (from 30 bp up to 200 bp), specific bioinformatics problems have become even more difficult to solve. De novo assembly with short reads, for example, is more complicated at least for two reasons: first, the overall amount of "noisy" data to cope with increased and, second, as the reads' length decreases the number of unsolvable repeats grows. Our work's aim is to go at the root of the problem by providing a pre-processing tool capable to produce (in-silico) longer and highly accurate sequences from a collection of Next Generation Sequencing reads. Results: In this paper a seed-and-extend local assembler is presented. The kernel algorithm is a loop that, starting from a read used as seed, keeps extending it using heuristics whose main goal is to produce a collection of error-free and longer sequences. In particular, GapFiller carefully detects reliable overlaps and operates clustering similar reads in order to reconstruct the missing part between the two ends of the same insert. Our tool's output has been validated on 24 experiments using both simulated and real paired reads datasets. The output sequences are declared correct when the seed-mate is found. In the experiments performed, GapFiller was able to extend high percentages of the processed seeds and find their mates, with a false positives rate that turned out to be nearly negligible. Conclusions: GapFiller, starting from a sufficiently high short reads coverage, is able to produce high coverages of accurate longer sequences (from 300 bp up to 3500 bp). The procedure to perform safe extensions, together with the mate-found check, turned out to be a powerful criterion to guarantee contigs' correctness. GapFiller has further potential, as it could be applied in a number of different scenarios, including the post-processing validation of insertions/deletions detection pipelines, pre-processing routines on datasets for de novo assembly pipelines, or in any hierarchical approach designed to assemble, analyse or validate pools of sequences.

Place, publisher, year, edition, pages
2012. Vol. 13, S8- p.
Keyword [en]
National Category
Bioinformatics (Computational Biology)
URN: urn:nbn:se:kth:diva-104380DOI: 10.1186/1471-2105-13-S14-S8ISI: 000309358500008ScopusID: 2-s2.0-84871481892OAI: diva2:564844
Science for Life Laboratory - a national resource center for high-throughput molecular bioscienceSwedish e‐Science Research Center

QC 20121105

Available from: 2012-11-05 Created: 2012-11-01 Last updated: 2013-04-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Vezzi, Francesco
By organisation
Science for Life Laboratory, SciLifeLab
In the same journal
BMC Bioinformatics
Bioinformatics (Computational Biology)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 24 hits
ReferencesLink to record
Permanent link

Direct link