WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2880
Volume 14, 2015
A Hybrid Method Applied to Multiple Sequence Alignment Problem
Authors: ,
Abstract: Multiple sequence alignment (MSA) is an important tool in biological analysis. However, it is difficult to solve this class of problems due to their exponential time complexity when the number of sequences and their lengths increase. In this research paper, we present a new method for multiple sequence alignment problem, based on classical tabu search (TS) and simulated annealing (SA) techniques. The developed approach is called (TSSA), it is implemented in order to obtain an optimal results of multiple sequence alignment. The essential idea of our TSSA approach is the integration of the metropolis criterion of SA algorithm to construct elite solutions list, which can be exploited by TS algorithm to intensify the search around of best elements of this list. At the same time, it helps to diversify the search when TS restarting with worse solutions from the constructed elite solutions list. Computational results on a wide range of datasets taken from the BaliBASE database have shown the degree to which simulated annealing enhance the performance of tabu search algorithm and demonstrate the superiority of TSSA algorithm over the six well-known multiple sequence alignment methods PRRP, ClustalW, SAGA, DiAlign, ML_PIMA and MultiAlign. The proposed method also finds solutions faster than binary particle swarm optimization (BPSO) algorithm, TS-R algorithm, AIS method and IMSA approach.
Search Articles
Pages: 465-473
WSEAS Transactions on Computers, ISSN / E-ISSN: 1109-2750 / 2224-2880, Volume 14, 2015, Art. #47