Title: Efficient Prediction of RNA Secondary Structure

Speaker: Assoc. Professor Gaurav Sharma, ECE Department, University of Rochester, Rochester, NY

Date/Time: Friday, November 9, 2007, 12:00 pm - 1:00 pm

Location: CSRI Building, Room 90 (Sandia NM)

Brief Abstract: Since structure determines function in biological systems, the determination of molecular structure constitutes one of the fundamental problems in biology. Due to the difficulty and cost associated with experimental procedures for determining structure, computational methods for predicting structure are of research interest. In this talk, we focus on computational techniques for RNA secondary structure prediction - the first step in the hierarchy of RNA structure estimation. Specifically, we consider joint alignment and secondary structure prediction for two homologous RNA sequences. Though the comparative analysis implicit in this process provides significant improvements in accuracy over single sequence prediction methods, in order to obtain reasonable run times and memory, algorithmic implementations for this problem are forced to employ heuristic constraints that reduce computation by restricting the space of permissible alignments and/or structures (i.e. folds). We present a new principled heuristic for determining alignment constraints based on nucleotide alignment and insertion posterior probabilities. We demonstrate that the new constraints possess the desired characteristic of high sensitivity and good specificity (i.e. they allow an overwhelming majority of true aligned positions while simultaneously eliminating improbable alignments). When integrated with Dynalign, a thermodynamic free energy minimization based joint secondary structure prediction method developed within our collaborating group, the new constraints provide a significant reduction in computation time (a factor of 2 over the prior heuristic, for sequences with average length of approximately 120 nucleotides) without compromising structural prediction accuracy. Benchmarks of the method against other publicly available algorithmic implementations for joint RNA secondary structure prediction indicate that the technique yields superior structural prediction accuracy and is much more frugal in its requirement of computational resources. Finally, we outline our continuing research in this direction which utilizes a maximum a posteriori probability formulation for the estimation of RNA secondary structure with the goal of developing turbo-decoding style iterative estimation algorithms with high accuracy and low computational cost.