In:
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, The Royal Society, Vol. 372, No. 2016 ( 2014-05-28), p. 20130134-
Abstract:
Problems related to string inclusion and non-inclusion have been vigorously studied in diverse fields such as data compression, molecular biology and computer security. Given a finite set of positive strings and a finite set of negative 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 to find 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 for consistent superstrings for given and . In our graph model, the set of strings represented by paths satisfying some conditions is the same as the set of consistent superstrings for and . We also present algorithms for the shortest and the longest consistent superstring problems. Our algorithms solve the consistent superstring problems for all cases, including cases that are not considered in previous work. Moreover, our algorithms solve in polynomial time the consistent superstring problems for more cases than the previous algorithms. For the polynomially solvable cases, our algorithms are more efficient than the previous ones.
Type of Medium:
Online Resource
ISSN:
1364-503X
,
1471-2962
DOI:
10.1098/rsta.2013.0134
Language:
English
Publisher:
The Royal Society
Publication Date:
2014
detail.hit.zdb_id:
208381-4
detail.hit.zdb_id:
1462626-3
SSG:
11
SSG:
5,1
SSG:
5,21
