License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-21294
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2129/

Bozdag, Doruk ; Barbacioru, Catalin C. ; Catalyurek, Umit V.

Parallelization of Mapping Algorithms for Next Generation Sequencing Applications

pdf-format:
Dokument 1.pdf (132 KB)


Abstract

With the advent of next-generation high throughput sequencing instruments, large volumes of short sequence data are generated at an unprecedented rate. Processing and analyzing these massive data requires overcoming several challenges. A particular challenge addressed in this abstract is the mapping of short sequences (reads) to a reference genome by allowing mismatches. This is a significantly time consuming combinatorial problem in many applications including whole-genome resequencing, targeted sequencing, transcriptome/small RNA, DNA methylation and ChiP sequencing, and takes time on the order of days using existing sequential techniques on large scale datasets. In this work, we introduce six parallelization methods each having different scalability characteristics to speedup short sequence mapping. We also address an associated load balancing problem that involves grouping nodes of a tree from different levels. This problem arises due to a trade-off between computational cost and granularity while partitioning the workload. We comparatively present the proposed parallelization methods and give theoretical cost models for each of them. Experimental results on real datasets demonstrate the effectiveness of the methods and indicate that they are successful at reducing the execution time from the order of days to under just a few hours for large datasets. To the best of our knowledge this is the first study on parallelization of short sequence mapping problem.

BibTeX - Entry

@InProceedings{bozdag_et_al:DSP:2009:2129,
  author =	{Doruk Bozdag and Catalin C. Barbacioru and Umit V. Catalyurek},
  title =	{Parallelization of Mapping Algorithms for Next Generation Sequencing Applications},
  booktitle =	{Combinatorial Scientific Computing},
  year =	{2009},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  number =	{09061},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2129},
  annote =	{Keywords: Genome sequencing, sequence mapping}
}

Keywords: Genome sequencing, sequence mapping
Seminar: 09061 - Combinatorial Scientific Computing
Issue date: 2009
Date of publication: 16.09.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI