1

我给了 n 个字符串。我必须找到一个字符串 S，这样，给定 n 个字符串是 S 的子序列。例如，我给出了以下 5 个字符串：

    AATT
    CGTT
    CAGT
    ACGT
    ATGC

然后字符串是 "ACAGTGCT" 。. 因为，ACAGTGCT 包含所有给定的字符串作为超序列。要解决这个问题，我必须知道算法。但我不知道如何解决这个问题。伙计们，你能告诉我解决这个问题的技术吗？

4

3 回答 3

0 
1 Definitions

长度为 n 的序列是从字母表中提取的 n 个符号的串联。如果 S 是长度为 n 的序列并且 T 是长度为 m 和 nm 的序列，则如果 S 可以通过从 T 中删除 mn 个符号来获得，则 S 是 T 的子序列。符号不必是连续的。如果 T 可以通过插入 mn 个符号获得，则长度为 m 的序列 T 是长度为 n 的 S 的超序列。也就是说，T 是 S 的超序列当且仅当 S 是 T 的子序列。序列 T 是序列 S1 和 S2 的公共超序列 T 是 S1 和 S2 的超序列。

2 The problem

问题是找到一个最短公共超序列（SCS），它是一个最小长度的公共超序列。对于一个给定的问题，可能有不止一个 SCS。

2.1 Example


S= {a, b, c}
S1 = bcb
S2 = baab
S3 = babc

一种最短的常见超序列是 babcab (babacb, baabcb, bcaabc, bacabc, baacbc)。

3 Techniques

动态编程需要太多内存，除非输入序列的数量非常少。分支定界 除非字母非常小，否则需要太多时间。多数合并 当序列的数量与字母表大小相比较大时，最知名的启发式算法。[1] 贪心（取两个序列并用它们的最优最短公共超序列替换它们，直到剩下一个字符串）比多数合并更糟糕。[1] 遗传算法表明它可能比多数合并更好。[1]

4 Implemented heuristics

4.1 The trivial solution

平凡的解决方案至多是|| 乘以最优解长度并且通过将 sigma 中所有字符的串联与最长序列的串联次数相同而获得。也就是说，如果 = {a, b, c} 并且最长输入序列的长度为 4，我们得到 abcabcabcabc。4.2 多数合并启发式 多数合并启发式通过以下方式从空序列 (S) 建立一个超序列：

WHILE 有非空输入序列 s <- 非空输入序列开头最常见的符号。将 s 添加到 S 的末尾。从每个以 s 开头的输入序列的开头删除 s。结束时

当序列数量大于字母表大小时，多数合并表现得非常好。

5 My approach - Local search

我的方法是将局部搜索启发式应用于 SCS 问题并将其与多数合并启发式进行比较，以查看在字母表大小大于序列数的情况下它是否会做得更好。

由于有效超序列的长度可能会有所不同，并且对超序列的任何更改都可能使无效字符串直接表示超序列，因为可行的解决方案不是一种选择。

我选择将可行解决方案 (S) 视为一系列映射 x1...xSl，其中 Sl 是所有序列长度的总和，xi 是到序列号和索引的映射。

这意味着，如果 L={{s1,1...s1,m1}, {s2,1...s2,m2} ...{sn,1...s3,mn}} 是输入的集合序列和 L(i) 是第 i 个序列，映射表示如下：

xi {k, l}，其中 k L 和 l L(k)

为了确保任何解决方案都是有效的，我们需要引入以下约束：

  1. 每个序列中的每个符号可能只有一个 xi 映射到它。
  2. 如果 xi ss,k 和 xj ss,l 和 k < l 则 i < j。
  3. 如果 xi ss,k 和 xj ss,l 和 k > l 则 i > j。

第二个约束强制保留每个序列的顺序，但不保留其在 S 中的位置。如果我们有两个映射 xi 和 xj，那么我们只能在它们映射到不同序列时交换它们之间的映射。

5.1 The initial solution

有很多方法可以选择初始解决方案。只要保留序列的顺序，它就是有效的。我选择不以某种方式随机化解决方案，而是尝试两种截然不同的解决方案类型并进行比较。

第一个是通过简单地连接所有序列来创建初始解决方案。

第二个是一次将序列交错一个符号。即从每个序列的第一个符号开始，然后以相同的顺序取每个序列的第二个符号，依此类推。

5.2 Local change and the neighbourhood

通过交换解决方案中的两个映射来完成本地更改。进行迭代的一种方法是从 i 到 Sl 并为每个映射做最好的交换。另一种方法是尝试按照序列定义的顺序交换映射。即先交换s1,1，再交换s2,1。这就是我们所做的。

我尝试过两种变体。

在第一个中，如果单个映射交换没有产生更好的值，我会返回，否则我会继续。

在第二个中，我分别对每个序列进行与序列一样多的交换，因此每个序列中的符号将有可能移动。给出我保留的最佳值的交换，如果该值比算法中最后一步的值差，我返回，否则我继续。

只要交换不改变原始序列的顺序，符号就可以向左或向右移动任意数量的位置。

第一个变体中的邻域是可以为符号进行的有效交换的数量。在第二个变体中，它是在前一个符号被交换之后每个符号的有效交换的总和。

5.3 Evaluation

由于解的长度始终是恒定的，因此必须在获得解的实际长度之前对其进行压缩。

由映射组成的解 S 通过使用每个映射指向的符号转换为字符串。创建了一个新的、初始为空的解决方案 T。然后执行这个算法：

T = {}
  FOR i = 0 TO Sl
    found = FALSE
    FOR j = 0 TO |L|
       IF first symbol in L(j) = the symbol xi maps to THEN
          Remove first symbol from L(j)
          found = TRUE
       END IF
    END FOR 
    IF found = TRUE THEN  
      Add the symbol xi maps to to the end of T            
    END IF
  END FOR

Sl 和之前一样是所有序列的长度之和。L 是所有序列的集合，L(j) 是序列号 j。

得到解 S 的值作为 |T|。

非常感谢：Andreas Westling

于 2013-05-10T05:04:27.083 回答
0

我的方法：使用Trie

Building a Trie from the given words.
create empty string (S)
create empty string (prev)

for each layer in the trie
    create empty string (curr)
    for each character used in the current layer
        if the character not used in the previous layer (not in prev)
            add the character to S
            add the character to curr
    prev = curr

希望这可以帮助 ：）

于 2013-05-09T07:55:03.493 回答
0

这是一个 NP 完全问题，称为多序列比对。

wiki 页面描述了解决方法，例如动态编程，它适用于小 n，但对于较大的 n 变得过于昂贵。

基本思想是构造一个数组 f[a,b,c,...] 表示最短字符串 S 的长度，它生成第一个字符串的“a”字符，第二个字符串的“b”字符，以及“c” " 第三个字符。

于 2013-05-09T12:31:57.090 回答