@Kpoxal

На листе в клетку последовательно (от A до Z) выложена цепочка букв алфавита. Каждая буква в отдельной клетке, каждая последующая буква рядом с предыдущей (слева, справа, выше или ниже). Цепочка нигде не пересекает себя, но может касаться.

На примере ниже цепочка A..K касается сама себя в буквами C и J.

...K
ABCJI
..D.H
..EFG

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

Задача имеет приложения в биоинформатике, связанное с восстановлением структуры хроматина. Оптимальное решение неизвестно.

0

@Kpoxal

Вот и зашли в тупик. Природу такого ограничения понять можно, если использовать геометрию объекта (к одному состоянию объекта относятся все геометрические и, в меньшей мере, топологические формы объекта, которые в 3D пространстве дают доступ к тем петлям хроматина, с которых транскрибируются заданные совокупности белков). Но формализовать такое ограничение без использования геометрической картины [практически] невозможно.

0

@wingblack

Попробуйте описать правило геометрически, тогда можно будет попытаться вывести правило для топологии.

0

@Kpoxal

Если попытаться формализовать условие "к одному состоянию объекта относятся все геометрические .. формы объекта, которые в 3D пространстве дают доступ к тем петлям хроматина, с которых транскрибируются заданные совокупности белков", то получается следующее:

1) выполняем генерацию ансамбля геометрических структур цепочки, удовлетворяющих ограничениям по контактам (оставляя за рамками эффективность такой генерации)
2) для каждой полученной структуры определяем совокупность "шаров", которые открыты (не окружены со всех сторон соседями), то есть каждая структура отображается в последовательность типа A..DEFG..JK..NOPQRS.....YZ (где буквами отмечены открытые "шары"). Как результат, имеем совокупность последовательностей, типа: ...DE..HIJ.........TUVWXYZ | A.CD..GHI......PQRSTUV..YZ | ..CDE..HIJ....OPQ..TUVWX.. | A...EFGHIJKLMNOPQRS...WXYZ
3) выполняем кластеризацию полученной совокупностей последовательностей, тем самым геометрические структуры, в которых открыты одни и те же петли для транскрипции, попадают в одну и ту же группу.
Итого, имеем отображение совокупности ограничений по контактам в группы геометрических последовательностей с одинаковыми открытыми участками.

При всем этом, исходная задача - эффективная генерация структур, удовлетворяющих заданным ограничениям по контактам, по прежнему остается открытой.

Добавлено через 5 часов 51 минуту
Почему то никто не предложил в качестве идеи увеличения эффективности генерации конфигурация снижение точности (переход к более крупной сетке). Во всей последовательности любые два соседа объединяются в новый "шар", вводится новая нумерация. Если в паре есть "шар" с контактом, то эта пара объявляется объектом, имеющим контакт. И решается та же задача, но с уменьшенным числом "шаров" в цепочке.

А возвращаться к исходной точности можно только для отфильтрованных конфигураций.

0

@wingblack

Наверное потому что это не настолько очевидно и удобно. Если вместо 2-х шаров брать один, то тогда будет неоднозначность какой из шаров (или же оба)склеивать если есть склейка. К тому же, новые склейки будут появляться только между такими парами, что уменьшит количество получаемых вариантов также вдвое, а вдруг это существенно отразится на результатах исследования?

Можно вывести это самое ограничение по контактам? Если хотите - в упрощенном виде.

С остальными пунктами пока проще, в (2) выбираем шары без склеек, в (3) вводим одну или несколько функций определения расстояния между состояниями и кластеризируем. Кстати, вот это место возможно тоже требует уменьшение вычислений, т.к. прямое сравнение потребует порядка N² тяжелых операций.

0

@Kpoxal

Я выразился неточно. Нужно "удовлетворяющих требованиям[а не ограничениям] по контактам". Требования задаются во входных данных.

Не так. Назовем склейкой известный и заданный во входных данных контакт. Неизвестные контакты (а они всяко будут при генерации цепи) назовем просто контактами. Итого в (2) выбираются шары, имеющие малое число контактов (у которых в локальной окрестности есть пустые клетки).
Здесь опять неточность. Наличие пустых клеток годится как некоторое приближение. Более точно нужно проанализировать эти пустые места. Имеют ли они выход за пределы нашей цепи? Если нет, то это пустое место - некоторая пустая область внутри нашей цепи. Если она не имеет выхода наружу, то к ней нет доступа. То есть, ее нужно игнорировать.

да, прямое сравнение имеет N^2 операций. Но это ничтожно мало по сравнению с числом операций генерации хотя бы одной конфигурации 3^N.

Добавлено через 5 часов 27 минут
Глупость я написал, перепутал N - число конфигураций и длину цепи L.

Добавлено через 12 часов 40 минут
Если данные хорошо кластеризуются, то кластеризация может быть выполнена за N операций. Первый объект формирует первый класс и является его представителем. Далее вводится некоторым образом расстояние между объектами. Вычисляется расстояние между вторым объектом и представителем первого класса. Если расстояние меньше заданного, то второй объект помещается в первый класс. Если больше, то формируется второй класс, и второй объект является его представителем. И так далее. Все сравнения для любого нового объекта производятся не со всем объектами имеющихся классов, а с их представителями. Итого, число операций линейно.

0