Cargando…

A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem

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. Thi...

Descripción completa

Detalles Bibliográficos
Autor principal: Gallardo, José E.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2012
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3531471/
https://www.ncbi.nlm.nih.gov/pubmed/23300667
http://dx.doi.org/10.1371/journal.pone.0052427
_version_ 1782254185560932352
author Gallardo, José E.
author_facet Gallardo, José E.
author_sort Gallardo, José E.
collection PubMed
description 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.
format Online
Article
Text
id pubmed-3531471
institution National Center for Biotechnology Information
language English
publishDate 2012
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-35314712013-01-08 A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem Gallardo, José E. PLoS One Research Article 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. Public Library of Science 2012-12-27 /pmc/articles/PMC3531471/ /pubmed/23300667 http://dx.doi.org/10.1371/journal.pone.0052427 Text en © 2012 José E http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Gallardo, José E.
A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
title A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
title_full A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
title_fullStr A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
title_full_unstemmed A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
title_short A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
title_sort multilevel probabilistic beam search algorithm for the shortest common supersequence problem
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3531471/
https://www.ncbi.nlm.nih.gov/pubmed/23300667
http://dx.doi.org/10.1371/journal.pone.0052427
work_keys_str_mv AT gallardojosee amultilevelprobabilisticbeamsearchalgorithmfortheshortestcommonsupersequenceproblem
AT gallardojosee multilevelprobabilisticbeamsearchalgorithmfortheshortestcommonsupersequenceproblem