Эта с виду простая задача до сих пор находится в списке нерешенных проблем вычислительной геометрии. Причем ситуация даже не касается точек в многомерных пространствах, тем более искривленных, проблемой является уже самый простой вариант — когда все точки имеют целочисленные координаты и локализованы на одной линии.
За прошедшие почти полвека с тех пор, как эта задача была осознана математиками как вызов (Shamos, 1975), были получены некоторые результаты. Рассмотрим два случая возможных для одномерной задачи:
- точки расположены на прямой (turnpike проблема)
- точки расположены на окружности (beltway проблема)
Эти два случая получили разные названия не просто так — требуются различные усилия, чтобы их решить. И действительно, первая задача была решена достаточно быстро (за 15 лет) и построен backtracking алгоритм, восстанавливающий решение в среднем за квадратичное время

То есть, за психологически приемлемое время (~10 сек) можно восстановить множество
Небольшое уточнение. Считается, что turnpike проблема решена с точки зрения использования в практике, то есть для подавляющего большинства встречаемых данных. При этом игнорируются возражения чистых математиков на то, что существуют специальные наборы данных для которых время получения решения экспоненциально
Важность решение beltway проблемы с точки зрения биоинформатики
В конце 20 века был обнаружен новый путь синтеза биомолекул, названный нерибосомальным путем синтеза. Главное его отличие от классического пути синтеза в том, что конечный результат синтеза вообще не закодирован в ДНК. Вместо этого, в ДНК записан только код «инструментов» (множества различных синтетаз), которые могут собирать эти объекты. Таким образом, биомашинная инженерия существенно обогащается, и клетке вместо одного типа сборщика (рибосомы), выполняющего работы только с 20 стандартными деталями (стандартные аминокислоты, также называемые протеиногенными) появляются множество других типов сборщиков, которые могут работать с более чем 500 стандартными и нестандартными деталями (непротеиногенные аминокислоты и различные их модификации). И эти сборщики могут не просто соединять детали в цепочки, но и получать весьма замысловатые конструкции — циклические, ветвящиеся, а также конструкции со многими циклами и ветвлением. Все это существенно повышает арсенал клетки на разные случаи ее жизни. Биологическая активность таких конструкций высока, специфичность (избирательность действия) тоже, разнообразие свойств — не ограничено. Класс этих продуктов клетки в англоязычной литературе имеет название NRPs (non-ribosomal products, или non-ribosomal peptides). Биологи надеются, что именно среди таких продуктов метаболизма клетки можно найти новые фармакологические препараты, обладающие высокой эффективностью и за счет специфичности не имеющие побочных эффектов.
Вопрос состоит только в том, а как и где искать NRPs? Они весьма эффективны, следовательно клетке совершенно незачем продуцировать их в большом количестве, и концентрации их ничтожны. Значит химические методы извлечения с их низкой точностью ~1% и огромными затратами по реактивам и времени бесполезны. Далее. Они не кодированы в ДНК, значит все базы данных, что накоплены при расшифровке генома, и все методы биоинформатики и геномики также бесполезны. Единственным способом что-то найти остаются физические методы, а, именно, масс-спектроскопия. Тем более, что уровень обнаружения вещества у современных спектрометров настолько высок, что позволяет найти ничтожные количества, всего >~ 800 молекул (атто-молярный диапазон, или концентрации
" А как работает масс-спектрометр? В рабочей камере прибора происходит разрушение молекул на фрагменты (чаще путем их столкновений друг с другом, реже за счет внешнего воздействия). Эти фрагменты ионизуются, а затем разгоняются и разделяются во внешнем электромагнитном поле. Разделение происходит либо по времени достижения детектора, либо по углу разворота в магнитном поле, ведь больше масса фрагмента и ниже его заряд, тем более неповоротливым он является. Таким образом, масс-спектрометр как бы «взвешивает» массы фрагментов. Причем, «взвешивание» можно сделать многоэтапным, многократно отфильтровывая фрагменты с одной массой (точнее с одним значением
Поясню более детально, как задача восстановления структуры биомолекулы сводится к указанным проблемам на примере циклического пептида.

Циклический пептид ABCD на первом этапе фрагментации может быть разорван в 4-х местах, либо по связи D-A, либо по A-B, B-C или C-D, образуя 4 возможных линейных пептида — либо ABCD, BCDA, CDAB или DABC. Поскольку через спектрометр проходит огромное число одинаковых пептидов, то на выходе будем иметь фрагменты всех 4-х типов. Причем заметим, что все фрагменты имеют одинаковую массу, и не могут быть разделены на первом этапе. На втором этапе, линейный фрагмент ABCD может быть разорван в трех местах, образуя более мелкие фрагменты с разной массой A и BCD, AB и CD, ABC и D, и формируя соответствующий масс-спектр. В этом спектре по оси x откладывается масса фрагмента, а по оси y — число мелких фрагментов с данной массой. Аналогично формируются спектры для остальных трех линейных фрагментов BCDA, CDAB и DABC. Так как все 4 крупных фрагмента прошли на второй этап, то все их спектры складываются. Итого, на выходе получается некоторое множество масс
Предчувствие возможности существования алгоритма с полиномиальным временем решения beltway проблемы
Из своего опыта и из общения с людьми, кто пытался или реально что-то сделал для решения этой проблемы, я заметил, что подавляющее большинство людей пытаются решить ее либо в общем случае, либо для целочисленных данных в узком диапазоне, вроде такого (1, 50). Оба варианта обречены на неудачу. Для общего случая было доказано, что полное число решений для beltway проблемы в одномерном случае
Узнав о этих фактах можно смириться и махнуть рукой на эту задачу. Допускаю, что это является одной из причин по которой beltway проблема до сих пор считается нерешенной. Однако лазейки все же существуют. Вспомним, что экспоненциальная функция
Получение алгоритма с полиномиальным временем решения beltway проблемы
Обнаружить данные для которых возможно построить нужный алгоритм удалось случайно. Потребовались дополнительные идеи. Основная идея возникла из наблюдения (см. выше), что спектр циклического пептида является суммой спектров всех линейных пептидов, которые образуются при однократных разрывах кольца. Поскольку последовательность аминокислот в пептиде может быть восстановлена из любого такого линейного пептида, то полное число линий в спектре существенно (в
Операции прореживания
- Симметризация. Первая операция заключается в том, чтобы выбрать произвольный элемент множества
и удалить из
все элементы, кроме тех, которые имеют симметричные пары относительно точек
и
, где
— длина окружности (напомню, что в beltway случае все точки расположены на окружности).
- Конволюция по частичному решению. Вторая операция использует наличие догадки о решении, то есть знание отдельных точек, которые принадлежат решению, так называемое частичное решение. Здесь из множества
также удаляются все элементы, кроме тех, которые удовлетворяют условию — если мы измерим расстояния от проверяемой точки до всех точек частичного решения, то все полученные значения имеются в
. Уточню, что если хотя бы одно из полученных расстояний отсутствует в
, то точка игнорируется.
Были доказаны теоремы, что обе операции прореживают множество
Вот пример, как резко сужается множество

Вычислительные эксперименты выполнялись для случайно генерированных циклических пептидов длиной
Заметим, что генерация тестовых примеров для левой диаграммы выполняется таким образом, чтобы уровень дублирования
После вставка операций прореживания в backtracking алгоритм и в решении beltway проблемы выявился полный аналог того, о чем говорила Тамара Дакис относительно turnpike проблемы. Напомню. Она говорила, что для turnpike проблемы возможно получить решение за полиномиальное время, если решение единственно и отсутствует дублирование в

На рисунке обе оси абсцисс и ординат даны в логарифмическом масштабе. Это позволяет четко увидеть является ли зависимость времени счета от длины последовательности
P.S. Ну и раскрою последний секрет относительно генерации множеств в разным уровнем дублирования. Это связано с разной точностью представления данных. Если данные генерятся с низкой точностью (например округляя до целых чисел), то уровень дублирования становится высоким, более 0.3. Если данные генерить с хорошей точностью, например, до 3 знака после запятой, то уровень дублирования резко снижается, менее 0.1. И отсюда следует последнее наиболее важное замечание.
Для реальных данных, в условиях постоянно увеличивающейся точности измерений, beltway проблема становится разрешима в реальном времени.
Литература.
1. Dakic, T. (2000). On the Turnpike Problem. PhD thesis, Simon Fraser University.
2. Fomin. E. (2016a) A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n^2 Pairwise Distances in n^2 Steps for the Sequencing Problem: I. Theory. J Comput Biol. 2016, 23(9):769-75.
3. Fomin. E. (2016b) A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n^2 Pairwise Distances in n^2 Steps for the Sequencing Problem: II. Algorithm. J Comput Biol. 2016, 23(12):934-942.
4. Lemke, P., Skiena, S., and Smith, W. (2003). Reconstructing Sets From Interpoint Distances. Discrete and Computational Geometry Algorithms and Combinatorics, 25:597–631.
5. Skiena, S., Smith, W., and Lemke, P. (1990). Reconstructing sets from interpoint distances. In Proceedings of the Sixth ACM Symposium on Computational Geometry, pages 332–339. Berkeley, CA
6. Zhang, Z. 1982. An exponential example for a partial digest mapping algorithm. J. Comp. Biol. 1, 235–240.
