5

假设我有一个如下所示的二维数组：

GACTG
AGATA
TCCGA

每个数组元素都取自一个小的有限集（在我的例子中是 DNA 核苷酸 -- {A, C, G, T}）。我想以某种方式随机打乱这个数组，同时保留行和列核苷酸频率。这可能吗？能否高效完成？

[编辑]：我的意思是我想生成一个新矩阵，其中每一行的As、Cs、Gs 和Ts 的数量与原始矩阵的相应行相同，并且每列的As 数量相同，Cs, Gs 和Ts 作为原始矩阵的对应列。 置换原始矩阵的行或列通常不会实现这一点。 （例如，对于上面的示例，顶行有 2个，G每个1个A，C和TAGT

通过一次改组一列来保留列频率很简单，对于行也是如此。但这样做通常会改变另一种频率。

到目前为止我的想法： 如果可以选择 2 行和 2 列，以便这个矩形角的 4 个元素具有模式

XY
YX

对于一些不同的元素X和Y，然后将这 4 个元素替换为

YX
XY

将保持行和列频率。在顶部的示例中，可以对（至少）第 1 行和第 2 行以及第 2 和第 5 列（其角为 2x2 矩阵AG;GA）以及第 1 行和第 3 行以及第 1 和第 4 列（其角为GT;TG）执行此操作. 显然，这可以重复多次以产生某种程度的随机化。

概括一下，由行子集和列子集引起的任何“子矩形”，其中所有行的频率相同，所有列的频率相同，都可以将其行和列置换以产生一个有效的完整矩形。（其中，只有那些至少改变了 1 个元素的子矩形才是真正有趣的。）大问题：

  1. 是否所有有效的完整矩阵都可以通过一系列这样的“子矩形重排”到达？ 我怀疑答案是肯定的。
  2. 是否所有有效的子矩形重排都可以分解为一系列 2x2 交换？ [编辑]：mhum 的反例表明答案是否定的。不幸的是，因为这似乎使得想出一个有效的算法变得更加困难，但知道这一点很重要。
  3. 是否可以有效地计算部分或全部有效重排？

这个问题解决了一个特殊情况，其中可能元素的集合是{0, 1}。人们提出的解决方案与我自己提出的解决方案相似，并且可能可用，但并不理想，因为它们需要任意数量的回溯才能正常工作。我也担心只考虑 2x2 交换。

最后，理想情况下，我希望有一个解决方案可以证明可以从具有与原始相同行频率和列频率的所有矩阵集中随机均匀地选择一个矩阵。我知道，我要求很多:)

4

4 回答 4

3

The answer to question 2 is no. Consider the following 2 matrices:

A B C   C A B
C A B   B C A
B C A   A B C

They clearly have the same row and column frequencies. Yet, there is no 2x2 submatrix with common corners.

于 2011-02-23T06:38:08.177 回答
3

编辑：哎呀错过了OP问题的最后一段，让我改写一下。

简单地说，您链接到的问题对所选解决方案的随机性“水平”进行了非常有趣的讨论，请允许我解释一下：

“......我真的需要尽可能随机的矩阵......”

“......代码中实现的算法非常随机......”

“……如果你选择这种方法，另一种提高随机性的方法是重复随机化过程几次（随机次数）……”

这些评论都没有任何意义，没有“更多”随机之类的东西，这与这个可爱的Daily WTF 条目完全一样。也就是说，最后的报价几乎是关于某事的。众所周知，如果您模拟马尔可夫链，例如随机交换算法，只要足够长的时间，您最终将开始从稳态分布生成样本。正是该分布的样子，谁知道...

无论如何，根据您的目标，您可能并不真正关心此分布的外观，只要它包含足够的元素即可。所以某种交换算法可能有用，但我真的不希望这很容易，因为问题是 NP-Complete（比 Sudoku 更通用）。

考虑到这一点，您可以考虑使用任何适用于解决 Sudoku的方法来解决您的问题，如果您在 Acadamia，我建议您获取一份免费供学术使用的 IBM CPLEX 12 副本。您可以用他们的 CP 语言 (OPL) 编写一个类似数独的求解器，并作为整数线性程序求解器为您生成解决方案。我认为他们甚至有解决数独问题的示例代码，你可以借鉴。

这是我能想到的从此类矩阵中采样的唯一真正随机且无偏的方法：首先让 CPLEX 找到给定数独问题的所有N 个解。在你有了这组 N 个解之后，在 1 和 N 之间画一个随机数并使用那个解，如果你想要另一个，就画另一个数字。由于生成所有解决方案可能有点慢，您可以通过告诉求解器在一定数量的解决方案或时间过去后停止并且仅从该集合中采样来近似这样的事情。

于 2011-02-23T05:47:35.220 回答
2

事实证明，对于 0-1 矩阵，2x2 交换足以从一个矩阵到另一个矩阵。HJ Ryser 在一篇名为“零和一矩阵的组合特性”的论文中证明了这一点作为定理 3.1：http: //cms.math.ca/cjm/v9/cjm1957v09.0371-0377.pdf。一段时间以来，人们一直试图证明基于 2x2 互换的马尔可夫链可以快速混合；这篇论文http://arxiv.org/pdf/1004.2612v3似乎是最接近的。

如果有人可以证明 Ryser 定理对您的情况的推广（可能多达 4x4 的“交换”），那么由于交换的对称性，得到一个稳定状态分布均匀的链不会太难在感兴趣的矩阵上。我认为目前没有任何希望证明它可以快速混合所有可能的行/列分布，但也许你知道一些我们不知道的分布......

于 2011-02-23T13:02:45.167 回答
2

没有线索，但你所说的基本上是一个广义的数独求解器。试试http://scholar.google.com/scholar?q=sudoku

于 2011-02-23T05:18:06.293 回答