# A Novel Framework Based on ACO and PSO for RNA Secondary Structure Prediction

Authors: Gang Wang; Wen-yi Zhang; Qiao Ning; Hui-ling Chen
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Prediction of RNA structure is a useful process for creating new drugs and understanding genetic diseases. In this paper, we proposed a particle swarm optimization (PSO) and ant colony optimization (ACO) based framework (PAF) for RNA secondary structure prediction. PAF consists of crucial stem searching (CSS) and global sequence building (GSB). In CSS, a modified ACO (MACO) is used to search the crucial stems, and then a set of stems are generated. In GSB, we used a modified PSO (MPSO) to construct all the stems in one sequence. We evaluated the performance of PAF on ten sequences, which have length from 122 to 1494. We also compared the performance of PAF with the results obtained from six existing well-known methods, SARNA-Predict, RnaPredict, ACRNA, PSOfold, IPSO, and mfold. The comparison results show that PAF could not only predict structures with higher accuracy rate but also find crucial stems.


---

## Body

## 1. Introduction

RNA functions as an information carrier, catalyst, and regulatory element, perhaps reflecting its importance in the earliest stages of evolution. The structures of RNAs provide insight into the mechanisms behind these functions. Determining sequence is the first step in determining structure, and many billions of nucleotide sequences are now known. The second step is determining secondary structure, and relatively few classes of RNAs currently have known secondary structures [1]. The RNA secondary structure prediction problem is a critical one in molecular biology. Secondary structure as well as tertiary structure can be determined by X-ray crystallography and Nuclear Magnetic Resonance (NMR) spectroscopy. Data analysis tools used for prediction of RNA structure are mainly based on dynamic programming [2]. Recently, the metaheuristic methods are widely used to predict RNA secondary structure. These methods generally include genetic algorithm (GA) [3], particle swarm optimization (PSO) [4], ant colony optimization (ACO) [5], and simulated annealing (SA) [6]. The state-of-the-art methods are introduced as follows.For SA. Shapiro and Wu [7] later modified the algorithm by introducing an annealing mutation operator. Tsang and Wiese [8] presented SARNA-Predict, the permutation-based algorithm for RNA secondary structure prediction based on SA with a simple thermodynamic model and studied mainly its convergence behavior. A performance evaluation of SARNA-Predict in terms of prediction accuracy was made via comparison with eight state-of-the-art RNA prediction algorithms. The results presented in this paper demonstrate that SARNA-Predict can outperform other state-of-the-art algorithms in terms of prediction accuracy. Furthermore, there is substantial improvement of prediction accuracy by incorporating a more sophisticated thermodynamic model.For GA. Benedetti and Morosetti [9] compared the accuracy of an EA against known RNA structures with the objective of finding optimal and suboptimal structures that were similar. Shapiro et al. [10] modified their EA to study folding pathways using a massively parallel genetic algorithm. Wiese et al. designed a serial EA, RnaPredict [11], which encodes RNA secondary structures as permutations. RnaPredict was parallelized via a coarse-grained distributed EA for RNA secondary structure prediction [12].For ACO. Yu et al. [13] put forward ACRNA based on ACO for RNA secondary structure prediction. For a given RNA sequence, the set of all possible stems is obtained, and the energy of each stem is calculated and stored at the initial stage. Furthermore, a more realistic formula is used to compute the energy of multibranch loop in the following iteration. Then a folding pathway is simulated, including such processes as construction of the heuristic information, the rule of initializing the pheromone, the mechanism of choosing the initial and next stem, and the strategy of updating the pheromone between two different stems.For PSO. Geis and Middendorf [14] introduced HelixPSO for finding minimum energy RNA secondary structures. Neethling and Engelbrecht [15] proposed a set-based Particle Swarm Optimization algorithm to optimize the structure of an RNA molecule, using an advanced thermodynamic model. Liu et al. [16] proposed an improved PSO (IPSO). The authors designed an efficient objective function according to the minimum free energy, the number of selected stems, and the average length of selected stems. A promising experimental result was obtained, and the effectiveness and practicability of IPSO for RNA secondary structure prediction was shown. Xing et al. [17, 18] proposed PSOfold based on IPSO. An adaptive parameter controller of PSO based on fuzzy logic is used to improve the balance between exploration and exploitation. Solution conversion strategy (SCS) is designed to enhance the PSO performance in discrete problem such as stem combination.The metaheuristic methods [19, 20] mentioned previously only paid attention to structure of the sequence but ignored the searching capability of algorithm. PSOfold is our previous work with an attempt to enhance the searching range in PSO, but the crucial stems are not considered. In this paper, we proposed PAF to improve the exploration ability and focused on the influence of the crucial stems.The main contributions of this paper are described as follows.(1)
A framework, namely, PAF, was proposed for RNA secondary structure prediction, which includes CSS and GSB.(2)
In CSS, MACO was proposed to search the crucial stems.(3)
In GSB, MPSO was designed to construct all the stems in one sequence.The rest of the paper is organized as follows. Section 2 briefly introduces the theory of ACO and PSO. In Section 3, we present the proposed PAF framework and describe the implementation of CSS and GSB. In Section 4, the experiment results on various public sequences are discussed. Finally, we draw the conclusions of this paper in Section 5.


