A Novel Hybridization Of ABC With CBR Biology Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The RNA molecule is substantiated to play important functions in living cells. The class of RNA with pseudoknots, has essential roles in designing remedies for many virus diseases in therapeutic domain. These various useful functions can be inferred from RNA secondary structure with pseudoknots. Many computational intensive efforts have been emerged with the aim of predicting the pseudoknotted RNA secondary structure. The computational approaches are much promising to predict the RNA structure. The reason behind this is that, the experimental methods for determining the RNA tertiary structure are difficult, time-consuming and tedious. In this paper, we introduce ABCRna, a novel method for predicting RNA secondary structure with pseudoknots. This method combines heuristic-based KnotSeeker with a thermodynamic programming model, UNAFold. ABCRna is a hybrid swarm-based intelligence method inspired by the secreting honey process in natural honey-bee colonies. The novel aspect of this method is adapting Case-Based Reasoning (CBR) and knowledge base, two prominent Artificial Intelligence techniques. They are employed particularly to enhance the quality performance of the proposed method. The CBR provides an intelligent decision, which results more accurate predicted RNA structure. This modified ABCRna method is tested using different kinds of RNA sequences to prove and compare its efficiency against other pseudoknotted RNA predicted methods in the literature. The proposed ABCRna algorithm performs faster with significant improvement in accuracy, even for long RNA sequences.

Keywords-RNA secondary structure; pseudoknots; Case-Bases Reasoning; Artificial Bee Colony (ABC) algorithm.


Ribonucleic acid or (RNA) is one of the nucleic acids, which plays diverse roles and functions. Basically, one kind of RNA is the messenger RNA (mRNA). It works as an intermediary in carrying the genetic information code from DNA to make proteins [1]. This carried genetic code is used in the natural process for synthesizing proteins in living cell. However, the recent biological studies confirmed that there are other kinds of RNAs, which play various useful roles [2]. The latest discovered functions of RNA molecule, include: splicing introns, catalyst for reaction and a regular in cellular activities [3, 4]. Predicting the RNA structure is the key to determine and scrutinize the active functions of RNA molecule. This fact is emphasized by central dogma in biochemistry and biology research domain [5, 6]. The RNA secondary structural outputs provide the base for shaping the RNA three-dimension (3D) structure, which is the first step of the RNA tertiary structure phase.

The importance of the computational methods for predicting RNA secondary structure has been acknowledged as a demanding research area, by computer scientists. Also, there are many conditions, facing the experimental methods that are used by biologists [7, 8]. The Nuclear Magnetic Resonance (NMR) and X-ray crystallography are the two popular experimental purification methods that are used to determine the RNA 3D spatial structure [9, 10]. Latest studies confirmed that many classes of RNA molecule broadly fold in the pseudoknot motif [11, 12]. Whereas, the RNA structural functions of pseudoknot elements, have been emphasized to be prominent for medical processes and designing anti-viral treatments, in therapeutic research [13]. Consequently, the computational RNA prediction methods for predicting the RNA secondary structures are extensively utilized with manageable efforts [14].

The RNA molecules come in two main shapes: the Stem-loop and the Pseudoknots, as illustrated in Figure 1 in terms of RNA structure classifiers [15]. The Stem-loop is a non-crossing RNA structure motif. While, the Pseudoknots is a crossing RNA structure, which plausibly has been spotted by [16]. Further, the pseudoknotted RNAs has been proven to play several vital roles. From complexity points of view, the top prediction methods of RNA without pseudoknots functional element are MFold [17] and Vienna [18] algorithms which execute with complexities O(n 3) in time and O(n 2) in space. PknotsRG [19] is one of the most proper algorithm for predicting RNA with pseudoknots. It requires O(n 4) and O(n 2) in time and space complexities, respectively. Even if the pseudoknotted RNA secondary structure prediction problem has been stated as Non-deterministic Polynomial time (NP)-Complete problem [20, 21], it is an insisted matter to be solved [22, 23], in recent years.

