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

Costas S. Iliopoulos; Derrick Kourie; Laurent Mouchard; Themba K. Musombuka; Solon P. Pissis; Corne de Ridder

doi:10.1016/j.jda.2011.08.006

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

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

Informatics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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.

Original language	English
Pages (from-to)	15 - 22
Number of pages	8
Journal	Journal of Discrete Algorithms
Volume	10
DOIs	https://doi.org/10.1016/j.jda.2011.08.006
Publication status	Published - Jan 2012

Access to Document

10.1016/j.jda.2011.08.006

Cite this

@article{c9e5e102cdf043878f5e69c45042bbe4,

title = "An algorithm for mapping short reads to a dynamically changing genomic sequence",

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.",

author = "Iliopoulos, {Costas S.} and Derrick Kourie and Laurent Mouchard and Musombuka, {Themba K.} and Pissis, {Solon P.} and Ridder, {Corne de}",

year = "2012",

month = jan,

doi = "10.1016/j.jda.2011.08.006",

language = "English",

volume = "10",

pages = "15 -- 22",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

}

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 - Ridder, Corne de

PY - 2012/1

Y1 - 2012/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.

U2 - 10.1016/j.jda.2011.08.006

DO - 10.1016/j.jda.2011.08.006

M3 - Article

SN - 1570-8667

VL - 10

SP - 15

EP - 22

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

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

Abstract

Access to Document

Fingerprint

Cite this