Article ID Journal Published Year Pages File Type
404942 Knowledge-Based Systems 2015 11 Pages PDF
Abstract

In this work, we propose a novel constructive method to deal with the unweighted minimum string cover problem. Given a set of strings S, this defiant optimization problem aims to find a minimum set of substrings M from S such that every string in S can be written as a concatenation of the strings in M. This problem has challenging real-world applications, especially in the field of computational biology.The proposed constructive algorithm is composed of two stages that are executed iteratively. The objective of the first stage is to find frequent substrings in S to be included in M. The aim of the second stage is to simplify the set M   to try to get a minimal set. Extensive computational experiments reveal that the proposed algorithm is highly effective for solving complex instances involving up to 100000 strings in S as compared to the current state-of-the-art method.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, , ,