Turbo-decoding of RNA Secondary Structure
Mon., Apr 23, 2012
2:00 - 3:00 PM
521 Cory (Hogan room)
We present a turbo-decoding framework for jointly estimating secondary structure of noncoding RNA (ncRNA) from multiple homologs, a problem of significance in Biology. The framework closely parallels and draws motivation from turbo-decoding for error correction in communications: In the communications setting, a single message stream is coded by two encoders separated by an interleaver. In the biological setting, Nature encodes the same secondary structure in multiple homologous ncRNA sequences occurring in different species, preserving topological structure essential for biological function. In both settings, a jointly optimal decoding of the encoded information is preferable because it offers significant improvements in accuracy compared with individual decodings. Furthermore, in both scenarios, exact jointly optimal decoding is stymied by computational complexity, which is exponential in the interleaver length for the communications setting and exponential in the number of homologs for the biological setting. In the communications setting, the turbo-decoding algorithm is now understood as an approximation to optimal joint decoding. We motivate and develop a similar framework for the ncRNA structure estimation problem and present the TurboFold iterative algorithm for computationally efficient joint estimation of ncRNA structure from multiple homologs. TurboFold mirrors the turbo decoding algorithm for the communications setting, posing the problem of predicting ncRNA structure from multiple homologs as the estimation of a posteriori base pairing probabilities, which are then iteratively estimated, each iteration propagating information to the next and providing improved accuracy. We also highlight the significance of the ncRNA structure in medicine and biology for both fundamental understanding and for the design of pharmaceutics for the wide variety of diseases and syndromes in which ncRNAs have been implicated.

Gaurav Sharma is an associate professor at the Electrical and Computer Engineering Department at the University of Rochester, where, from 2008-2010, he also served as the Director for the Center for Emerging and Innovative Science (CEIS), a New York state funded center located at the University of Rochester chartered with promoting economic development through university-industry technology transfer. He received the PhD degree in Electrical and Computer engineering from North Carolina State University, Raleigh in 1996. From 1993 through 2003, he was with the Xerox Innovation group in Webster, NY, most recently in the position of Principal Scientist and Project Leader. His research interests include color science and imaging, multimedia/print security, and bioinformatics. He is the Editor-in-Chief for the Journal of Electronic Imaging and the editor of the Digital Color Imaging Handbook published by CRC press in 2003. He serves as a Technical Program co-chair for ICIP 2012 and is the Symposium Chair for the 2013 Electronic Imaging symposium. He has also served as an associate editor for the Journal of Electronic Imaging, the IEEE Transactions on Image Processing, and for the IEEE Transactions on Information Forensics and Security. Dr. Sharma is a senior member of the IEEE, a member IS&T and has been elected to Sigma Xi, Phi Kappa Phi, and Pi Mu Epsilon. He is a member of the Image, Video, and Multi-dimensional Signal Processing (IVMSP) and the Information Forensics and Security (IFS) technical committees of the IEEE Signal Processing Society and served as the Chair for the former committee in 2010-11. In recognition of his research contributions, he received an IEEE Region I technical innovation award in 2008.
UC Berkeley Networking
Ashwin Pananjady and Orhan Ocal
Last Modification Date: Wednesday, February 10, 2016