Date |
June 15, 2011 |
Speaker |
Dr. Kengo Sato, Department of Biosciences and Informatics, Keio University |
Title |
Fast and accurate predictions of RNA structures using integer programming |
Abstract |
Considerable attention has been paid to the functions of RNAs,
especially those of regulatory non-coding RNAs. It is widely believed
that there is a strong correlation between the 3D structure of an RNA
molecule and its function. A set of base pairs is called a secondary
structure, which shapes the substructure of the 3D structure. Since
experimental determination of RNA 3D structures is difficult and their
structures are hierarchical, secondary structure prediction provides a
major key to elucidating the potential functions of RNAs. In the
former part of the talk, we present IPknot, a novel computational
method for predicting RNA secondary structures with pseudoknots based
on maximizing expected accuracy of a predicted structure. Pseudoknots,
found in secondary structures of a number of functional RNAs, play
various roles in biological processes. The problem of maximizing
expected accuracy is solved by using integer programming with
threshold cut. IPknot is validated through extensive experiments on
various data sets, indicating that IPknot achieves sufficiently better
prediction accuracy and faster running time as compared with several
competitive prediction methods. The latter part of the talk focuses on
predicting RNA-RNA interaction, leading to identifying possible
targets of non-coding small RNAs that regulate gene expression
post-transcriptionally. We present RactIP, a fast and accurate
prediction method for RNA-RNA interaction of general type using
integer programming with threshold cut similar to the methodology of
IPknot. Experimental results on real interaction data show that
prediction accuracy of RactIP is at least comparable to that of
several state-of-the-art methods for RNA-RNA interaction
prediction. Moreover, we demonstrate that RactIP can run incomparably
faster than competitive methods for predicting joint secondary
structures. |
|