A HYBRID GENETIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE OF MULTIPLE SEQUENCES

Finding the longest common subsequence for multiple sequences are knows as k-LCS. For significant number and longer length sequences the k-LCS turns out to be a NP-hard problem. To solve this problem, we have developed a hybrid genetic algorithm that can be used to find an optimal solution in comparatively less time. The results obtained by our solution are comparatively better than that of EA (Expansion-algorithm), BNMAS(Best next maximal available symbol algorithm.), GA(Genetic algorithm) and ACO(Ant colony optimization algorithm). Using Hill Climbing along with Genetic Algorithm proved to be a successful development in finding the more optimal solution with less time complexity. As Genetic Algorithm has been used, the number or length of the sequences doesn't post to be a problem and a better subsequence is obtained with each iteration.