In order to overcome the prediction problem of RNA secondary structure with pseudoknots, this article introduces

a nature-inspired hybrid method called ABCRna. Innovatively, this approach combines a new derivation from Artificial Bee Colony (ABC) algorithm with a special deterministic constraints [24]. On top of this, it is borrowed from the Artificial Intelligence (AI) field, which is a kind of nature swarm-intelligence [25]. The objective of this proposed method is to build the entire RNA secondary structure with pseudoknots from a given single-stranded RNA primary sequence. Indeed, this proposed method is a combination of KnotSeeker (heuristic-based method [3]) with UNAFold (a dynamic programming method [26]) for solving the RNA structural related issue. This hybrid method is a new derivation from ABC algorithm. It adapts the inspired swarm-based intelligence behavior of the honeybees in collecting nectar and converting that to honey and royal jelly [27]. Naturally, every individual worker bee visits many flower patches during the round-trip of collecting nectar and pollen. Then it goes back to the hive to submit the mixed nectar to the nurse bee. Finally, the nurse bee starts making honey by a natural biological secreting process.

Intuitively, the proposed RNA structural hybrid method is deployed and built to solve the related pseudoknotted RNA bioinformatics problem. By a deeper understanding of the CBR technique [28], the proposed hybrid model obtains a global optima RNA structural assurance results with more accuracy and better performance. Finally, the results show that the ABCRna method significantly improves the execution time and the accuracy in both sensitivity and specificity. This improvement when comparing the outputs with the other pseudoknotted RNA prediction methods existing in the state-of-the-art like; FlexStem [29], HotKnots

[30] and PknotsRG [19].

The remainder of this article is ordered as follows: In the next section, we start with describing the secondary structure of the RNA molecule, in computer context representation. In section 3 background materials, gives a concise expression to the generic ABC optimization method. Then, a derivation of

Figure 1. A stem-loop and pseudoknots of RNA structures types.

ABC is adapted to generate the proposed method. Next, the CBR as a modern AI technique, is extensively and widely discussed, from theoretical concept. Section 4 presents the proposed method with the implemental mapping between pseudoknotted RNA secondary structural prediction and the secreting process of making honey. Subsequently, the following section reports the comparative benchmark of the proposed method. The results of ABCRna is comparing against the results of other RNA prediction methods in the literature. Finally, the article ends with conclusion remarks, in section 6.


A. RNA Stem-Loop (non-pseudoknots)

The single-stranded RNA molecule forms many folded structures in hierarchal shape; the primary RNA single sequence, the secondary structure of RNA molecule, the three-dimensional (3D) or tertiary RNA functional structure and the quaternary structure for RNA polymerase [31]. Generally, the RNA computational methods predict the secondary structure of the given RNA primary sequence. Thus, the RNA secondary structure defines: as an RNA structural motif, which in some parts includes the double-stranded motifs. These parts joined by complementary and canonical base pairings with the other parts, which are the non-paired single bases. The double-stranded motif parts coming in several shaped of stem-loops: hairpin, internal (or interior), bulge, multi-branch external bases and stacking (or helices) loops. As explained above and illustrated in Figure 2, the RNA primary sequence (RNA bases) folds and joins on itself in real RNA secondary structure by hydrogen chemical bonds for low energy and more stability [15]. In mathematical and computational representation concept, the various layers of RNA structures can be defined as follows:

b = b1, b2, , bi, , bn, where b is an RNA primary sequence and bi is the RNA base or nucleotide [32, 33]. The element bi is also a member of set which includes {A,C,G,U,N}. While, the first four alphabets are representation of the original paired bases (pairednucleotides) of the real RNA molecule: Adenine, Cytosine, Guanine and Uracil, respectively. The last nucleotide N is assigned to the non-paired base. Such that the n is the length of the given RNA sequence and 1...

S ={(bi, bj)}, such that (bi, bj) belongs to the canonical base pairs. S is the secondary structure of the given RNA primary sequence which satisfies the following conditions:

