Repository logo
 

RNA secondary structure prediction using AlphaZ

Date

2010

Authors

Pathan, Tanveer, author
Rajopadhye, Sanjay, advisor
Pasricha, Sudeep, committee member
Bohm, A. P. Willem, committee member

Journal Title

Journal ISSN

Volume Title

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(N4). We show that the optimized O(N3) 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.

Description

Rights Access

Subject

Citation

Associated Publications