Bioinformatics is a field which concerns with application of information technology and computer science to the field of molecular biology. A very popular discipline in bioinformatics is Next-Generation Sequencing (NGS) or DNA sequencing. It specifies sequencing methods for determining the order of nucleotide bases; adenine, guanine, cytosine and thymine in a molecule of DNA which is then assembled for analysis. A central challenge in DNA sequencing is sequence alignment, whereby fragments of much longer DNA sequence are aligned and merged in order to construct the original sequence. A wide variety of alignment algorithms have been subsequently developed over the past few years. Some commonly used softwares implementing these algorithms are BWA-SW, Bowtie, Velvet, SOAP and MAQ. Most of these take a lot of time to execute on general purpose processors. Hardware accelerators such as GPUs and FPGAs can be used in conjunction with processors to fasten these applications. In this project, we first exploit the performance and memory issues in processor based implementation of various algorithms and choose one out of them for implementation. Secondly, we develop both a FPGA and a GPU based tool to achieve a considerable increase in performance of the chosen algorithm compared to its standalone processor implementation using hardware-software codesign.
This project was the beginning of my journey into Computer Science research. With the help of PhD students in the department, I developed the idea for my own project in January 2011: use of FPGAs to parallelize the existing DNA sequencing algorithms. I was aware of new software tools being developed in the market for DNA sequencing. I thought of addressing one such software tool and implementing it in parallel on FPGAs by unrolling the loops. Thus, I surveyed for 2 months and came up with recent software tools which, based on my rough estimate could be implemented in parallel. I then took this idea to one of the Computer Science faculty and we applied for the Summer Undergraduate Research Award (SURA). We got the grant from the Ministry of Human Resource and Development, India and the project began in Summer 2011 when I profiled the six software tools and based on their performance, selected one of them (BWA) to be implemented on FPGA. But, all hope came down when I began coding the algorithm in VHDL. I was working alone, there wasn’t enough guidance and resources in this area in our department and the algorithm was too complex for a novice like me to understand and implement. I continued to mull over the problem through the rest of the semester with very little success. Though the project was not completed, I learned a lot in the area of FPGAs, bioinformatics etc. and volunteered to organize the FPGA design contest for the international conference on Field Programmable Technology (FPT) held in December 2011. Interactions with researchers from all over the world in the area boosted my confidence. I made few contacts and discussed my problem with them. They provided me with insights and agreed to help me with my problem. I came back and re-opened the project to arrive at the design for parallelized implementation (shown in the attached report in the 'Publications' section). Due to lack of resources however, I wasn't able to implement the design.
Moving on, I took a course called 'Modern Parallel Programming' where we were given an option to submit the idea for our own project. I redrafted my previous proposal for parallelized implementation of BWA, this time for GPU instead of FPGA (GPUs are another class of hardware accelerators). My background research during the SURA days convinced me of the potential of this research. I joined with my partner Amit and we wrote the code for implementation of whole BWA algorithm on general purpose GPUs. Due to my background knowledge in the area, Amit's CUDA coding expertise and availability of high-performance GPUs in the department, the work went very smoothly unlike earlier. We tested our implementation on CPU X5650 @2.67GHz (6 cores), coupled with, GPU-nVidia Tesla M2070 (2 cores) and were able to obtain an average speed-up of 4.04 for alignment of 1 million 50bp query sequences as compared to standalone processor implementation.
This project taught me to keep pushing myself throughout the research process. Most importantly, I learned how crucial it is to thoroughly estimate the required knowledge and materials before starting a project.
Dhruv Jain, M. Balakrishnan, "FPGAs as accelerators for Next-Generation Sequencing Applications", A report submitted in partial fulfillment of the requirements of the Summer Undergraduate Research Award (SURA), Ministry of Human Resource and Development (HRD), Govt. of India, 2012. (Download Pdf)Dhruv Jain, Amit Jaiswal, "GPUBwa- Parallelization of Burrows Wheeler Aligner using Graphical Processing Units", Report for the project in the course- "Modern Parallel Programming", 2012. (Download Pdf)