FASTER IMPLEMENTATION OF PROTEIN FOLDING ALGORITHM AND EXTENDED BURROWS WHEELER TRANSFORM

Abstract

Over the recent years, there has been an extensive development in the field of bioinformatics. A couple amongst the various works done under this field includes Protein Folding and Genome based Phylogenetic Studies. Protein folding is the physical process by which a polypeptide folds into its characteristic and functional three-dimensional structure. The problem is inherently intractable and hence, non-analytical alternatives for solving the problem exist. Even such alternatives are computationally intensive due to the inherent vastness of the search space. Genome based Phylogenetic studies include the process of matching Mitochondrial DNA of different species to establish their phylogenetic relation. One novel algorithm to achieve this is the Extended Burrows Wheeler Transform. This algorithm also is very compute intensive due to size of mitochondrial genomes used as data. All this necessitates the optimization of such algorithms by parallelization or other means. The Sony-Toshiba-IBM Cell Broadband Engine is heterogeneous multi core architecture, consisting of a traditional PowerPC based master core meant to run the operating system, and 8 delegate slave processors built for compute intensive processing. Exposure of system level optimization features allows programmer to use algorithm specific tweaks to achieve order of magnitude improvements using Cell-BE. CUDA is a parallel computing architecture developed by NVIDIA. It is a middle-ware compute engine which exposes the power of NVIDIA Graphics Processing Units to software developers through industry standard programming language. This work introduces a modification on the traditional Protein Folding Algorithm. It describes the implementation of the modified algorithm on Cell-BE and CUDA. Lastly the work describes the implementation of Extended Burrows Wheeler Transform on CUDA and issues involve