Minimum common string partition revisited

Haitao Jiang (), Binhai Zhu (), Daming Zhu () and Hong Zhu ()
Additional contact information
Haitao Jiang: Montana State University
Binhai Zhu: Montana State University
Daming Zhu: Shandong University
Hong Zhu: East China Normal University

Journal of Combinatorial Optimization, 2012, vol. 23, issue 4, No 10, 519-527

Abstract: Abstract Minimum Common String Partition (MCSP) has drawn much attention due to its application in genome rearrangement. In this paper, we investigate three variants of MCSP: MCSP c , which requires that there are at most c elements in the alphabet; d-MCSP, which requires the occurrence of each element to be bounded by d; and x-balanced MCSP, which requires the length of blocks being in range (n/k−x,n/k+x), where n is the length of the input strings, k is the number of blocks in the optimal common partition and x is a constant integer. We show that MCSP c is NP-hard when c≥2. As for d-MCSP, we present an FPT algorithm which runs in O ∗((d!)2k ) time. As it is still unknown whether an FPT algorithm only parameterized on k exists for the general case of MCSP, we also devise an FPT algorithm for the special case x-balanced MCSP parameterized on both k and x.

Keywords: Minimum common string partition; Genomic distance; Genome rearrangement; NP-completeness; FPT algorithms (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9370-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:23:y:2012:i:4:d:10.1007_s10878-010-9370-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9370-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().