An Integer Programming Formulation of the Minimum Common String Partition Problem.
Where this comes from
- Record sourced from PubMed, PMID 26134848.
- Also identified by DOI 10.1371/journal.pone.0130266 and PMC identifier 4489654.
- Licence recorded as CC BY.
- The licence permits redistribution, so the abstract is shown in full and the full text is available from the publisher.
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.
Medical subject headings
- Algorithms
- Genome
- Programming, Linear