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

TY - CHAP

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

AU - Flouri, Tomas

AU - Holub, Jan

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

PY - 2010

Y1 - 2010

N2 - The constant advances in sequencing technology 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 this massive amount of data, efficient algorithms for mapping these reads to reference sequences are in great demand, and recently, there has been ample work for publishing such algorithms. 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 applied to address the problem of mapping millions of reads to multiple genomic sequences.

AB - The constant advances in sequencing technology 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 this massive amount of data, efficient algorithms for mapping these reads to reference sequences are in great demand, and recently, there has been ample work for publishing such algorithms. 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 applied to address the problem of mapping millions of reads to multiple genomic sequences.

U2 - 10.1109/BIBM.2010.5706551

DO - 10.1109/BIBM.2010.5706551

M3 - Conference paper

SN - 9781424483068

SP - 133

EP - 136

BT - 2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)

A2 - Park, Taesung

A2 - Chen, Luonan

A2 - Wong, Limsoon

A2 - Tsui, Stephen

A2 - Ng, Michael

A2 - Hu, Xiaohua

PB - IEEE

ER -