A two-stage constructive method for the unweighted minimum string cover problem

摘要

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 strings in S as compared to the current state-of-the-art method.