Можно ли перетасовать 2D-матрицу, сохраняя частоты строк и столбцов?

Question

Предположим, у меня есть двумерный массив, подобный следующему:

GACTG
AGATA
TCCGA

Каждый элемент массива взят из небольшого конечного набора (в моем случае, нуклеотидов ДНК - {A, C, G, T}). Я хотел бы как-то случайным образом перемешать этот массив, сохраняя при этом частоты нуклеотидов столбцов и . Это возможно? Можно ли сделать это эффективно?

[EDIT] : Я имею в виду, что хочу создать новую матрицу, в которой каждая строка имеет одинаковое количество A s, C s, G s и T s как соответствующая строка исходной матрицы, и где каждый столбец имеет то же число A s, C s, G s и T s, что и соответствующий столбец исходной матрицы. Перестановка строк или столбцов исходной матрицы в общем случае не приведет к этому. (Например, для приведенного выше примера верхняя строка имеет 2 G с и 1 каждый из A, C и T; если эту строку поменять местами со строкой 2, верхняя строка в результирующей матрице будет иметь 3 A s, 1 G и 1 T.)

Достаточно просто сохранить только частоты столбцов, перетасовывая столбец за раз, а также для строк. Но в общем случае это изменит частоты другого типа.

Мои мысли пока: Если возможно выбрать 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}. Решения, которые придумали люди, похожи на те, что я придумал сам, и, вероятно, пригодны для использования, но не идеальны, поскольку для правильной работы им требуется произвольное количество возвратов. Также меня беспокоит, что рассматриваются только свопы 2х2.

Наконец, в идеале мне бы хотелось решение, которое, как можно доказать, выбрало бы матрицу равномерно случайным образом из набора всех матриц, имеющих частоты строк и столбцов, совпадающие с исходными. Я знаю, я прошу много:)

Answer 1

Редактировать: упс пропустил последний абзац вопроса ОП, позвольте мне перефразировать.

Если коротко, то вопрос, на который вы ссылались, имел довольно веселую дискуссию об "уровне" случайности для выбранного решения,позвольте мне перефразировать:

"... Мне действительно нужны матрицы, которые являются как можно более случайными ..."

"... Алгоритм, реализованный в коде, совершенно случайно ... "

" ... если вы выберете этот метод, другой способ улучшить случайность - это повторить процесс рандомизации несколько раз (случайное число раз) ... "

Ни один из этих комментариев не имеет никакого смысла, не существует такого понятия, как «более» случайное, все это точно так же, как эта прекрасная Ежедневная запись в WTF .Тем не менее, последняя цитата почти на что-то.Хорошо известно, что если вы будете моделировать цепочку Маркова, как этот алгоритм случайной замены, достаточно долго, вы в конечном итоге начнете генерировать выборки из стационарного распределения .Как именно выглядит этот дистрибутив, кто знает ...

В любом случае, в зависимости от ваших целей, вам может быть наплевать, как выглядит этот дистрибутив, если он содержит достаточно элементов.Так что некоторый алгоритм обмена может быть полезен, но я действительно не ожидал бы, что это будет легко, так как проблема в NP-Complete (более общей, чем Sudoku).

Имея это в виду, вы можете рассмотреть решение своей проблемы любым подходом, который подходит для решения Судоку , если вы находитесь в Acadamia, я бы предложил получить копию IBM CPLEX 12, бесплатную дляакадемическое использование.Вы можете закодировать решение, похожее на судоку, на их языке CP (OPL) и в качестве целочисленного линейного решателя программ для генерации решений для вас.Я думаю, что у них даже есть пример кода для решения судоку, который вы можете позаимствовать.

Вот единственный действительно случайный и непредвзятый способ, которым я могу придумать для выборки из таких матриц: сначала получите CPLEX, чтобы найти всех N решений данной проблемы Судоку.Получив этот набор из N решений, нарисуйте случайное число от 1 до N и используйте это решение, если хотите другое, нарисуйте еще одно число.Поскольку генерация всех решений может быть немного медленной, вы можете приблизить что-то подобное, сказав решающему остановиться после определенного количества решений или времени и только выборки из этого набора.

Answer 2

Ответ на вопрос 2 - нет.Рассмотрим следующие 2 матрицы:

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

Они явно имеют одинаковые частоты строк и столбцов.Тем не менее, нет подматрицы 2x2 с общими углами.

Answer 3

Оказывается, что для матриц 0-1 достаточно 2x2 перестановок, чтобы перейти от одной матрицы к другой. Это доказал H J Ryser в качестве теоремы 3.1 в статье «Комбинаторные свойства матриц нулей и единиц»: http://cms.math.ca/cjm/v9/cjm1957v09.0371-0377.pdf. Некоторое время люди пытались доказать, что цепь Маркова, основанная на свопах 2х2, быстро смешивается; эта статья http://arxiv.org/pdf/1004.2612v3 кажется самой близкой.

Если бы можно было доказать обобщение теоремы Райзера на ваш случай (может быть, с помощью «свопов» до 4х4), то из-за симметрии свопов было бы не сложно получить цепочку с устойчивым состоянием Распределение равномерно по интересующим матрицам. Я не думаю, что на данный момент есть надежда доказать, что он быстро смешивается для всех возможных распределений строк / столбцов, но, возможно, вы знаете что-то о распределениях, которых у нас нет ...

Answer 4

Понятия не имею, но то, о чем вы говорите, это в основном обобщенный решатель судоку.Попробуйте http://scholar.google.com/scholar?q=sudoku