An algorithm for mapping short reads to a dynamically changing genomic sequence

Loading...
Thumbnail Image

Authors

Iliopoulos, Costas S.
Kourie, Derrick G.
Mouchard, Laurent
Musombuka, Themba K.
Pissis, Solon P.
De Ridder, Corne

Journal Title

Journal ISSN

Volume Title

Publisher

Elsevier

Abstract

Next-generation sequencing technologies have redefined the way genome sequencing is performed. They are able to produce tens of millions of short sequences (reads), during a single experiment, and with a much lower cost than previously possible. Due to the dramatic increase in the amount of data generated, a challenging task is to map (align) a set of reads to a reference genome. In this paper, we study a different version of this problem: mapping these reads to a dynamically changing genomic sequence. We propose a new practical algorithm, which employs a suitable data structure that takes into account potential dynamic effects (replacements, insertions, deletions) on the genomic sequence. The presented experimental results demonstrate that the proposed approach can be extended and applied to address the problem of mapping short reads to multiple related genomes.

Description

Keywords

String algorithms, Next-generation sequencing, Mapping

Sustainable Development Goals

Citation

Iliopoulos, CS, Kourie, D, Mouchard, L, Musombuka, TK, Pissis, SP & De Ridder, C 2012, 'An algorithm for mapping short reads to a dynamically changing genomic sequence', Journal of Discrete Algorithms, vol. 10, no. 1, pp. 15-22.