-(bi, bj) . {(A,U), (U,A), (G,C), (C,G), (G,U) ,(U,G)}, these are the sets of RNA base-pairs. While, the base pairs include in the set { A-U , U-A , G-C , C-G} is a Watson-Crick RNA base-pairs [34], the set { A-U , U-A} is a Wobble RNA base-pair [35].

-Then S = {(bi, bj): 1.<. and . > }, where is a threshold constant number depend on the limit length of the minimum un-paired bases in a stem-loop (hairpin, stem or bulge ... etc). The is typically taken to be equal three.

-If(bi, bj) . S,(bk, bl) . S and if bi = bk, then bj = bl. This implies (bi, bj)=(bk, bl). In another words, every base (nucleotide) in RNA secondary structure make join by hydrogen bond at most with another one base (non-triple or only allow one-to-one).

-If(bi, bj) . S,(bk, bl) . S and <, this can include two location elements in RNA stem-loop structure (nonpseudoknots):

If <<<, then the two base pairs are form a type of nested location elements (nested-fashion), as depictured in Figure 3 a.

If <<< , then the two base pairs are form a type of juxtaposed location elements (juxtaposedfashion) [36], as shown in Figure 3 b.

B. RNA with Pseudoknots

The majority of RNA molecule classes fold in functional structural elements called pseudoknots. Indeed, they belong to the (3D) tertiary structure element and perform an important useful roles and constructive functions [37].

The pseudoknots substructure can theoretically satisfy the following term. If there are two base pairs (bi, bj) and (bk, bl), then satisfy the conditions: <<< or <<<, as shown in Figure 3 c and d. These two base paired shapes are represented the pseudoknots RNA structural elements. In another word, the pseudoknots is a crossing sub-structural functional element in the RNA molecules. It forms interaction the unpaired bases part of the stem-loop, which folds back and join in a loop region located outside that stem-loop.

In spite of the prediction algorithms of RNA with pseudoknots structural elements, have been proven to be NP-complete problem [21]. It is a demanding research area because of the pseudoknotted RNAs has importance as key functions. Further it plays essential roles in viral and cellular regulatory [38].

Figure 3. The diagrammatic position relation between different types of RNA base pairs. (a) two base-pair in juxtaposed fashion. (b) two base-pair in nested fashion. (c)&(d) two base-pair in pseudoknots.


A. Problem Statement of RNA with Pseudoknot

Pseudoknotted RNA secondary structure is the problem of predicting its secondary structure from a given primary sequence. Particularly, it has recently become attractive research area. Due to that the RNA with pseudoknots, has many important and useful roles, which needs to be solved computationally [40]. The existing pseudoknotted RNA prediction algorithms perform in exponential time complexity. The best prediction method run, in the worst case, O(n 4) in time and O(n 2) in space [19]. Thus they run very slowly and need an ever increasing memory-space, especially for long sequences. Veritably, this means that the prediction solving algorithms of the pseudoknotted RNA secondary structural problem, suffer from long execution time and storage complexities. To the best knowledge of the authors, the final structural results suffer from poor quality and inaccuracy, for long RNA sequences.

The pseudoknots class of the RNA structural prediction issue, has been proven an NP-complete problem [20]. Increasingly, the collecting nectar to make honey is an inspired field for the bioinformatics researchers, which is derived from the original ABC model [24]. In this article, a new hybrid method as a sub-area of swarm intelligence approaches for solving the pseudoknotted RNA structural problem is adapted. Besides that the CBR as a modern AI technique highlighted a way to be deployed, in term of enhancement the final results of the proposed hybrid ABCRna model. From comparison points of view, we find this method improved the accuracy of the RNA structural outputs with good performance.

B. Swarm-Intelligence in AI Technology Swarm Intelligence (SI): is an emergent and bioinspired field of AI, which has been generated from numerous researches in social insects behavioural models [41]. The phrase swarm comes up to present solution to overcome the

