The Shortest Common Supersequence (SCS) problem is a justify; MARGIN: 0cm 0cm 0pt; unicode-bidi: embed; DIRECTION: ltr" 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