Short Read Alignment

Short read alignment aims to align short reads to reference genomes, which is essential to almost all applications related to next-generation sequencing technologies, such as methylation patterns profiling (MeDIP-Seq), protein-DNA interactions mapping (ChIP-Seq), and differentially expressed genomes identification (RNA-Seq). All these applications require aligning large quantities of short reads to the human genome (or the genomes of other species) in a reasonably short time. However, the computational cost for aligning large-scale short reads to mammalian genomes is prohibitive and thus establishes a strong need for short read aligners that consume less time and fewer computing resources.

CUSHAW

CUSHAW has evolved into a software package designed for next-generation sequencing read alignment. This is the first version of the package, which only provides support for ungapped read alignment. It is a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform (BWT) and is programmed in CUDA C++  parallel programming language. Performance evaluation, using simulated as well as real short read datasets, reveals that CUSHAW running on one or two GPUs achieves significant speedups in terms of execution time, while yielding comparable or even better alignment quality for paired-end alignments, compared to three popular BWT-based aligners: Bowtie, BWA and SOAP2. This aligner does not support for gapped alignments.

Download: Sourceforge

Publications:

 

CUSHAW2

CUSHAW2 is the second version of the CUSHAW package, which is a paralell and accurate long read aligner for gapped alignments to large genomes, such as the human genome. This aligner is part of our software package CUSHAW for next-generation sequencing read alignment. We have evaluated and compared CUSHAW2 to the three other long read aligners BWA-SW, Bowtie2, and GASSST, by aligning simulated and real datasets to the human genome. The performance evaluation shows that CUSHAW2 is consistently among the highest-ranked aligners in terms of alignment quality for both single-end and paired-end alignment, while demonstrating highly competitive speed. Furthermore, our aligner shows good parallel scalability with respect to the number of CPU threads.

Download: Sourceforge

Publications:

 

Other Related Research

Chen et al. present a hybrid system for short read mapping utilizing both software  and FPGA-based hardware. The compute intensive semi-global alignment operation is accelerated on the FPGA. The proposed FPGA aligner is implemented with a parallel block structure to gain computational efficiency. The paper also propose a block-wise alignment algorithm to approximate the score of the conventional dynamic programming algorithm. The performance comparison shows that the FPGA achieves an average speedup of 38 for the alignment operation on a Xilinx Virtex5 FPGA compared to the GASSST software implementation. For the overall execution time, the hybrid system achieves an average speedup of 2.4 compared to GASSST at comparable sensitivity and an average speedup of 1.8 compared to the popular BWA software at a significantly better sensitivity.

Publication:

  • Yupeng Chen, Bertil Schmidt, and Douglas L. Maskell: ".Accelerating short read mapping on an FPGA". Proceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays, 2012