optimization problems. These optima solutions have been successfully got by utilizing the co-operative and coordinative efforts among the worker-insects. The inspiration of the swarm intelligence is gained from many social insects behavioral models like; honey-bees colony and ant-colony. For instance in bee-colony, the objective of the swarm is the quantity and quality production of honey by the mutual teamwork. It is a key fact that, the amount of honey that an individual worker-bee harvests is worthless. But, the honey production by all worker-bees is considerably much better than the crop of an individual one [42].

Lately, swarm intelligence has obtained high interest to be adapted by many researchers from diverse fields. The list compromises, but it is not limited of: engineering, science and commerce fields. The computer researchers propose swarm intelligence optimization methods to solve many complex problems that suffer from severe drawbacks. The typical research domain of the computational swarm intelligence is to solve many real-world problems. Some applications of swarm intelligence in a development areas as follows: (i) The routing optimization in different communication network [43]. (ii) The job scheduling [44].

(iii) The swarm control in the Unmanned Aerial Vehicles (UAV) for both civil-military purposes [45, 46].

C. Honey-Bee Colony Structure

Many social insects live in colonies have instinctual ability to perform as agents in a group for solving complex problems and to complete their tasks. The new AI disciplinary swarm-intelligence has been attractively produced by deep knowledge of the biological swarm in solving the problems. This can done by a behavioral interaction among thousands members of the swarm-insects [47]. Naturally, the social insects have talent to be in self-organized behavioral models for achieving an intelligence solution of the vital tasks.

Honey-bees live in a well structured social insects colony called a hive. The hive typically is a composition of a solo queen, drones and workers [48]. Each one does the following roles: (i) As usual, there is one queen. She is egg-laying, female as a mother for other colony members and mates one time in her lifelong by drones. (ii) There are drones or male bees as bee-colony fathers. Their main responsibility is fertilizing the new queen in a mating flight party (social gathering) before dying. They live at most six months and reach to hundreds up to several thousands during the summer season. (iii) There are around 10,000 in winter to 60,000 in summer female worker-bees (foragers) in each bee-colony. They do many important jobs including: collecting nectar to make food, raising and bringing up the broods and larvaes, guarding and ventilating the hive. But, the primary resourceful task of the worker-bees is collecting the nectars and pollens from the flower patches (forage field). Later, when they back to the hive the worker bees secret the honey and royal jelly (food).

D. Honey-bee Collecting Nectar (Foraging)

Honey-bees collecting nectar process to make honey is to be considered as an optimization swarm-based intelligence approach [49]. The worker-bees perform the collecting nectar and secreting honey process in a well-organized behavioral model known as bees foraging process [50]. It is obvious that, this gigantic task is beyond the ability of every worker-bee individually. Nevertheless, all the group members interact among each other in a fashion to solve the collective bee-foraging problem.

The main incentive task in bees colony is the foraging (collecting nectar to make honey). To investigate the bee foraging process Seeley in [51], introduced a detailed systematic mechanism. It is about the self organized honeybees social behavioral model in collecting forage, as shown in Figure 4. In the proposed system, every worker bee (forager) visits many flowers from the same type within 30 to 120 minutes of foraging trip. All the collected nectars, from these flower patches, have been stored in the forager honey stomach. Besides that, the forager commits several actions to provide a feedback. Waggle dance is providing the profitability rating of nectar in the flower patches, the odor, location and other required information [52, 53]. Accordingly, the making honey and royal jelly process starts when the worker-bee back to hive from the foraging round-trip journey.

