Computational biology and bioinformatics are two important interdisciplinary fields which connect biology and information technology. An important goal of these fields is to interpret genome and protein data, which has led to such problems as genome rearrangement, sequence alignment, and sequences consensus problem, most of which are known to be NP-hard. Sequences consensus problems include closest string problem and farthest string problem and far from most string problem, Which have applications in drug design and coding theory. The closest string problem seeks for a string whose distance from all the strings in a given set of strings is minimum. Consequently, the solution to the problem is a sequence with maximum 'similarity' to the input strings. The farthest string problem, on the other hand, is the reverse of the closest string problem in the sense that it seeks for a string whose distance from the given strings is maximum. The third problem is to find a string which has distance more than a predefined threshold from all the strings of the input strings. These problems are especially important in the context of studying molecular evolution, protein structures, and drug target design. For example, one of their applications in drug target design is to find a genetic sequence that kills all pathogenic bacteria without any impact on human being genes. The closest string problem also has applications in the coding theory, data compression, error decoding, and speech coding. Several algorithms have been proposed to solve these problems. Since the problems are NP-hard, none of these algorithms is a polynomial time exact algorithm. That is, the existing algorithms which can solve the problem to optimality are all exponential. However, because of their exponential complexity, these algorithms are not of much use in practice. Consequently, many non-exact algorithms have been proposed which try to obtain 'good' solutions in acceptable time. There are in general two justify; LINE-HEIGHT: 12pt; TEXT-INDENT: 11.35pt; MARGIN: 0in 0in 0pt; unicode-bidi: embed; DIRECTION: ltr; mso-line-height-rule: exactly; tab-stops: 28.35pt" dir=ltr Key Words Bioinformatic, Closest string problem, farthest string problem, far from most string problem, memetic algorithm, GRASP
