Bioinformatický seminár

Tue 17 Jan. 2012, 17:20
I-9

Title: Sato et al. IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming
Speaker: Martin Macko, Martin Višňovec

MOTIVATION: Pseudoknots found in secondary structures of a number of
functional RNAs play various roles in biological processes. Recent methods
for predicting RNA secondary structures cover certain classes of
pseudoknotted structures, but only a few of them achieve satisfying
predictions in terms of both speed and accuracy. RESULTS: We propose
IPknot, a novel computational method for predicting RNA secondary
structures with pseudoknots based on maximizing expected accuracy of a
predicted structure. IPknot decomposes a pseudoknotted structure into a
set of pseudoknot-free substructures and approximates a base-pairing
probability distribution that considers pseudoknots, leading to the
capability of modeling a wide class of pseudoknots and running quite fast.
In addition, we propose a heuristic algorithm for refining base-paring
probabilities to improve the prediction accuracy of IPknot. The problem of
maximizing expected accuracy is solved by using integer programming with
threshold cut. We also extend IPknot so that it can predict the consensus
secondary structure with pseudoknots when a multiple sequence alignment is
given. IPknot is validated through extensive experiments on various
datasets, showing that IPknot achieves better prediction accuracy and
faster running time as compared with several competitive prediction
methods. AVAILABILITY: The program of IPknot is available at
http://www.ncrna.org/software/ipknot/. IPknot is also available as a web
server at http://rna.naist.jp/ipknot/. CONTACT: satoken@k.u-tokyo.ac.jp;
ykato@is.naist.jp SUPPLEMENTARY INFORMATION: Supplementary data are
available at Bioinformatics online.