Highly accurate and sensitive short read aligner

Gok M. Y., GÖREN UĞURDAĞ S., ÜNSALAN C., Sagiroglu M. S.

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, cilt.26, sa.2, ss.721-731, 2018 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 26 Sayı: 2
  • Basım Tarihi: 2018
  • Doi Numarası: 10.3906/elk-1703-251
  • Dergi Adı: TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.721-731
  • Anahtar Kelimeler: Alignment, short read, FPGA, Smith-Waterman, genome, sensitivity, accuracy
  • Marmara Üniversitesi Adresli: Evet

Özet

Next-generation sequencing generates large numbers of short reads from DNA. This makes it difficult to process and store. Therefore, efficient sequence alignment and mapping techniques are needed in bioinformatics. Alignment and mapping are the basic steps involved in genetic data analysis. The Smith Waterman (SW) algorithm, a well-known dynamic programming algorithm, is often used for this purpose. In this work, we propose to utilize Phred quality scores in Gotoh's affine gap model to increase the accuracy and sensitivity of the SW algorithm. Hardware platforms such as FPGAs and GPUs are commonly used to solve computationally expensive problems. In this work, a hybrid PC-FPGA system is built where the SW algorithm based on the affine gap model with Phred quality scores is implemented on the FPGA and a read compressor is implemented on the host PC. We compare our method with state-of-the-art systems such as Bowtie, BWA, and the Kim-Olson FPGA-based system in terms of sensitivity, accuracy, and speed. Based on extensive experiments, we observed that our proposed method is more sensitive and accurate as compared to other solutions.