Soon after reaching the hive from the foraging trip, the field bee (forager) gears up to submit that nectar, which already stored in her honey sac [54]. This process of submission the gathered nectar to the house bee (nurse bee) is accomplished in a regurgitated behavior. The role of the house bee is converting that nectar to honey or royal jelly (bee food) in a secreting process. In this synthesizing honey process, the main work is to split the complex sucrose sugar into fructose and glucose, which are simpler sugars and predominant in honey. This sucrose-splitting process is performed by adding the invertase, which is a special enzyme, to the nectar from the hypopharyngeal gland in the head of bee. Then, the new synthesized honey or royal jelly is spread out in a honey comb cells. The house bee exposes this secreted honey as a thin film to aware of the last filtration. This final step was done by increasing the surface area, to insure the fast evaporation of water in the well-done honey. Finally, the filled honey comb cells sealed and capped by propolis (plant gum), which is an adhesive material. This waxy cover prevents the honey from the bacterial attacks or in case of prevention the stored food to avoid the fermentation.

Consequently, here the details of the foraging process are presented to make a base for our nature-inspired method. It is a hybrid adaptation from the process of honeybees in collecting nectar to make honey and royal jelly. The proposed ABCRna method solves the secondary structure prediction problem of RNA with pseudoknots. The idea is stimulating a hybrid novelty swarm-intelligence approach from collecting nectar and making honey in the natural secretion process. ABCRna as a new optimization algorithm is based on the main features of a hybrid between two heuristic-based method KnotSeeker [3] and dynamic programming algorithms UNAFold [26].

E. CBR and KB

Its commonly known that the AI research area provides many methodologies and technologies for solving complex problems, which the CBR is one of them. Recently, the CBR has been successfully used to restore solution for a new problem based on expertise by retrieving the similar mature solutions of the past problems [55]. Originally, CBR comes up from the cognitive science and the human expertise to retain and retrieve the information. In another word in CBR method, the people solve the new problem by recalling how they solved the past similar problems. The CBR method includes a problem solving cycle with four main activities: Retrieve, Reuse, Revise and Retain [56]. According to the Figure 5, in the heart of this four-REs cycle there is a case-library as a Knowledge Base (KB). This KB is used in retrieval action to assess an intelligent decision of the similar cases for revising the final outputs by retrieving the most correct solutions.

By referring to the adhere of exact matching concepts, the CBR is a generic AI methodology in problem solving [57]. In the proposed ABCRna method, the CBR is deployed as a modern AI inspired technique with KB to augment the result in retrieval steps. The role of CBR is finding the current pseudoknotted RNA sub-structure with the exact matching from KB. The KB holds and clusters all real pseudoknotted RNA sequences and their known native structures. If the retrieval one has pseudoknots in its secondary structure, then the CBR chooses the current one. This CBR comparing process, enhances the quality of the predicted pseudoknotted RNA secondary structure. Moreover, it is deployed significantly to be an alternative development technique for solving the secondary structure prediction problem of RNA with pseudoknots.

F. Preliminarly in Optimization

According to the theoretical viewpoint, the optimization methods are branch of the applied mathematics and basically

Figure 5. The Case-Based Reasoning (CBR), a modern Artificial Intelligence methodology, adapted from [55].

compromise from two main classes of algorithms; deterministic and probabilistic. Figure 6 shows the general category of the global optimization methods to clear the relation among all their characteristics. Definitely, the deterministic algorithms are a type of algorithm which take a set of fixed inputs and produce a fixed result. While, the heuristic is a single assumption works as a search strategy or technique in problem-solving. It is based on intelligence and experience, which can be applied loosely in computer implementation [58]. The meta-heuristic is based-on several assumptions work as an optimizer to improve a series of candidate solutions to reach to the final problem solving. Also it may use the many trials iteratively. In 2001, Geem et al. introduced the Harmony Search (HS) algorithm, which was a new meta-heuristic algorithm based on natural-inspired phenomena behavioral models [59]. The HS has been developed from mimicking the natural phenomena of the musicians improvisation (music players). Several experiments proved that the HS as a meta-heuristic algorithm, is capable to solve the optimization problems with more improved performance. The result makes the HS as a durable meta-heuristic algorithm in solving the NP-complete problems. The Traveling Salesman Problem (TSP) is an example of NP-problem which was solved by HS [60].

