带孔洞随机样本信号的重构

Question

作为我的硕士论文的一部分，我遇到了以下问题，在过去的几个星期里，我一直找不到合适的解决方案，所以我会问群众。

问题1

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

ABCBACBBBAACBAABCCBABBCA...  # 2000 Symbols long

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

ABCBACBBBAA
ACBBBAACBAABCCBAB
CBACBBBAACBAAB
BAABCCBABBCA
...

问题2(更难)

现在，从好的方面来说，我可以制作多少样本是没有限制的，而在不那么乐观的方面，故事还有更多。

1. 样品很吵。也就是说，可能会有错误。
2. 样本中有已知的洞。我只能观察每4-6符号一次。

因此，这些样本实际上看起来更像这样：

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

--我试过以下几种方法：

设S是所有有空穴的部分含噪序列的集合。

• 具有随机抽样和滑动窗口的贪婪算法。

1. Let _X_ be the the "best" sequence thus far.
2. Set _X_ as a random sample from _S_.
3. Choose a sequence _v_ from _S_
4. Slide _v_ along _X_ and score the match, and choose the "best" sequence as the new _X_.
5. Repeat from 3.

这个算法的问题是，我一直无法找到一个很好的指标来得分的序列。特别是当考虑到洞+噪音时。结果倾向于较短的序列，结果在随后的运行中有很大的差异。解决这一问题的想法是非常受欢迎的。

• 试图对齐序列的开始。 这种方法试图使用这样的事实:我可能能够识别字符串中可能构成未知序列开头的后缀。但是，由于样本中的漏洞，我甚至需要将匹配的序列移动几步左右。这导致了指数复杂性，并使问题难以解决。
• 我也玩过使用隐马尔可夫模型的想法，但在如何处理丢失的数据方面遇到了挫折。
• 其他的想法包括，尝试通过一个由字符串构建的图形(不要认为这是可行的)，网格解码维特比等等。

任何新的想法都是非常欢迎的。对相关文章的链接/引用就像天哪！

有关我的数据集的特定信息

• 我有三个符号S(开始)，A和B。
• 我是< 60%，确定任何给定的符号都是正确采样的。
• S符号应该在主序列开头出现几次，但由于分类错误而出现的频率更高。
• 在主序列中，符号B的出现频率是A的1.5倍。

Answer 1

问题1被称为最短公共超序列问题。这是NP-硬的两个以上的输入字符串，即使只有两个符号。问题2是多序列比对的一个实例。它有许多算法和实现，大部分是启发式的，因为它通常也是NP难的。