Title:An Implementation of Three-level Multi-objective ABC Algorithm for RNA Multiple Structural Alignment
VOLUME: 12
Author(s):Soniya Lalwani*, Harish Sharma and Kusum Deep
Affiliation:Department of Computer Science & Engineering, Rajasthan Technical University, Kota, Department of Computer Science & Engineering, Rajasthan Technical University, Kota, Department of Mathematics, Indian Institute of Technology, Roorkee
Keywords:Parallel Computing, Multi-objective optimization, RNA structural alignment, Particle swarm optimization, Ctrie, Pareto optimal solution, Minimum free energy
Abstract:Background: Structural alignment of ribose nucleic acid (RNA) is one of the most challenging
multi-objective real world problems from the field of bioinformatics.
Objective: RNA molecules are less stable; hence they require inclusion of most stable secondary
structure during their alignment. Therefore, the structural alignment requires the consideration of
similarity score and structure score, as two objectives. Trade-off between these two objectives exists
since obtaining optimum similarity score at concurrent optimum structure score is not possible. This
paper presents artificial bee colony algorithm based three level multi-objective approach for performing
structural alignment of RNA sequences, namely MO-3LABC.
Method: Algorithm firstly builds the secondary structure of all sequences at minimum free energy
(MFE). Then sequence alignment is performed in level one at average percent sequence identity
(APSI) score based gap length, optimized by ABC algorithm. Level two now builds the secondary
structure of these aligned sequences based on base-pair probability and co-variation. Now the scores
of level one and level two move towards level three for multi-objective optimization at Pareto optimality
criteria with few additional strategies.
Results: The results of MO-3LABC are compared with an already established efficient strategy
MO-TLPSO; multi-objective two level strategy based on particle swarm optimization. The outputs
are compared for pairwise and multiple sequence alignment datasets at prediction accuracy and solution
quality criteria.
Conclusion: MO-3LABC is found significantly better than MO-TLPSO at all the four evaluation
criteria for both the datasets.
