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

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)15-22
Number of pages8
JournalJournal of Discrete Algorithms
Volume10
Issue number1
DOIs
Publication statusPublished - 1 Jan 2012
Externally publishedYes

Keywords

  • Mapping
  • Next-generation sequencing
  • String algorithms

Fingerprint Dive into the research topics of 'An algorithm for mapping short reads to a dynamically changing genomic sequence'. Together they form a unique fingerprint.

Cite this