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
Download: Sourceforge
Publications:
- Yongchao Liu, Bertil Schmidt, and Douglas L. Maskell: "CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform". Bioinformatics , 2012, 28(14): 1830-1837
CUSHAW2
Download: Sourceforge
Publications:
- Yongchao Liu and Bertil Schmidt:"Long read alignment based on maximal exact match seeds". Bioinformatics, 2012, 28(18): i318-i324
- Yongchao Liu and Bertil Schmidt: "CUSHAW2-GPU: empowering faster gapped short-read alignment using GPU computing". IEEE Design & Test of Computers, 2014, 3(1): 1-9
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