PASQUAL: Parallel techniques for next generation genome sequence assembly

Xing Liu, Pushkar R. Pande, Henning Meyerhenke, David A. Bader

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

The study of genomes has been revolutionized by sequencing machines that output many short overlapping substrings (called reads). The task of sequence assembly in practice is to reconstruct long contiguous genome subsequences from the reads. With Next Generation Sequencing (NGS) technologies, assembly software needs to be more accurate, faster, and more memory-efficient due to the problem complexity and the size of the data sets. In this paper, we develop parallel algorithms and compressed data structures to address several computational challenges of NGS assembly. We demonstrate how commonly available multicore architectures can be efficiently utilized for sequence assembly. In all stages (indexing input strings, string graph construction and simplification, extraction of contiguous subsequences) of our software Pasqual, we use shared-memory parallelism to speed up the assembly process. In our experiments with data of up to 6.8 billion base pairs, we demonstrate that Pasqual generally delivers the best tradeoff between speed, memory consumption, and solution quality. On synthetic and real data sets Pasqual scales well on our test machine with 40 CPU cores with increasing number of threads. Given enough cores, Pasqual is fastest in our comparison.

Original languageEnglish (US)
Article number6226376
Pages (from-to)977-986
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Volume24
Issue number5
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • de novo sequence assembly
  • high-performance bioinformatics
  • Parallel algorithms
  • parallel suffix array construction
  • shared memory parallelism

Fingerprint

Dive into the research topics of 'PASQUAL: Parallel techniques for next generation genome sequence assembly'. Together they form a unique fingerprint.

Cite this