Now the main question, Is it feasible to develop a hybrid meta-heuristic algorithm for building the pseudoknotted RNA structure with good performance and more accurate result? To do this an optimized swarm-based intelligence algorithm would be inspired as a kind of stimulation from the Artificial Bee Colony (ABC) algorithm [61]. This inspired proposal utilizes the ABC to solve the related issue of RNA structure in bioinformatics. Moreover, the Particle Swarm Optimization (PSO) is a distinguished swarm-based intelligence algorithm that models some animal social behavior like fish schooling or swarm of honey-bees [62]. PSO has been proposed by Kennedy in 1995 and has reached to be an interesting area of knowledge to exploit for developing a new meta-heuristic algorithm by mimicking and inspiring the natural phenomena of animals and colony insects.


This section explains in details, the new hybrid of derived ABC algorithm to overcome the pseudoknotted RNA secondary structure prediction problem. The proposed hybrid ABCRna method is inspired from the swarm-intelligence social behavioral model of honey-bees in collecting nectar and secreting honey, as shown in Figure 7. Hence, the authors develop ABCRna as a hybrid method in a simple way to build the secondary structure of RNA molecule with pseudoknots. The following sub-sections demonstrate separately the paradigms of designing the proposed method. These sub-sections describe the mapping of the all features between the ABC optimized algorithm and the RNA structural prediction problem. The final computational results of ABCRna for RNA structure reveal an optimized better performance and more accuracy in terms of sensitivity and specificity. Its computer code implementation shows less space and time complexities when comparing with other state-of-the-art methods in solving such RNA prediction problem.

Here, the researchers underline the hybrid adaption model as a new derivation from ABC algorithm to solve RNA prediction problem. It is a first threshold further opens the door in front of the other bioinformatics researchers to follow. Furthermore, it gives immense opportunity to expand this proposed optimizer in solving such kind of complex biocomputing problems. This is why the AI material already has presented in the background section to be a general guidance.

A. Honey-bee Foraging Algorithm

The innovative ABC as a swarm-based intelligence algorithm was deployed particularly based on the honeybee natural social behaviours. A few other algorithms have been derived by inspiring the honeybees swarm behavioral model, intelligently [61]. Many researchers have been adapted such this swarm collective behaviours to solve optimization combinatorial problems. Herein, we describe a new hybrid

Figure 7. Workflow of the ABCRna approach for predicting the pseudoknotted RNA secondary structure, some parts adapted [55].

algorithm called ABCRna, which is derived from the original ABC algorithm [24]. It is developed as a hybrid adaptation between ABC models with deterministic constraints and inspired by the intelligence social behaviours of bees in collecting nectar to secret honey. The proposed method is applied to solve the pseudoknotted RNA secondary structure prediction problem, which is a kind of combinatorial NP-complete problem [20].

The bees in colony deliberated for collecting nectar and secreting honey and they compromise in three bee groups: employed bees, unemployed bees (onlookers or scouts) and nurse bees, plus the food sources (flower patches profitability). The first two groups of honeybees (employed and unemployed) search for the last part which is the rich food sources. The third bee component takes the collected forage (nectar) from the first two groups by process of regurgitation. After that, the nurse bee starts making honey and royal jelly by a popular secretion honey process. The behavioral steps of the bees to carry out the forage collecting process, has been shown in Figure 4. Naturally, it can be described as follows:

a) Employed bee (Forager): visits several food sources to collect the harvested crop, in each round-trip foraging journey. Nectar from many flower patches accumulate and store in the foragers honey stomach (honey sac).

b) Nurse bee: working inside the hive and she receive the collected nectar from the employed bee (forager) by regurgitation process. After that, the nurse bee starting makes honey or royal jelly from the associated mixed nectar by secreting invertase enzyme from the hypopharyngeal gland in her head. The corresponding enzyme assists to split the complex sugar (sucrose) to two simplifier sugars (fructose and glucose), which are principal of new well-done honey.

