title: RNA-RNA interaction prediction using genetic algorithm.
abstract: BACKGROUND
  RNA-RNA interaction plays an important role in the regulation of gene expression and cell development. In this process, an RNA molecule prohibits the translation of another RNA molecule by establishing stable interactions with it. In the RNA-RNA interaction prediction problem, two RNA sequences are given as inputs and the goal is to find the optimal secondary structure of two RNAs and between them. Some different algorithms have been proposed to predict RNA-RNA interaction structure. However, most of them suffer from high computational time.
  
  
  RESULTS
  In this paper, we introduce a novel genetic algorithm called GRNAs to predict the RNA-RNA interaction. The proposed algorithm is performed on some standard datasets with appropriate accuracy and lower time complexity in comparison to the other state-of-the-art algorithms. In the proposed algorithm, each individual is a secondary structure of two interacting RNAs. The minimum free energy is considered as a fitness function for each individual. In each generation, the algorithm is converged to find the optimal secondary structure (minimum free energy structure) of two interacting RNAs by using crossover and mutation operations.
  
  
  CONCLUSIONS
  This algorithm is properly employed for joint secondary structure prediction. The results achieved on a set of known interacting RNA pairs are compared with the other related algorithms and the effectiveness and validity of the proposed algorithm have been demonstrated. It has been shown that time complexity of the algorithm in each iteration is as efficient as the other approaches.
authors.affiliation: Department of Mathematics, Statistics and Computer Sciences, University of Tehran, Tehran, Iran.
authors.forename: Soheila
authors.initials: S
authors.lastname: Montaseri
authors.affiliation: Faculty of Mathematics & Computer Science, Amirkabir University of Technology, Tehran, Iran ; School of Biological Science, Institute for Research in Fundamental Sciences (IPM), P.O. Box: 19395- 5746, Tehran, Iran.
authors.forename: Fatemeh
authors.initials: F
authors.lastname: Zare-Mirakabad
authors.affiliation: Faculty of Electrical & Computer Engineering, Tarbiat Modares University, Tehran, Iran.
authors.forename: Nasrollah
authors.initials: N
authors.lastname: Moghadam-Charkari
keywords: Fitness function; Minimum free energy; RNA secondary structure
references.citation: RNA. 2004 Oct;10(10):1507-17
references.pmid: 15383676
references.citation: Bioinformatics. 2011 Jul 15;27(14):1934-40
references.pmid: 21593134
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2009 Oct-Dec;6(4):682-8
references.pmid: 19875865
references.citation: Bioinformatics. 2010 Sep 15;26(18):i460-6
references.pmid: 20823308
references.citation: J Comput Biol. 2006 Mar;13(2):267-82
references.pmid: 16597239
references.citation: Bioinformatics. 2011 Jan 15;27(2):211-9
references.pmid: 21088024
references.citation: Bioinformatics. 2006 May 15;22(10):1177-82
references.pmid: 16446276
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: Methods Mol Biol. 2008;453:3-31
references.pmid: 18712296
references.citation: Bioinformatics. 2011 Feb 15;27(4):456-63
references.pmid: 21134894
references.citation: Bioinformatics. 2008 Nov 15;24(22):2657-63
references.pmid: 18434344
references.citation: Algorithms Mol Biol. 2006 Mar 16;1(1):3
references.pmid: 16722605
references.citation: J Theor Biol. 2012 May 7;300:206-11
references.pmid: 22300797
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