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...
Autor principal: | |
---|---|
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 |