Anchor Point Approach For Initial Population Of Bat Algorithm Forprotein Multiple Sequence Alignment

Loading...
Thumbnail Image
Date
2016-09
Authors
Boraik Ali, Aziz Nasser
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Multiple sequence alignment (MSA) is a fundamental step for many bioinformatics applications such as phylogenetic tree construction, prediction of the secondary structure and identification of domains and conserved motifs. The reliability and accuracy of these applications depend on the quality of MSA. Although there are many approaches available for MSA including meta-heuristic, the accuracy of MSA remains a challenge. In addition, finding an optimal alignment is NP-hard problem under any reasonable objective function. On the other hand, bat algorithm (BA) is a recently used meta-heuristic algorithm, which is efficient in solving various optimization problems such as multiprocessor scheduling, image-matching problem and protein folding. This research aims to investigate the capability of BA, a population-based method with local search-based characteristics, to tackle the accuracy problem of multiple sequence alignment. The generation of initial population in optimization algorithms for MSA problem is one of the important factors that can influence the alignment quality. Determining beforehand specific positions (anchor points) to generate partial alignment has proved valuable for the accuracy of MSA in some research, where the anchor points is used as a guide to build the MSA. Therefore, this research proposes a method to detect the anchor points by using Shared Near Neighbours clustering algorithm to generate partial alignment. Then, a basic BA for MSA (BA-MSA) which has the ability to accept anchor points is presented. Afterward, an enhanced BA for MSA (ProfileBA-MSA) was developed by modifying the local search in BA. For further improvement, an enhanced initial MSA is presented as well as a new operator is included into BA (IBA-MSA) by combining a profile alignment technique with crossover operator. The proposed methods were evaluated and comparatively analyzed against other commonly applied MSA methods using BaliBase 3.0 benchmark. The inclusion of anchor points has improved the accuracy of the BA-MSA and ProfileBA-MSA methods.
Description
Keywords
Investigate the capability of BA, a population-based method , with local search-based characteristics.
Citation