2-MCSP：计算机科学中的关键问题，NP完全与近似算法
需积分: 9 195 浏览量
更新于2024-07-30
收藏 221KB PDF 举报
在计算机科学中，字符串比较是一个基本问题，它在生物计算、文本处理和数据压缩等领域具有广泛的应用。本文主要关注的是最小公共字符串分割问题（Minimum Common String Partition Problem，MCSP），这是一个与通过反转操作对重复字符进行排序（Sorting by Reversals with Duplicates）紧密相关的字符串比较问题，后者在基因组重组研究中扮演着关键角色。
MCSP定义为：给定两个字符串A和B，任务是找到一个共同的分割序列P和Q，使得Q是P的排列，并且分割序列的块数最少。当每个字符在输入字符串中出现次数限制为k时，这个问题的受限版本被称为k-MCSP，其中k=2的情况尤为关注，因为k-MCSP的难易度直接影响到整个问题。
本文的核心贡献在于证明了2-MCSP（以及更一般的情况MCSP）是NP-hard问题，这意味着没有多项式时间的算法可以解决所有实例。此外，论文还展示了2-MCSP的一个困难性，即它是APX-hard问题，这意味着即使对于近似最优解，也没有多项式时间内的算法能保证找到比某个固定常数因子更好的解。尽管如此，论文提供了两个重要的算法解决方案：
1. 对于2-MCSP，提出了一种1.1037-approximation算法，这意味着它能够在多项式时间内找到一个接近最优解的解，尽管不是最佳的近似率。
2. 对于3-MCSP，给出了一个线性时间的4-approximation算法，虽然效率上不如2-MCSP算法，但仍然可以在较短的时间内找到一个相对合理的解。
这些结果不仅揭示了MCSP问题的理论复杂性，也为实际应用中的字符串分析和优化提供了重要的理论基础。对于需要高效处理大量字符串比较和基因组重构任务的领域来说，理解和利用这些算法的局限性和优势至关重要。然而，对于更高值的k-MCSP版本，目前尚缺乏更有效的近似算法，这为未来的研究提出了挑战。
other hand, for a common partition π = hP, Qi interpreted as a permutation,
#blocks(π) ≥ #breaks(π) +1 (the inequality is due to possible unnecessary breaks
in π). Thus, the MCSP problem is to find a permutation π on [n] that preserves
letters of A and B and has the minimum number of breaks. An alternative
formulation is that the goal is to find a letter-preserving permutation that maps
the maximum number of pairs of consecutive letters in A to pairs of consecutive
letters in B.
Common partitions and independent sets. Let Σ denote the set of all letters that
occur in A. A duo is an ordered pair of letters xy ∈ Σ
2
that occur consecutively
in A or B (that is, there exists an i such that x = a
i
and y = a
i+1
, or x = b
i
and y = b
i+1
). A specific duo is an occurrence of a duo in A or B. The difference
is that a duo is just a pair of letters whereas a specific duo is a pair of letters
together with its position. A match is a pair (a
i
a
i+1
, b
j
b
j+1
) of specific duos,
one from A and the other one from B, such that a
i
= b
j
and a
i+1
= b
j+1
. Two
matches (a
i
a
i+1
, b
j
b
j+1
) and (a
k
a
k+1
, b
l
b
l+1
), i ≤ k, are in conflict if either i = k
and j 6= l, or i + 1 = k and j + 1 6= l, or i + 1 < k and {j, j + 1} ∩ {l, l + 1} 6= ∅.
Informally, two matches are in conflict if they cannot be realized at the same
time.
abc ab
ab abc
a bc ab
ab a bc
ab abc
ab c ab
ab ab c
ab c ab
abc ab
ab ab c
Fig. 1. Conflict graph for MCSP instance A = abcab and B = ababc.
We construct a conflict graph G = (V, E) of A and B as follows. The se t of
nodes V consists of all matches of A and B and the set of edges E consists of
all pairs of matches that are in conflict. Figure 1 shows an example of a conflict
graph. The number of vertices in G can be much higher than the length of the
strings A and B (and is trivially bounded by n
2
).
Lemma 1. For A = a
1
. . . a
n
and B = b
1
. . . b
n
, let MIS(G) denote the size
of the maximum independent set of the conflict graph G of A and B and m
denote the number of blocks in a minimum common partition of A and B. Then,
n − MIS(G) = m .
Proof. Given an optimal solution for MCSP, let S be the set of all matches
that are used in this solution. Clearly, S is an independent set in G and |S| =
n − 1 − (m − 1).
Conversely, given a maximum independent se t S, we cut the string A between
a
i
and a
i+1
for every specific duo a
i
a
i+1
that does not appear in any match in
剩余15页未读，继续阅读
2019-07-14 上传
2009-03-02 上传
2023-07-17 上传
2023-07-17 上传
2023-07-08 上传
2023-09-04 上传
2023-06-02 上传
2023-06-07 上传
renfengchao
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
