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

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

A Study of Existing Algorithms and Providing an Improved Algorithm for Shortest Common Supersequence Problem Fateme Bahri f bahri@ec iut ac ir Date of Submission 2011 03 16 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor Sayyed Rasoul Mousavi srm@cc iut ac ir Abstract The Shortest Common Supersequence SCS problem is a classical combinatorial optimization problem This problem receives as input a set of strings and searches for the shortest string that is a supersequence of all the given strings A supersequence of a given string is a string which can be obtained by inserting zero or more characters anywhere in the given string Various applications of SCS include data compression query optimization in databases planning and bioinformatics One of the most important applications of SCS in bioinformatics is to reduce manufacturing cost time and error of oligonucleotide microarray production Oligonucleotide microarrays are high throughput tools used in gene clustering gene identification Gene expression profiling and single nucleotide polymorphism detection Till now dynamic programming and branch and bound algorithms have been proposed to solve SCS problem optimally but the problem is NP Hard if the number of strings is greater than 2 so no exact polynomial time algorithm has yet been proposed Because of the inefficiency of exact algorithms for large instances of the problem most of the proposed algorithms are inexact which sacrifice optimality to obtain near optimal solutions in a reasonable time Among such algorithms for SCS problem are approximation heuristic and meta heuristic algorithms Approximation algorithms guarantee a bound on the approximation ratio of their solutions Heuristic algorithms which are usually fast use a heuristic function to achieve a near optimal solution These algorithms divide to simple heuristic and meta heuristic algorithms Till now different heuristic algorithms are proposed for the problem and some of them are designed particularly for DNA strings In this thesis an exact A algorithm is proposed for SCS problem Several heuristic functions are investigated and a hybrid heuristic function is finally proposed which outperforms the other ones by providing a better estimated bound Branch and bound strategy and also dominance pruning are used in the proposed algorithm to reduce the search space and execution time Extensive experimental results indicate that the proposed A algorithm comparing to other existing exact algorithms results in significant reduction of the search space and execution time Also a new heuristic algorithm and a post processing procedure are developed in this thesis for SCS problem This heuristic algorithm is a local beam search that employs a recursive heuristic and uses dynamic programming to populate an array of probabilistic values which are then used to speed up the calculation of the heuristic values It also uses the dominance property to further prune the search space The proposed algorithm is compared with three most recent algorithms proposed for the problem on both random and biological sequences outperforming them all by quickly providing solutions of higher average quality in all the experimental cases The input to the post processing procedure is any non optimal solution to an SCS instance The procedure then tries to shorten the given solution in an iterative cycle that is still a supersequence of the input strings Extensive experiments indicate that this post processing procedure is significantly faster and more effective than an existing post processing procedure Keywords Shortest Common Supersequence Heuristic Functions A Algorithm Local Beam Search

بحري، فاطمه

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

الگوريتم A , الگوريتم هاي مكاشفه اي , جستجوي پرتوي محلي