最小公共字符串划分问题的整数规划公式化表述。

An Integer Programming Formulation of the Minimum Common String Partition Problem.

作者信息

Ferdous S M, Rahman M Sohel

机构信息

Department of Computer Science and Engineering, Ahsanullah University of Science and Technology (AUST), Dhaka, Bangladesh; AℓEDA Group, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh.

AℓEDA Group, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh.

出版信息

PLoS One. 2015 Jul 2;10(7):e0130266. doi: 10.1371/journal.pone.0130266. eCollection 2015.

DOI:10.1371/journal.pone.0130266

PMID:26134848

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC4489654/

Abstract

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.

摘要

我们考虑寻找两个字符串的最小公共字符串划分（MCSP）的问题，这是一个NP难问题。MCSP问题与基因组比较和重排密切相关，而基因组比较和重排是计算生物学中的一个重要领域。在本文中，我们运用一种先前的技术将MCSP问题映射到一个图上，并利用这个图为该问题开发了一个整数线性规划（ILP）公式。我们实现了ILP公式，并将结果与文献中最先进的算法进行了比较。实验结果很有前景。