title: A multilevel probabilistic beam search algorithm for the shortest common supersequence problem.
abstract: The shortest common supersequence problem is a classical problem with many applications in different fields such as planning, Artificial Intelligence and especially in Bioinformatics. Due to its NP-hardness, we can not expect to efficiently solve this problem using conventional exact techniques. This paper presents a heuristic to tackle this problem based on the use at different levels of a probabilistic variant of a classical heuristic known as Beam Search. The proposed algorithm is empirically analysed and compared to current approaches in the literature. Experiments show that it provides better quality solutions in a reasonable time for medium and large instances of the problem. For very large instances, our heuristic also provides better solutions, but required execution times may increase considerably.
authors.affiliation: Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Málaga, Spain. pepeg@lcc.uma.es
authors.forename: José E
authors.initials: JE
authors.lastname: Gallardo
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000235:genetics; D011336:Probability; D013997:Time Factors
chemical_list: D004247:DNA