title: An Integer Programming Formulation of the Minimum Common String Partition Problem.
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.
authors.affiliation: 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.
authors.forename: S M
authors.initials: SM
authors.lastname: Ferdous
authors.affiliation: AℓEDA Group, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh.
authors.forename: M Sohel
authors.initials: MS
authors.lastname: Rahman
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000706:statistics & numerical data; D016678:Genome; D006801:Humans; D011382:Programming, Linear