Metaheuristics for String Problems in Bio-informatics

3Longest Common Subsequence Problems

Longest common subsequence (LCS) problems frequently arise in bio-informatics applications. The most general problem in this class is simply known as the LCS problem. However, this problem class comprises a whole range of specific problems that are mostly restricted cases of the general LCS problem. Apart from the general LCS problem, we will also deal with one specific restriction known as the repetition-free longest common subsequence (RFLCS) problem in this chapter. An important landmark in the development of metaheuristics for LCS problems was the application of beam search to the general LCS problem in 2009. This algorithm significantly outperformed any other algorithm that was known at that time. Most approaches proposed thereafter have been based on beam search.

In this chapter, we will describe the original beam search approach to the general LCS problem. Moreover, we describe Beam–ACO, which is one of the more recent proposals based on beam search. This algorithm is obtained by combining the metaheuristic ant colony optimization (ACO) with beam search. After presenting the adaptation of the Beam–ACO algorithm to solve the RFLCS problem, we will describe current state-of-the-art metaheuristic for the RFLCS problem. This algorithm is a (IPL) hybrid metaheuristics obtained by combining probabilistic solution construction with the application of an integer linear programming of solver for sub-instances of the original problems. The general ...