RactIP: fast and accurate prediction of RNA-RNA interaction using integer programming.
BACKGROUND
Considerable attention has been focused on predicting RNA-RNA interaction since it is a key to identifying possible targets of non-coding small RNAs that regulate gene expression post-transcriptionally. A number of computational studies have so far been devoted to predicting joint secondary structures or binding sites under a specific class of interactions. In general, there is a trade-off between range of interaction type and efficiency of a prediction algorithm, and thus efficient computational methods for predicting comprehensive type of interaction are still awaited.


RESULTS
We present RactIP, a fast and accurate prediction method for RNA-RNA interaction of general type using integer programming. RactIP can integrate approximate information on an ensemble of equilibrium joint structures into the objective function of integer programming using posterior internal and external base-paring probabilities. 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.


BACKGROUND
RactIP is implemented in C++, and the source code is available at http://www.ncrna.org/software/ractip/.
Kato
Yuki
Y
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, Japan. ykato@kuicr.kyoto-u.ac.jp
Sato
Kengo
K
Hamada
Michiaki
M
Watanabe
Yoshihide
Y
Asai
Kiyoshi
K
Akutsu
Tatsuya
T
D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D001665:Binding Sites; D008432:Mathematical Computing; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000378:metabolism; D012984:Software
D012313:RNA
RNA. 2004 Oct;10(10):1507-17
15383676
Bioinformatics. 2009 Oct 15;25(20):2646-54
19671692
Biophys J. 2004 Jul;87(1):215-26
15240459
Genome Inform. 2004;15(2):92-101
15706495
Curr Opin Microbiol. 2007 Jun;10(3):262-70
17574901
Bioinformatics. 2009 Jun 15;25(12):i365-73
19478011
Nat Rev Genet. 2001 Dec;2(12):919-29
11733745
Nucleic Acids Res. 2007 Jul;35(Web Server issue):W325-9
17488837
Biochim Biophys Acta. 2002 May 3;1575(1-3):15-25
12020814
Bioinformatics. 2006 May 15;22(10):1177-82
16446276
BMC Bioinformatics. 2007 Jul 27;8:271
17662141
J Mol Biol. 2005 Feb 4;345(5):987-1001
15644199
Bioinformatics. 2010 Jan 15;26(2):175-81
19910305
Nucleic Acids Res. 2003 Jul 1;31(13):3429-31
12824340
J Comput Biol. 2006 Mar;13(2):267-82
16597239
Pac Symp Biocomput. 2010;:98-107
19908362
Bioinformatics. 2008 Dec 15;24(24):2849-56
18940824
Algorithms Mol Biol. 2010 Jan 04;5:5
20047661
BMC Bioinformatics. 2009 Jan 30;10 Suppl 1:S38
19208139
Bioinformatics. 2006 Jul 15;22(14):e90-8
16873527
Algorithms Mol Biol. 2006 Mar 16;1(1):3
16722605
Biochimie. 2002 Sep;84(9):925-44
12458085
Bioinformatics. 2009 Feb 15;25(4):465-73
19095700
Trends Genet. 2002 May;18(5):223-6
12047936