B. The Classical ABC Algorithm

The ABC algorithm is a new AI model, which has been stimulated by the collective behavior of the social honeybees based on swam intelligence. It uses multi-resource and multiform to perform the job with full optimization [24]. The ABC algorithm originally is divided into three parts: employed bees, onlookers and scouts. The employed bee is a hard-worker part in the colony that responsible to collect food. Onlookers part is waiting inside the hive to decide on a forage source. Scouts is performed a general search to find the food resources.

C. Hybrid ABC Algorithm for RNA Structural Prediction

Our proposed ABCRna method is a hybrid model based on the PSO and it is derived from the original ABC model. This new derivation of the modified ABC is associated with a specific case corresponding to the pseudoknotted RNA secondary structure prediction problem. The worker bee (employed bee) works as an agent, visits many rich flower patches (artificial food sources) to collect the nectar. Thereafter, all collected nectar from many flowers stored in foragers honey stomach, which will be a mixture of nectar from several food sources (many flowers). Then, the employed bee (forager) back to the hive from the foraging journey with the mixed nectar fills her honey stomach. In the hive, the forager submits the crop (collected nectar) to the nurse bee in a regurgitation process. Finally, the nurse bee now is ready to make honey from the corresponding mixture of gathered nectar that submitted by employed bee. The nurse bee starts secreting the honey or royal jelly associated with specific needs of the hive. Here, the final well-done honey is represented the good solutions for the RNA structural prediction problem. In another words, the concluding honey in mapping segment, stands for the more accurate pseudoknotted RNA secondary structure for a giving primary sequence.

The central phase of the ABCRna method is a HoneyRna algorithm, which is a modified from ABC algorithm to solve the pseudoknotted RNA structural prediction method. This HoneyRna algorithm is illustrated in Figure 7 and computes in steps as follows:

1: Initialize


3: Place the employed bee on her food sources (many flowers)

4: Place the nurse bee on hive working to receive mixed nectar

5: Secret enzyme to split the complex nectar to a simpler honey

6: Fill the secreting food (honey & royal jelly) in the honeycomb

7: Filter the well-done honey from extra water by evaporation

8: Cap and seal the filled cell with food by adhesive wax

9: UNTIL (Demanded food is met)

In the modified ABC algorithm, each cycle of the collecting nectar and secreting honey process includes three steps: (i) the employed bee visits many flower patches in each round-trip of collecting nectar journey. All gathered nectar is stored in her honey stomach. The employed bee backs to the hive with holding the mixed nectar. Then, she will submit this mixture to the nurse bee.

Moreover, the secretion process of the honey by nurse bee performs in many steps, as follows:

a) The harvest of the forage (the mixed nectar), has been collected from many flowers. By mapping this phase with the RNA related issue, the predicted RNA secondary structure is collected from many existed RNA predicted methods, as illustrated in Figure 7.

b) The nurse bee starts make honey by secreting invertase enzyme from the gland in her head. This enzyme simplifies the sucrose which is a complex sugar in the nectar to two types (fructose and glucose) of simpler sugars, which are composed the well done honey. By mapping this with RNA structural problem, there is an agent program, which is working like that enzyme. This function re-constructs the entire secondary structure of RNA sequence with pseudoknots from many parts.


We evaluated ABCRna on different types of pseudoknotted RNA classes. The proposed method is built to predict the RNA secondary structure with pseudoknots. The comparisons of the ABCRna results have been performed by measuring the accuracy of its outputs to the outputs that has been achieved from FlexStem [29], HotKnots [30] and pknotsRG [19]. These accuracy measurements compromise three statistical notations: (Sensitivity S, Selectivity P and F-measure). They can be calculated by applying the following formulas, which derived from [63]:


Sensitivity = 100 1



Speciicity = 100 2


F.measure= 2 100, 3


