A Survey on Multiple Sequence Alignment using Metaheuristics

Over the past two decades, various research works have been going on Multiple Sequence Alignment (MSA) and it becomes an important domain in bioinformatics. This is an NPhard problem. For this purpose, various traditional, heuristics and metaheuristic methods have been applied. Among these methods, metaheuristics show an effective output to overcome the bottleneck of MSA problem. Different metaheuristic methods and software have been developed to overcome the speed and accuracy problem of MSA, while the number of sequences increases. In this article, we have surveyed widely used metaheuristic methods and alignment tools applied for solving MSA problem. However, after reviewing we can conclude that the time complexity is still a big challenge for MSA problem.