Back to Search Start Over

Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model

Authors :
Jin Wook Kim
Joong Chae Na
Jeong Seop Sim
Siwon Choi
Source :
Algorithms and Computation ISBN: 9783642106309, ISAAC
Publication Year :
2009
Publisher :
Springer Berlin Heidelberg, 2009.

Abstract

The problems that are related to string inclusion and non-inclusion have been vigorously studied in such diverse fields as data compression, molecular biology, and computer security. Given a finite set of negative strings ? and a finite set of positive strings ?, a string ? is a consistent superstring if every positive string is a substring of ? and no negative string is a substring of ?. The shortest (resp. longest) consistent superstring problem is finding a string ? that is the shortest (resp. longest) among all the consistent superstrings for the given sets of strings. In this paper, we first propose a new graph model based on the Aho-Corasick algorithm to represent the consistent superstrings for the given sets. Then, we propose improved algorithms for the problems of the shortest consistent superstring and the longest consistent superstring using the graph model.

Details

ISBN :
978-3-642-10630-9
ISBNs :
9783642106309
Database :
OpenAIRE
Journal :
Algorithms and Computation ISBN: 9783642106309, ISAAC
Accession number :
edsair.doi...........3372f3f8e8ee233c5bd3cd0c1f0cd01c
Full Text :
https://doi.org/10.1007/978-3-642-10631-6_119