algorithm - 从带孔的随机样本中重建信号

Question

我在硕士论文中遇到了以下问题，最近几周一直找不到合适的解决方案，我会请教群众。

问题1

假设存在一个已知长度的(未知)符号序列。比如说

ABCBACBBBAACBAABCCBABBCA...  # 2000 Symbols long

现在，给定序列中任意位置的 N 个样本，任务是重建原始序列。例如:

ABCBACBBBAA
ACBBBAACBAABCCBAB
CBACBBBAACBAAB
BAABCCBABBCA
...

问题2(更难)

现在，从好的方面来说，我可以制作的 sample 数量没有限制，而在不那么好的方面，还有更多的故事。

1. 样本有噪音。即可能存在错误。
2. sample 中有已知的孔洞。我只能观察每 4-6 个符号。

因此样本实际上看起来更像这样:

A   A     A
A    A   A   C
C   B     B
B     B    C*     # The C should have been an A.
...

我尝试了以下方法:

设 S 为所有带孔的部分噪声序列的集合。

• 带有随机采样和滑动窗口的贪心算法。

  1. 让 X 成为迄今为止“最佳”序列。
  2. 将X设置为S中的随机样本。
  3. 从S中选择一个序列v
  4. 沿着 X 滑动 v 并对匹配进行评分，然后选择“最佳”序列作为新的 X。
  5. 从 3 开始重复。

  这个算法的问题是我一直无法找到一个好的指标来对序列进行评分。特别是在考虑孔+噪声时。结果倾向于支持较短的序列，并且在随后的运行中结果非常不同。欢迎提出解决此问题的想法。

• 尝试对齐序列的开头。

  这种方法试图利用这样一个事实，即我可能能够识别可能构成未知序列开头的字符串中的后缀。但是，由于样本中存在漏洞，我什至需要将匹配序列向右或向左移动几步。这导致指数级的复杂性并使问题变得棘手。

• 我也曾考虑过使用隐马尔可夫模型，但在如何处理缺失数据方面受挫。

• 其他想法包括，尝试最大流通过从字符串构建的图形(我认为这行不通)，网格解码 [Viterbi](看不出我如何处理从中间开始的样本未知序列)等等。

非常欢迎任何新鲜的想法。相关文章的链接/引用就像甘露!

关于我的数据集的具体信息

• 我有三个符号 S(开始)、A 和 B。
• 我是 < 60%某些给定的符号被正确采样。
• S 符号应该只在主序列的开头出现几次，但由于分类错误确实出现得更多。
• 符号 B 在主序列中出现的频率大约是 A 的 1.5 倍。

Answer 1

问题 1 被称为最短公共(public)超序列问题。对于两个以上的输入字符串，即使只有两个符号，它也是 NP-hard。问题 2 是 Multiple Sequence Alignment 的一个实例.它有许多算法和实现，大多数是启发式的，因为它通常也是 NP 难的。