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

作者：Lozano Manuel; Rodriguez Francisco J^*; Garcia Martinez Carlos

来源：Knowledge-Based Systems, 2015, 77: 103-113.

DOI：10.1016/j.knosys.2015.01.003

• Unweighted minimum string cover problem
• Constructive two-stage algorithm
• Combinatorial optimization
• Identifying parts within sets of DNA sequences
• Dictionary generation

In this work, we propose a novel constructive method to deal with the unweighted minimum string cover problem. Given a set of strings 5, 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.

• 出版日期2015-3