5

次のような 2D 配列があるとします。

GACTG
AGATA
TCCGA

各配列要素は、小さな有限セット (私の場合、DNA ヌクレオチド -- {A, C, G, T}) から取得されます。行と列の両方のヌクレオチド頻度を維持しながら、この配列を何らかの形でランダムにシャッフルしたいと思います。これは可能ですか？それは効率的に行うことができますか？

[編集] : これは、各行が元の行列の対応する行と同じ数のAs、Cs、Gs およびs を持ち、各列が同じ数のsを持つ新しい行列を作成したいということです。元の行列の対応する列としての s、s、およびs。元の行列の行または列を並べ替えても、一般にこれは達成されません。 (例えば、上記の例では、一番上の行には が 2つあり、とがそれぞれ 1 つずつあります。この行が行 2 と交換された場合、結果の行列の一番上の行には1と 1の 3 つが含まれます。)TACGTGACTAGT

一度に列をシャッフルすることで列の頻度だけを保持するのは簡単で、行についても同様です。しかし、これを行うと、一般に他の種類の周波数が変更されます。

これまでの私の考え: この長方形の角にある 4 つの要素がパターンを持つように、2 行 2 列を選択することが可能であれば

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 の反例は、答えがnoであることを示しています。残念ながら、これにより効率的なアルゴリズムを考え出すことが難しくなるように思われるため、知っておくことは重要です。
  3. 有効な再配置の一部またはすべてを効率的に計算できますか?

この質問は、可能な要素のセットが である特殊なケースに対処します{0, 1}。人々が思いついた解決策は、私が思いついたものと似ており、おそらく使用可能ですが、正しく機能するには任意の量のバックトラックが必要になるため、理想的ではありません. また、2x2 スワップのみが考慮されることも懸念しています。

最後に、元の行列と同じ行周波数と列周波数を持つすべての行列のセットから行列を一様にランダムに選択することを証明できるソリューションが理想的です。私は知っています、私はたくさん求めています:)

4

4 に答える 4

3

質問 2 の答えはノーです。次の 2 つの行列を考えてみましょう。

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

行と列の頻度は明らかに同じです。しかし、共通のコーナーを持つ 2x2 サブマトリックスはありません。

于 2011-02-23T06:38:08.177 に答える
3

編集：おっと、OPの質問の最後の段落を見逃しました。言い換えさせてください。

簡単に言うと、リンク先の質問では、選択したソリューションのランダム性の「レベル」について非常に陽気な議論がありました。言い換えると、次のようになります。

「...できるだけランダムな行列が本当に必要です...」

「...コードに実装されているアルゴリズムは、かなりランダムです...」

「...この方法を選択した場合、ランダム性を向上させる別の方法は、ランダム化プロセスを数回 (ランダムな回数) 繰り返すことです...」

これらのコメントはどれも意味をなしません。「もっと」ランダムなものはありません。これはすべて、この素敵なデイリー WTF エントリとまったく同じです。とはいえ、最後の引用はほとんど何かにかかっています。ランダム スワッピング アルゴリズムのようなマルコフ連鎖を十分長くシミュレートすると、最終的に定常状態分布からサンプルを生成し始めることはよく知られています。まさにその分布がどのように見えるか、誰が知っていますか...

とにかく、目的によっては、十分な要素が含まれている限り、このディストリビューションがどのように見えるかはあまり気にしないかもしれません。したがって、ある種のスワッピング アルゴリズムが役立つ可能性がありますが、問題が NP-Complete (数独よりも一般的) であるため、これが簡単であるとは本当に期待できません。

それを念頭に置いて、数独を解決するのに役立つ任意のアプローチで問題を解決することを検討できます。アカデミアにいる場合は、教育機関向けに無料で使用できる IBM CPLEX 12 のコピーを入手することをお勧めします。CP 言語 (OPL) で数独のようなソルバーをコーディングし、整数線形計画法ソルバーとしてソリューションを生成することができます。借りられる数独を解くためのコード例もあると思います。

このような行列からサンプリングするために私が考えることができる唯一の真にランダムで偏りのない方法は次のとおりです。まず、CPLEX を取得して、指定された数独問題の N 個の解をすべて見つけます。この N 個の解のセットを取得したら、1 から N までの乱数を描画し、その解を使用します。別の解が必要な場合は、別の数を描画します。すべてのソリューションを生成するには少し時間がかかる可能性があるため、特定の数のソリューションまたは時間が経過したら停止し、そのセットからのみサンプリングするようにソルバーに指示することで、このようなものに近づけることができます。

于 2011-02-23T05:47:35.220 に答える
2

0-1 行列の場合、ある行列から別の行列に移動するには 2x2 スワップで十分であることがわかります。これは、HJ Ryser によって「0 と 1 の行列の組み合わせのプロパティ」という論文の定理 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 に答える