## 2. Basic Theory

### 2.1. ACO

ACO algorithm is biologically inspired from the behavior of colonies of real ants, and in particular how they forage for food. ACO has been formalized into a metaheuristic for combinatorial optimization problems by Dorigo and coworkers [21].In ACO, an antk being in node i chooses the next node j with a probability given by the random proportional rule defined as follows [22].(a) State Transition Rule. Consider
(1)Pij(t)={[τij(t)]·[ηij]β∑j∈Iik[τij(t)]·[ηij]βifj∈Iik,0otherwise,
where Iik is its feasible neighborhood. The feasible neighborhood excludes nodes already visited in the partial tour of ant i, and it may be further restricted to a candidate set of the nearest neighbors of a city i. Once an ant has visited all nodes, it returns to its starting node.(b) State Updating Rule. After all ants have completed their solutions, pheromone evaporation on all nodes is triggered according to (2). The pheromone on each edge is updated according to the following equation:
(2)τij(t+1)=(1-ρ)·τij(t)+∑k=1NΔτijk(t),
where m is the number of ants at each iteration and ρ∈(0,1) is the pheromone evaporation rate. Consider
(3)Δτijk={QLkifτij∈tourdonebyantk,0otherwise,
where Lk denotes the tour length and Q is a predefined constant.


### 2.2. PSO

PSO originated from the simulation of social behavior of birds in a flock [23, 24]. In PSO, each particle flies in the search space with a velocity adjusted by its own flying memory and its companion’s flying experience. All particles have objective function values which are decided by a fitness function. Consider the following:
(4)vidt=w×vidt-1+c1×r1(pidt-xidt)+c2×r2(pgdt-xidt),d=1,2,3,4,…,D,
where c1 indicates the cognition learning factor, c2 indicates the social learning factor, and r1 and r2 are random numbers uniformly distributed in U(0,1). Each particle then moves to a new potential solution based on the following equation:
(5)xidt+1=xidt+vidt,d=1,2,…,D.Kennedy and Eberhart [25] proposed a binary PSO in which a particle moves in a state space restricted to 0 and 1 on each dimension, in terms of the changes in probabilities that a bit will be in one state or the other. Consider the following:
(6)xid={1,rand()<S(vi,d),0,otherwise,S(v)=11+e-v.The functionS(v) is a sigmoid limiting transformation and rand() is a random number selected from a uniform distribution in [0.0,1.0].


## 2.1. ACO

ACO algorithm is biologically inspired from the behavior of colonies of real ants, and in particular how they forage for food. ACO has been formalized into a metaheuristic for combinatorial optimization problems by Dorigo and coworkers [21].In ACO, an antk being in node i chooses the next node j with a probability given by the random proportional rule defined as follows [22].(a) State Transition Rule. Consider
(1)Pij(t)={[τij(t)]·[ηij]β∑j∈Iik[τij(t)]·[ηij]βifj∈Iik,0otherwise,
where Iik is its feasible neighborhood. The feasible neighborhood excludes nodes already visited in the partial tour of ant i, and it may be further restricted to a candidate set of the nearest neighbors of a city i. Once an ant has visited all nodes, it returns to its starting node.(b) State Updating Rule. After all ants have completed their solutions, pheromone evaporation on all nodes is triggered according to (2). The pheromone on each edge is updated according to the following equation:
(2)τij(t+1)=(1-ρ)·τij(t)+∑k=1NΔτijk(t),
where m is the number of ants at each iteration and ρ∈(0,1) is the pheromone evaporation rate. Consider
(3)Δτijk={QLkifτij∈tourdonebyantk,0otherwise,
where Lk denotes the tour length and Q is a predefined constant.


## 2.2. PSO

PSO originated from the simulation of social behavior of birds in a flock [23, 24]. In PSO, each particle flies in the search space with a velocity adjusted by its own flying memory and its companion’s flying experience. All particles have objective function values which are decided by a fitness function. Consider the following:
(4)vidt=w×vidt-1+c1×r1(pidt-xidt)+c2×r2(pgdt-xidt),d=1,2,3,4,…,D,
where c1 indicates the cognition learning factor, c2 indicates the social learning factor, and r1 and r2 are random numbers uniformly distributed in U(0,1). Each particle then moves to a new potential solution based on the following equation:
(5)xidt+1=xidt+vidt,d=1,2,…,D.Kennedy and Eberhart [25] proposed a binary PSO in which a particle moves in a state space restricted to 0 and 1 on each dimension, in terms of the changes in probabilities that a bit will be in one state or the other. Consider the following:
(6)xid={1,rand()<S(vi,d),0,otherwise,S(v)=11+e-v.The functionS(v) is a sigmoid limiting transformation and rand() is a random number selected from a uniform distribution in [0.0,1.0].


## 3. PAF

### 3.1. CSS

#### 3.1.1. MACO

(
1) State Transition Rule. The task of each ant is to build a set of stems. The ants find an RNA secondary structure via a probabilistic decision rule to move through adjacent states. An ant selects a stem as follows:
(7)Pi={[τi]α[ηi]β∑j∈Iik[τj]α[ηj]βifj∈Iik,0otherwise,
where α and β are the regulatory factors, τi is the amount of pheromone trail on stem i, ηi is the priori available heuristic information, and Iik is the remaining stems.(2) State Update Rule. The pheromone trails are updated according to (8) and (9). Consider
(8)τ=(1-ρ)·τi+∑k=1nΔτik,
where ρ is the pheromone trail evaporation rate and τi is the quantity per unit of length of the trail substance that is laid on stem i by the kth ant. Also,
(9)Δτik={Energyifkuses  stemiin  its  tour0otherwise,
where Energy represents the quality of an ant’s solution. If stem i is not included, the zero is returned.


#### 3.1.2. Algorithm of MACO

See Algorithm1.Algorithm 1
Initialize the parameters of MACO
Randomly initialize the solutions for all the ants
While current number of iterations < Max iteration
For each ant in the population
For each stem
Decide whether to select current stem according to (7)
End for
Evaluate the solution according to the energy.
End for
For each stem in the set
Update the pheromones according to (8) and (9)
End for
End while


### 3.2. GSB

#### 3.2.1. MPSO

MPSO was modified based on our previous studies IPSO [16] and PSOfold [18] which could predict the RNA secondary structure with excellent performance. The objective function is improved according to the size of stem and the number of pseudoknots. Consider the following:
(10)fi=aEi-b[∑j=1Nδ(j)P]-c[∑k=1Mφ(k)/L+SW],
where a, b, c is the weight; Ei is the free energy for the secondary structure in the ith particle; δ is the number of pairs of the jth stem; P is the length of possible pairs; φ is the size of stem k which is higher than 4; M is the number of selected stems; L is the total number of stems which are higher than 4; S is the size of pseudoknots; W is the size of possible pairs.


#### 3.2.2. Algorithm of MPSO

See Algorithm2.Algorithm 2
Initialize all the parameters of MPSO
While current number of iterations < Max iteration
For each particle
Update its velocity
Update its position
Restrict position and velocity
Calculate fitness and Update local best
End for
Update the global best
Turn the parameters of MPSO via fuzzy logic controllers
End while


## 3.1. CSS

### 3.1.1. MACO

(
1) State Transition Rule. The task of each ant is to build a set of stems. The ants find an RNA secondary structure via a probabilistic decision rule to move through adjacent states. An ant selects a stem as follows:
(7)Pi={[τi]α[ηi]β∑j∈Iik[τj]α[ηj]βifj∈Iik,0otherwise,
where α and β are the regulatory factors, τi is the amount of pheromone trail on stem i, ηi is the priori available heuristic information, and Iik is the remaining stems.(2) State Update Rule. The pheromone trails are updated according to (8) and (9). Consider
(8)τ=(1-ρ)·τi+∑k=1nΔτik,
where ρ is the pheromone trail evaporation rate and τi is the quantity per unit of length of the trail substance that is laid on stem i by the kth ant. Also,
(9)Δτik={Energyifkuses  stemiin  its  tour0otherwise,
where Energy represents the quality of an ant’s solution. If stem i is not included, the zero is returned.


### 3.1.2. Algorithm of MACO

See Algorithm1.Algorithm 1
Initialize the parameters of MACO
Randomly initialize the solutions for all the ants
While current number of iterations < Max iteration
For each ant in the population
For each stem
Decide whether to select current stem according to (7)
End for
Evaluate the solution according to the energy.
End for
For each stem in the set
Update the pheromones according to (8) and (9)
End for
End while


## 3.1.1. MACO

(
1) State Transition Rule. The task of each ant is to build a set of stems. The ants find an RNA secondary structure via a probabilistic decision rule to move through adjacent states. An ant selects a stem as follows:
(7)Pi={[τi]α[ηi]β∑j∈Iik[τj]α[ηj]βifj∈Iik,0otherwise,
where α and β are the regulatory factors, τi is the amount of pheromone trail on stem i, ηi is the priori available heuristic information, and Iik is the remaining stems.(2) State Update Rule. The pheromone trails are updated according to (8) and (9). Consider
(8)τ=(1-ρ)·τi+∑k=1nΔτik,
where ρ is the pheromone trail evaporation rate and τi is the quantity per unit of length of the trail substance that is laid on stem i by the kth ant. Also,
(9)Δτik={Energyifkuses  stemiin  its  tour0otherwise,
where Energy represents the quality of an ant’s solution. If stem i is not included, the zero is returned.


## 3.1.2. Algorithm of MACO

See Algorithm1.Algorithm 1
Initialize the parameters of MACO
Randomly initialize the solutions for all the ants
While current number of iterations < Max iteration
For each ant in the population
For each stem
Decide whether to select current stem according to (7)
End for
Evaluate the solution according to the energy.
End for
For each stem in the set
Update the pheromones according to (8) and (9)
End for
End while


## 3.2. GSB

### 3.2.1. MPSO

MPSO was modified based on our previous studies IPSO [16] and PSOfold [18] which could predict the RNA secondary structure with excellent performance. The objective function is improved according to the size of stem and the number of pseudoknots. Consider the following:
(10)fi=aEi-b[∑j=1Nδ(j)P]-c[∑k=1Mφ(k)/L+SW],
where a, b, c is the weight; Ei is the free energy for the secondary structure in the ith particle; δ is the number of pairs of the jth stem; P is the length of possible pairs; φ is the size of stem k which is higher than 4; M is the number of selected stems; L is the total number of stems which are higher than 4; S is the size of pseudoknots; W is the size of possible pairs.


### 3.2.2. Algorithm of MPSO

See Algorithm2.Algorithm 2
Initialize all the parameters of MPSO
While current number of iterations < Max iteration
For each particle
Update its velocity
Update its position
Restrict position and velocity
Calculate fitness and Update local best
End for
Update the global best
Turn the parameters of MPSO via fuzzy logic controllers
End while


## 3.2.1. MPSO

MPSO was modified based on our previous studies IPSO [16] and PSOfold [18] which could predict the RNA secondary structure with excellent performance. The objective function is improved according to the size of stem and the number of pseudoknots. Consider the following:
(10)fi=aEi-b[∑j=1Nδ(j)P]-c[∑k=1Mφ(k)/L+SW],
where a, b, c is the weight; Ei is the free energy for the secondary structure in the ith particle; δ is the number of pairs of the jth stem; P is the length of possible pairs; φ is the size of stem k which is higher than 4; M is the number of selected stems; L is the total number of stems which are higher than 4; S is the size of pseudoknots; W is the size of possible pairs.


## 3.2.2. Algorithm of MPSO

See Algorithm2.Algorithm 2
Initialize all the parameters of MPSO
While current number of iterations < Max iteration
For each particle
Update its velocity
Update its position
Restrict position and velocity
Calculate fitness and Update local best
End for
Update the global best
Turn the parameters of MPSO via fuzzy logic controllers
End while


## 4. Results

The parameter details of ACRNA are number of ants = 100, number of iterations = 600,ρ = 0.2, α = 1, and β = 1. For IPSO, number of particles = 100, number of iterations = 600, ω = 0.9, c1 = 2, and c2 = 2. For PSOfold, number of particles = 100, number of iterations = 600, ω = 0.9, c1 = 2, and c2 = 2. For CSS, number of ants = 100, number of iterations = 600, ρ=0.2, α=1, and β=1. For GSB, number of particles = 100, number of iterations = 600, ω=0.9, c1 = 2, and c2=2. To generate the mfold results presented here, the mfold Web server version 3.1 was used with default settings. One noteworthy setting is the percentage of suboptimality. This percentage allows the user to control the number of suboptimal structures predicted by mfold. In this experiment, the value was set to return the 5 percent lowest energy structures.The measures used for prediction accuracy on the majority of documents currently are sensitivity, specificity, andF-measure. In RNA secondary structure prediction, TP (true positive) indicates the number of base pairs predicted correctly; FN (false negative) denotes the number of base pairs which existed in real structure but were not predicted correctly; FP (false positive) represents the number of base pairs which existed in no real structure but was mistakenly predicted; TN (true negative) stands for the number of base pairs which were not matched and predicted correctly. The TN is rarely used in actual measurement because it is generally much larger than TP, FN, and FP. Sensitivity (Se) means the percentage of all base pairs which was correctly predicted in the real structure; specific (Sp) refers to the percentage of all predicted base pairs which was correctly predicted. The general prediction is very difficult for both and is always biased in favor of one side. A metric that combines both the specificity and sensitivity measures into one is F-measure; it can be used as a single performance measure for a predictor. The main result of the paper will be concluded by the sensitivity and specificity [18]. The specific formula is as follows:
(11)Se=TPTP+FN,Sp=TPTP+FP,F=2×specificity×sensitivityspecificity+sensitivity.Ten sequences from the comparative RNA website are selected for evaluation of the proposed method, and the details of the sequence are described in Table1. For these sequences the natural secondary structures are also available from the comparative RNA website. These sequences were chosen as they represent different sequence lengths and come from various genomes of organisms that are exposed to a range of physiological conditions. They represent four RNA classes: 5S rRNA, Group I intron 16S rRNA, 16S rRNA, and Group I intron 23S rRNA. Due to space constraints in some tables, we refer to these specific RNA sequences by an abbreviation of the name of the organism from which they originated [18].Table 1
RNA sequence details.
Organism
Accession number
RNA class
Length
Base pairs in known structure
Drosophila virilis
X05914
16S rRNA
784
233
Xenopus laevis
M27605
16S rRNA
945
251
Haloarcula marismortui
AF034620
5S rRNA
122
38
Aureoumbra lagunensis
U40258
Group I intron, 16S rRNA
468
113
Metahizium anisopliae var.
AF197120
Group I intron, 23S rRNA
394
120
Hildenbrandia rubra
L19345
Group I intron, 16S rRNA
543
138
Acanthamoeba griffini
U02540
Group I intron, 16S rRNA
556
131
Homo sapiens
J01415
16S rRNA
954
266
Ailurus fulgens
Y08511
16S rRNA
964
265
Sulfolobus acidocaldarius
D14876
16S rRNA
1494
468Table2 shows the comparative results of the highest matching base pair structures between PAF and mfold in regard to sensitivity, specificity, and F-measure. PAF predicts fewer base pairs on 8 sequences. PAF obtained higher TP in 7 cases and lower FP in all cases. The values FN predicted by PAF are also lower than mfold in 7 out of 10 cases. For sensitivity, specificity, and F-measure, PAF won in 7, 10, and 10 cases, respectively. Generally, PAF performs significantly better than mfold with respect to sensitivity, specificity, and F-measure.Table 2
A comparison of the highest matching base pair structures from PAF and mfold in terms of sensitivity, specificity, andF-measure.
Sequence
Known bps
Predicted bps
TP
FP
FN
Sensitivity
Specificity
F-measure
PAF
mfold
PAF
mfold
PAF
mfold
PAF
mfold
PAF
mfold
PAF
mfold
PAF
mfold
D. virilis
233
247
252
103
82
144
170
130
151
44.2
35.2
41.7
32.5
42.9
33.8
X. laevis
251
235
245
116
113
119
132
135
138
46.2
45.0
49.4
46.1
47.7
45.6
H. marismortui
38
31
34
28
29
3
5
10
9
73.7
76.3
90.3
85.3
81.2
80.6
A. lagunensis
113
124
133
85
74
39
59
28
39
75.2
65.5
68.6
55.6
71.7
60.2
M. anisopliae var.
120
110
116
91
92
19
24
29
28
75.8
76.7
82.7
79.3
79.1
78.0
H. rubra
138
141
167
82
83
59
84
56
55
59.4
60.1
58.1
49.7
58.8
54.4
A. griffini
131
160
174
102
95
58
79
29
36
77.9
72.5
63.8
54.6
70.1
62.3
H. sapiens
266
260
258
124
95
136
163
142
171
46.6
35.7
47.7
36.8
47.2
36.3
A. fulgens
265
249
241
99
74
150
167
166
191
37.4
27.9
39.8
30.7
38.5
29.2
S. acidocaldarius
468
483
496
281
271
202
225
187
197
60
57.9
58.1
54.6
59.1
56.2
Averages
202.3
204
211.6
111.1
100.8
92.9
110.8
91.2
101.5
59.64
55.28
60.02
52.52
59.63
53.66Table3 shows a more detailed analysis of comparing the highest matching base pair structures from SARNA-Predict, RnaPredict, ACRNA, PAF, PSOfold, and mfold according to sensitivity and specificity. The results generated by SARNA-Predict and RnaPredict were taken from the literature [8, 11]. From Table 3, it can be seen that PAF gets better sensitivity on 6 sequences and predicts higher specificity in 8 cases. SARNA-Predict gets better results in 2 cases in terms of sensitivity and in 2 cases with regard to specificity. ACRNA wins on 1 sequence for sensitivity and on 1 sequence for specificity. PSOfold and mfold obtained better sensitivity on one sequence and two sequences, respectively. Among the six methods, PAF gets the best results in most cases. From another point of view, the average performance of PAF on sensitivity and specificity exceeds that of the other methods. It is demonstrated that PAF is significantly superior to the other 5 methods.Table 3
A comparison of the highest matching base pair structures from SARNA-predict, RnaPredict, ACRNA, PAF, PSOfold, and mfold in terms of sensitivity and specificity.
Sequence
Length
SARNA-Predict
RnaPredict
ACRNA
PAF
PSOfold
mfold
Se
Sp
Se
Sp
Se
Sp
Se
Sp
Se
Sp
Se
Sp
D. virilis
784
42.1
42.2
27.9
26.9
27.9
26.9
44.2
41.7
42.9
41.5
35.2
32.5
X. laevis
945
46.2
48.9
37.1
38.8
45.8
46.9
46.2
49.4
45.6
48.5
45.0
46.1
H. marismortui
122
71.1
90.0
71.1
90.0
76.3
78.4
73.7
90.3
71.1
87.1
76.3
85.3
A. lagunensis
468
74.3
64.6
60.2
51.9
63.7
54.1
75.2
68.6
76.1
64.7
65.5
55.6
M. anisopliae var.
394
63.3
65.0
62.5
62.0
63.3
65.0
75.8
82.7
75.0
74.4
76.7
79.3
H. rubra
543
64.5
56.7
57.2
49.1
58.0
47.9
59.4
58.1
58.0
53.0
60.1
49.7
A. griffini
556
74.0
58.8
61.8
50.3
73.3
55.2
77.9
63.8
76.3
59.2
72.5
54.6
H. sapiens
954
44.7
48.8
33.5
35.6
44.7
48.8
46.6
47.7
44.4
47.2
35.7
36.8
A. fulgens
964
35.1
38.9
30.9
33.9
34.3
38.7
37.4
39.8
35.1
39.6
27.9
30.7
S. acidocaldarius
1494
52.4
51.9
52.4
51.9
58.3
58.0
60
58.1
58.3
58.0
57.9
54.6
Averages
722.4
56.77
56.58
49.46
49.04
54.56
51.99
59.64
60.02
58.28
57.32
55.28
52.52In order to validate the stability of the proposed method, we ran ACRNA, IPSO, PAF, and PSOfold ten times and calculated the average highest matching base pair structures of each algorithm in terms of sensitivity and specificity. The detail results are shown in Table4. From Table 4, it is easy to see that PAF obtains best sensitivity and specificity on 8 sequences and on 7 sequences, respectively. Thus, this proves that the proposed method performs stably on multiple sequences, considerably surpassing the other methods. The convergence progress is shown in Figures 1, 2, and 3. From the figures, we can clearly see that the proposed method could avoid trapping in the local optimum during the iterations. This is because the crucial stems lead the algorithm to the right direction.Table 4
Average sensitivity and specificity via ACRNA, IPSO, PAF, and PSOfold.
Sequence
Length
ACRNA
IPSO
PAF
PSOfold
se
sp
se
sp
se
sp
se
sp
D. virilis
784
25.1
24.5
27.8
27.1
34.1
30.4
32.6
29.9
X. laevis
945
40.2
38.8
38.7
36.7
43.8
41.5
42.4
40.1
H. marismortui
122
70.5
73.6
67.8
68.1
70.6
76.0
69.2
75.4
A. lagunensis
468
61.3
52.6
60.5
51.8
62.4
53.8
63.9
52.6
M. anisopliae var.
394
60.9
63.5
57.1
56.2
66.5
64.1
65.1
63.3
H. rubra
543
56.2
48.8
50.1
41.3
56.9
47.8
54.4
47.8
A. griffini
556
67.1
54.1
63.2
47.3
69.2
52.9
68.5
54.5
H. sapiens
954
34.1
32.1
31.9
33.5
35.8
34.9
32.4
33.3
A. fulgens
964
31.1
30.2
30.2
32.5
34.2
31.8
32.6
31.8
S. acidocaldarius
1494
56.0
55.4
52.5
51.4
54.5
56.3
56.5
55.9
Averages
722.4
50.25
47.36
47.98
44.59
52.8
48.95
51.76
48.46Figure 1
Average best sensitivity by running the algorithms 10 times onA. griffini.Figure 2
Average best sensitivity by running the algorithms 10 times onH. rubra.Figure 3
Average best sensitivity by running the algorithms 10 times onX. laevis.


## 5. Conclusion

In this paper, a framework, PAF, was proposed for RNA secondary structure prediction, which consists of CSS and GSB. In order to preserve crucial structures, MACO in CSS is proposed to find the important stems. MPSO in GSB is developed to generate predicted structures in order to save searching spaces. The experimental results show that the performance of the proposed method is significantly better than those of the other metaheuristic methods in terms of sensitivity, specificity, andF-measure. We will try to enhance the performance of convergence and reduce time complexity in the future.



---

*Source: 796304-2013-09-11.xml*