بررسي الگوريتم هاي موجود براي برخي مسائل انتخاب و مقايسه رشته ها در بيوانفورماتيك و ارائه الگوريتم هاي بهبود يافته

چكيده انگليسي :

89 A study of existing algorithms for some string selection and comparison problems and providing improved algorithms Maryam Babaie m babaie@ec iut ac ir March 13 2010 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor S R Mousavi srm@cc iut ac ir Abstract 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 classes of non exact algorithms for CSP which are approximation algorithms and meta heuristic algorithms The distinction between these classes of algorithms is that the former guarantees a bound called approximation ratio on the optimal solution whereas the latter does not In practice however meta heuristic algorithms usually provide better solutions than those provided by approximation algorithms In this thesis two heuristic algorithms are proposed for three problems closest string problem farthest string problem and far from most string problem The first algorithm is memtic algorithm In a memetic algorithm local search is incorporated within an evolutionary algorithm Memetic algorithms have been successfully applied to many optimization problems such as knapsack and graph coloring In our proposed algorithm local search is added to GA as a consequence of which neighborhood of the chromosomes are also investigated The other algorithm is Greedy randomized adaptive search procedure GRASP these algorithm uses the advantages of greedy and randomized algorithms to find good solutions for optimization problems Results of implementation of proposed algorithms are compared with the last algorithms for each problem Is has been shown that our algorithms could outperform the results of state of the art algorithms for all problems For closest string problem and farthest string problem GRASP could find better solutions but for farthest string problem memetic algorithm obtained better results Key Words Bioinformatic Closest string problem farthest string problem far from most string problem memetic algorithm GRASP

بابائي، مريم

بررسي الگوريتم هاي موجود براي برخي مسائل انتخاب و مقايسه رشته ها در بيوانفورماتيك و ارائه الگوريتم هاي بهبود يافته

NP و P , روشهاي فرامكاشفه اي , مسئله ي FSP