Graduate Exam Abstract

Tanveer Pathan

M.S. Final

August 18, 2010, 11:00 AM

Room 425 Computer Science Building

RNA Secondary Structure Prediction using AlphaZ

Abstract: Optimizing complex algorithms using conventional programming languages can be a difficult task. The performance aspect of such implementations relies on the programmer and the target architectures. Minor alterations to the algorithm can result in a considerable amount of reprogramming effort. In our work, we experiment with equational programming using the AlphaZ tool. We illustrate our work using a fairly complex algorithm for RNA secondary structure prediction. The algorithm is extracted from the UNAFold software package, a huge C library, by identifying the time consuming parts. It is then represented as equations, which are transformed for optimizations, followed by code generation and finally validating the generated code by plugging it back into the original C program. The algorithm, in its basic form, has complexity O(N^4). We show that the optimized O(N^3) algorithm can be derived systematically using AlphaZ. We used the AlphaZ system to automatically generate a C program that implements this improved algorithm. Our work forms the basis for future optimizations and also acts as a case-study for polyhedral equational programming in the real world.

Adviser: Dr. Sanjay Rajopadhye
Co-Adviser: N/A
Non-ECE Member: Dr. A. P. Willem Bohm (Dept. of Computer Science)
Member 3: Dr. Sudeep Pasricha
Addional Members: N/A


Program of Study: