About: An enhanced beam search algorithm for the Shortest Common Supersequence Problem

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: An enhanced beam search algorithm for the Shortest Common Supersequence Problem Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	An enhanced beam search algorithm for the Shortest Common Supersequence Problem
Creator	Bahri, Fateme Mousavi, Sayyed Sadat Tabataba, Farzaneh
Source	Elsevier; Medline; PMC
abstract	Abstract The Shortest Common Supersequence Problem asks to obtain a shortest string that is a supersequence of every member of a given set of strings. It has applications, among others, in data compression and oligonucleotide microarray production. The problem is NP-hard, and the existing exact solutions are impractical for large instances. In this paper, a new beam search algorithm is proposed for the problem, which employs a probabilistic heuristic and uses the dominance property to further prune the search space. The proposed algorithm is compared with three 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 Java source and binary files of the proposed IBS_SCS algorithm and our implementation of the DR algorithm and all the random and real datasets used in this paper are freely available upon request.
has issue date	2012-04-30(xsd:dateTime)
bibo:doi	10.1016/j.engappai.2011.08.006
bibo:pmid	32288320
has license	els-covid
sha1sum (hex)	bd8bee485194f10f696c48bbe1b9193a006292f4
schema:url	https://doi.org/10.1016/j.engappai.2011.08.006
resource representing a document's title	An enhanced beam search algorithm for the Shortest Common Supersequence Problem
has PubMed Central identifier	PMC7127599
has PubMed identifier	32288320
schema:publication	Engineering Applications of Artificial Intelligence
resource representing a document's body	covid:bd8bee485194f10f696c48bbe1b9193a006292f4#body_text
is schema:about of	named entity 'dominance' named entity 'probabilistic' named entity 'random' covid:arg/bd8bee485194f10f696c48bbe1b9193a006292f4 named entity 'BIOLOGICAL SEQUENCES' named entity 'SET' named entity 'JAVA' named entity 'HEURISTIC' named entity 'PRODUCTION' named entity 'ALGORITHM' named entity 'ALGORITHMS' named entity 'SOURCE' named entity 'SEARCH' named entity 'PROVIDING' named entity 'RECENT' named entity 'AVERAGE' named entity 'BEAM' named entity 'PROPERTY' named entity 'QUALITY' named entity 'GIVEN' named entity 'DOMINANCE' named entity 'COMMON' named entity 'EMPLOYS' named entity 'SEARCH ALGORITHM' named entity 'IBS' named entity 'OLIGONUCLEOTIDE MICROARRAY' named entity 'EXPERIMENTAL' named entity 'USES' named entity 'PROBLEM' named entity 'PAPER' named entity 'COMPARED' named entity 'FREELY' named entity 'DATA COMPRESSION' named entity 'PRUNE' named entity 'RANDOM' named entity 'APPLICATIONS' named entity 'REQUEST' named entity 'LARGE' named entity 'MEMBER OF' named entity 'OUR' named entity 'AVAILABLE' named entity 'REAL' named entity 'EXACT' named entity 'USED' named entity 'SOLUTIONS' named entity 'HIGHER' named entity 'CASES' named entity 'NEW' named entity 'PROPOSED' named entity 'BINARY' named entity 'IMPLEMENTATION' named entity 'HARD' named entity 'SPACE' named entity 'IS A' named entity 'SCS' named entity 'SHORTEST' named entity 'STRING' named entity 'OBTAIN' named entity 'microarray' named entity 'The' named entity 'member' named entity 'search space' named entity 'datasets' named entity 'search space' named entity 'NP-hard' named entity 'binary files' named entity 'Java' named entity 'Shortest Common Supersequence' named entity 'algorithm' named entity 'Genetic Algorithms' named entity 'beam search' named entity 'PBS' named entity 'algorithm' named entity 'SCS' named entity 'metaheuristic' named entity 'candidate solution' named entity 'algorithm' named entity 'SCS' named entity 'algorithm'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software