where TP is represented the True Positive, which denotes the number of base pairs that are predicted correctly and presented in the known native structure. FN is represented the False Negative, which counts the base pairs that are presented in the known native structure, but they are not reported in the predicted structure. FP is represented the False positive, which denotes the number of base pairs, presented in the native known structure, but they are not in predicted structure. F-measure is a single measure that combines both sensitivity and specificity of the predictor algorithm in a unique performance measure.

Figure 8. Plots of qualitative comparison analysis of TMV structures: (a) The known native secondary structure of TMV molecule. (b) Secondary structure predicted by our proposed ABCRna method, with highest excellent sensitivity of (92.9%) and specificity (95.6%). (c) Secondary structure predicted by FlexStem (sensitivity of 44.3% and specificity 44.9%). (d) Secondary structure predicted by HotKnots (sensitivity of 67.1% and specificity 81.0%). (e) Secondary structure predicted by pknotsRG (sensitivity of 60.0% and specificity 66.7%).

Here, the comparison analysis of the outputs are performed between our proposed ABCRna method against to the FlexStem [29], HotKnots [30] and pknotsRG [19]. One example of this comparison pricess uses the RNA sequence tobacco mosaic virus (TMV) from 3UTR type [64]. The length of TMV is equal 214 nucleotides (nt), which its accession number J02415. Our proposed ABCRna method obtained the highest results, Sensitivity (S = 92.9%) and Specificity (P = 95.6%), which are measured according to the known native structure of TMV molecule. The sensitivity and specificity of FlexStem [29], HotKnots [30] and pknotsRG [19], are listed in the legend of the illustrative Figure 8, respectively. Finally, the Figure 8 depicts a qualitative comparison analysis among the output of our ABCRna and the best result of all others methods from the literature. This comparison analysis is applied on the secondary structure of TMV RNA molecule, which its images are produced by PseudoViewer software tool [65]. NUPACK [66] and pknotsRE [67] methods cannot predict the secondary structure of RNA sequences in larger than the length of 200 nt and 150 nt, respectively. The reason behind that the both algorithms NUPACK [66] and pknotsRE [67], require an enormous amount of memory (RAM) and run in exponential time. To reach to a fair comparison, the outputs for these scenarios put out of the result. Also, all five existing methods (FlexStem [29], HotKnots [30], pknotsRG [19], NUPACK [66] and pknotsRE [67]), have been implemented in the same machine, a PC Ubuntu 10.04 64-bit Linux OS, with AMD Phenom-II 810 2.6-GHz Quad-Core processor and Dual Channel 4GB (2x2GB) DDR2-800 Memory (RAM).

Table 1 summarizes the final comparison analysis of the results among the predicted RNA structures from our proposed ABCRna method and the best ones from FlexStem [29], HotKnots [30], pknotsRG [19], NUPACK [66] and pknotsRE [67] methods. The comparison process has been done in respects to the three accuracy metrics listed in Equations (1, 2 and 3). The evaluation of these comparative results were performed and verified according to the standard native structures of each RNA molecule. The analyses show the results of the ABCRna method are significantly better than the results of other methods from literature, in terms of sensitivity, specificity and F-measure.


This paper presented a novel hybrid method for solving RNA secondary structure with pseudoknot functional classes. This hybrid method includes ABC model as a global optimization method, hybridized with CBR as a local optimization technique. The proposed method used the existing results from KnotSeeker and UNAFold to generate a secondary structure of RNA includes pseudoknots, by using an existing cases.

Three evaluation mechanisms are used to measure the efficiency and performance of proposed method comparing to others from literature. The sensitivity, specificity and F-measure metrics showed that successful outcomes have been recorded. Furthermore, three different comparative methods are used in order to compare the obtained results. The proposed ABCRna hybrid method outperformed other comparators in almost all standard benchmarks. Note that the factor for comparison is the real native structure.

We believe that the proposed hybrid method have a high potential with a great efficiency for the problems solved by RNA community. This worthwhile domain is pregnant with several future research directions such as: further study cases in CBR, different global optimization, different factors of analysis and hybridize more RNA prominent methods.