Parallel algorithms for mapping short degenerate and weighted dna sequences to a reference genome

Costas S. Iliopoulos*, Mirka Miller, Solon P. Pissis

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


One of the most ambitious trends in current biomedical research is the large-scale genomic sequencing of patients. Novel high-throughput (or next-generation) sequencing technologies have redefined the way genome sequencing is performed. They are able to produce millions of short sequences (reads) in a single experiment, and with a much lower cost than previously possible. Due to this massive amount of data, efficient algorithms for mapping these sequences to a reference genome are in great demand, and recently, there has been ample work for publishing such algorithms. One important feature of these algorithms is the support of multithreaded parallel computing in order to speedup the mapping process. In this paper, we design parallel algorithms, which make use of the message-passing parallelism model, to address this problem efficiently. The proposed algorithms also take into consideration the probability scores assigned to each base for occurring in a specific position of a sequence. In particular, we present parallel algorithms for mapping short degenerate and weighted DNA sequences to a reference genome.

Original languageEnglish
Pages (from-to)249-259
Number of pages11
JournalInternational Journal of Foundations of Computer Science
Issue number2
Publication statusPublished - 1 Feb 2012
Externally publishedYes


  • next-generation sequencing
  • Parallel algorithms
  • string algorithms


Dive into the research topics of 'Parallel algorithms for mapping short degenerate and weighted dna sequences to a reference genome'. Together they form a unique fingerprint.

Cite this