TY - JOUR
T1 - An algorithm for mapping short reads to a dynamically changing genomic sequence
AU - Iliopoulos, Costas S.
AU - Kourie, Derrick
AU - Mouchard, Laurent
AU - Musombuka, Themba K.
AU - Pissis, Solon P.
AU - De Ridder, Corne
PY - 2012/1/1
Y1 - 2012/1/1
N2 - 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.
AB - 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.
KW - Mapping
KW - Next-generation sequencing
KW - String algorithms
UR - http://www.scopus.com/inward/record.url?scp=84855532326&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84855532326&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2011.08.006
DO - 10.1016/j.jda.2011.08.006
M3 - Article
AN - SCOPUS:84855532326
VL - 10
SP - 15
EP - 22
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
SN - 1570-8667
IS - 1
ER -