An Integer Programming Formulation of the Minimum Common String Partition Problem

We consider the problem of finding a minimum common string partition (MCSP) of two strings, which is an NP-hard problem. The MCSP problem is closely related to genome comparison and rearrangement, an important field in Computational Biology. In this paper, we map the MCSP problem into a graph applying a prior technique and using this graph, we develop an Integer Linear Programming (ILP) formulation for the problem. We implement the ILP formulation and compare the results with the state-of-the-art algorithms from the literature. The experimental results are found to be promising.

我们研究了求解两个字符串的最小公共字符串划分（Minimum Common String Partition，MCSP）问题，该问题属于NP难问题。MCSP问题与计算生物学中的重要研究方向——基因组比较与重排密切相关。本文先采用已有技术将MCSP问题映射为图结构，随后基于该图结构为该问题构建了整数线性规划（Integer Linear Programming，ILP）模型。我们对该ILP模型进行了实现，并将其实验结果与现有文献中的当前最优算法进行了对比。实验结果表现优异，颇具应用前景。