title: RactIP: fast and accurate prediction of RNA-RNA interaction using integer programming.
abstract: 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/.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, Japan. ykato@kuicr.kyoto-u.ac.jp
authors.forename: Yuki
authors.initials: Y
authors.lastname: Kato
authors.forename: Kengo
authors.initials: K
authors.lastname: Sato
authors.forename: Michiaki
authors.initials: M
authors.lastname: Hamada
authors.forename: Yoshihide
authors.initials: Y
authors.lastname: Watanabe
authors.forename: Kiyoshi
authors.initials: K
authors.lastname: Asai
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: 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
chemical_list: D012313:RNA
references.citation: RNA. 2004 Oct;10(10):1507-17
references.pmid: 15383676
references.citation: Bioinformatics. 2009 Oct 15;25(20):2646-54
references.pmid: 19671692
references.citation: Biophys J. 2004 Jul;87(1):215-26
references.pmid: 15240459
references.citation: Genome Inform. 2004;15(2):92-101
references.pmid: 15706495
references.citation: Curr Opin Microbiol. 2007 Jun;10(3):262-70
references.pmid: 17574901
references.citation: Bioinformatics. 2009 Jun 15;25(12):i365-73
references.pmid: 19478011
references.citation: Nat Rev Genet. 2001 Dec;2(12):919-29
references.pmid: 11733745
references.citation: Nucleic Acids Res. 2007 Jul;35(Web Server issue):W325-9
references.pmid: 17488837
references.citation: Biochim Biophys Acta. 2002 May 3;1575(1-3):15-25
references.pmid: 12020814
references.citation: Bioinformatics. 2006 May 15;22(10):1177-82
references.pmid: 16446276
references.citation: BMC Bioinformatics. 2007 Jul 27;8:271
references.pmid: 17662141
references.citation: J Mol Biol. 2005 Feb 4;345(5):987-1001
references.pmid: 15644199
references.citation: Bioinformatics. 2010 Jan 15;26(2):175-81
references.pmid: 19910305
references.citation: Nucleic Acids Res. 2003 Jul 1;31(13):3429-31
references.pmid: 12824340
references.citation: J Comput Biol. 2006 Mar;13(2):267-82
references.pmid: 16597239
references.citation: Pac Symp Biocomput. 2010;:98-107
references.pmid: 19908362
references.citation: Bioinformatics. 2008 Dec 15;24(24):2849-56
references.pmid: 18940824
references.citation: Algorithms Mol Biol. 2010 Jan 04;5:5
references.pmid: 20047661
references.citation: BMC Bioinformatics. 2009 Jan 30;10 Suppl 1:S38
references.pmid: 19208139
references.citation: Bioinformatics. 2006 Jul 15;22(14):e90-8
references.pmid: 16873527
references.citation: Algorithms Mol Biol. 2006 Mar 16;1(1):3
references.pmid: 16722605
references.citation: Biochimie. 2002 Sep;84(9):925-44
references.pmid: 12458085
references.citation: Bioinformatics. 2009 Feb 15;25(4):465-73
references.pmid: 19095700
references.citation: Trends Genet. 2002 May;18(5):223-6
references.pmid: 12047936