Студенты знакомятся с проблемой кольцевой дороги, пройдя курсы по биоинформатике, в частности, одним из самых качественных и близких по духу для программистов является курс «Биоинформатика» (Павел Певзнер) на Coursera Калифорнийского университета в Сан-Диего.
Задача привлекает внимание своей простотой постановки, практической значимостью, а также тем, что она до сих пор считается нерешенной, несмотря на кажущуюся возможность ее решения путем простого кодирования.
Проблема ставится так.
Можно ли восстановить координаты множества точек за полиномиальное время? 
, если известно множество всех попарных расстояний между ними 
?
Эта, казалось бы, простая задача до сих пор находится в списке нерешенных задач вычислительной геометрии.
Причем ситуация не касается даже точек в многомерных пространствах, особенно искривленных; проблема уже в самом простом варианте - когда все точки имеют целочисленные координаты и локализованы на одной прямой.
За почти полвека, прошедшие с тех пор, как математики признали эту проблему сложной задачей (Шамос, 1975), были получены некоторые результаты.
Рассмотрим два возможных случая одномерной задачи:
- точки расположены на прямой (задача магистрали)
- точки, расположенные на окружности (задача о кольцевой дороге)
И действительно, первая задача была решена довольно быстро (за 15 лет) и был построен алгоритм поиска с возвратом, восстанавливающий решение в среднем за квадратичное время.
, Где 
— количество баллов (Скиена, 1990); для второй задачи пока это сделать не удалось, а лучший предложенный алгоритм имеет экспоненциальную вычислительную сложность 
(Лемке, 2003).
На рисунке ниже показано примерное время, которое понадобится вашему компьютеру, чтобы решить набор с различным количеством точек.
То есть за психологически приемлемое время (~10 сек) можно восстановить многие
до 10 тыс.
точек в случае магистрали и всего ~10 точек в случае кольцевой дороги, что совершенно непригодно для практического применения.
Небольшое уточнение.
Считается, что проблема магистрали решена с точки зрения практического использования, то есть для подавляющего большинства встречающихся данных.
При этом игнорируются возражения чистых математиков о том, что существуют специальные наборы данных, для которых время получения решения экспоненциально.
(Чжан, 1982).
В отличие от магистрали, кольцевой дороги, задачу с ее экспоненциальным алгоритмом нельзя считать практически решенной.
Важность решения проблемы кольцевой дороги с точки зрения биоинформатики
В конце 20 века был открыт новый путь синтеза биомолекул, получивший название нерибосомального пути синтеза.Его главное отличие от классического пути синтеза состоит в том, что конечный результат синтеза вообще не кодируется в ДНК.
Вместо этого ДНК содержит только код «инструментов» (множества различных синтетаз), которые могут собирать эти объекты.
Таким образом, биомашинная инженерия значительно обогатилась, и вместо одного типа ассемблеров (рибосом), работающих всего с 20 стандартными частями (стандартными аминокислотами, также называемыми протеиногенами), клетка теперь имеет множество других типов ассемблеров, которые могут работать более чем с 500 стандартных и нестандартных частей (непротеиногенные аминокислоты и их различные модификации).
И эти ассемблеры умеют не только соединять детали в цепочки, но и создавать весьма сложные конструкции — циклические, ветвящиеся, а также конструкции со множеством циклов и разветвлений.
Все это существенно увеличивает арсенал клетки на разные случаи ее жизни.
Биологическая активность таких структур высока, специфичность (селективность действия) также высока, а разнообразие свойств не ограничено.
Класс этих клеточных продуктов в англоязычной литературе называется NRP (нерибосомальные продукты или нерибосомальные пептиды).
Биологи надеются, что именно среди таких продуктов клеточного метаболизма можно будет найти новые фармакологические препараты, обладающие высокой эффективностью и в силу своей специфичности не имеющие побочных эффектов.
Вопрос только в том: как и где искать НРП? Они очень эффективны, поэтому у клетки совершенно нет необходимости производить их в больших количествах, а их концентрации незначительны.
Это означает, что методы химической экстракции с их низкой точностью ~1% и огромными затратами реагентов и времени бесполезны.
Дальше.
Они не закодированы в ДНК, а значит, все базы данных, накопленные при расшифровке генома, и все методы биоинформатики и геномики также бесполезны.
Единственным способом что-то найти остаются физические методы, а именно масс-спектроскопия.
Более того, уровень обнаружения вещества в современных спектрометрах настолько высок, что позволяет обнаружить мизерные количества, всего > ~ 800 молекул (аттомольный диапазон, или концентрации 
).
"
Как работает масс-спектрометр? В рабочей камере устройства молекулы разрушаются на фрагменты (обычно за счет их столкновений друг с другом, реже за счет внешних воздействий).
Эти фрагменты ионизируются, а затем ускоряются и разделяются во внешнем электромагнитном поле.
Разделение происходит либо по времени достижения детектора, либо по углу поворота в магнитном поле, поскольку чем больше масса фрагмента и чем меньше его заряд, тем он более неповоротлив.
Таким образом, масс-спектрометр как бы «взвешивает» массы осколков.
Причем «взвешивание» можно производить многоступенчато, многократно отфильтровывая фрагменты с одинаковой массой (точнее, с одним значением).
) и прогоняем их через фрагментацию с дальнейшим разделением.
Двухстадийные масс-спектрометры широко распространены и называются тандемными; многоступенчатые масс-спектрометры встречаются крайне редко и называются просто 
, Где
— количество этапов.
И вот здесь возникает проблема: как узнать ее структуру, просто зная массы всех возможных фрагментов любой молекулы? Здесь мы подходим к задачам магистрали и кольцевой дороги для линейных и циклических пептидов соответственно.
Более подробно поясню, как задача восстановления структуры биомолекулы сводится к указанным проблемам на примере циклического пептида.
Циклический пептид ABCD на первой стадии фрагментации может разрываться в 4 местах либо по связи D-A, либо по A-B, BC или C-D, образуя 4 возможных линейных пептида - либо ABCD, BCDA, CDAB или DABC. Поскольку через спектрометр проходит огромное количество одинаковых пептидов, на выходе будут фрагменты всех 4 типов.
При этом отметим, что все фрагменты имеют одинаковую массу и не могут быть разделены на первом этапе.
На втором этапе линейный фрагмент ABCD может разорваться в трех местах, образуя более мелкие фрагменты с разными массами A и BCD, AB и CD, ABC и D и образуя соответствующий масс-спектр.
В этом спектре по оси x отложена масса фрагмента, а по оси y – количество мелких фрагментов с заданной массой.
Аналогично формируются спектры для остальных трех линейных фрагментов BCDA, CDAB и DABC. Поскольку все 4 крупных фрагмента перешли на второй этап, все их спектры суммируются.
Итого на выходе получается некий набор масс 
, Где 
- некоторая масса и 
- частота его повторения.
Однако мы не знаем, какому фрагменту принадлежит эта масса и является ли этот фрагмент уникальным, поскольку разные фрагменты могут иметь одинаковую массу.
Чем дальше друг от друга находятся связи в пептиде, тем больше масса пептидного фрагмента между ними.
То есть задача восстановления порядка элементов в циклическом пептиде сводится к задаче кольцевой дороги, в которой элементы множества
– связи в пептиде, а элементы множества
— массы фрагментов между связями.
Предчувствие возможности существования полиномиального алгоритма решения задачи кольцевой дороги
По своему опыту и из общения с людьми, которые пытались или действительно делали что-то для решения этой проблемы, я заметил, что подавляющее большинство людей пытаются решить ее либо в общем случае, либо для целочисленных данных в узком диапазоне, вот так ( 1, 50).Оба варианта обречены на провал.
Для общего случая доказано, что общее число решений задачи кольцевой дороги в одномерном случае равно 
ограничено значениями (Лемке, 2003) 
что означает наличие экспоненциального числа решений в асимптотике 
.
Очевидно, что если количество решений растет экспоненциально, то время их получения не может расти медленнее.
То есть для общего случая невозможно получить полиномиальное решение по времени.
Что касается целочисленных данных в узком диапазоне, то все можно проверить экспериментально, поскольку написать код, ищущий решение методом перебора, не слишком сложно.
Для маленьких
Расчет этого кода не займет много времени.
Результаты тестирования такого кода покажут, что при таких условиях данных общее количество различных решений для любого набора
уже на низком уровне
также растет чрезвычайно резко.
Узнав об этих фактах, вы сможете смириться и отказаться от этой задачи.
Признаюсь, это одна из причин, по которой проблема кольцевой дороги до сих пор считается нерешенной.
Однако лазейки все еще существуют. Напомним, что показательная функция 
ведет себя очень интересно.
Сначала оно растёт ужасно медленно, поднимаясь от 0 до 1 за бесконечно долгий период от 
до 0, затем его рост все больше ускоряется.
Однако чем ниже значение 
, тем больше должно быть значение 
так, чтобы результат функции превышал некоторое заданное значение 
.
В качестве такого значения удобно выбрать число 
, до него есть только одно решение, после него решений много.
Вопрос.
Кто-нибудь проверял зависимость количества решений от того, какие данные вводятся? Да, я проверил.
Есть замечательная кандидатская диссертация хорватского математика Тамары Дакич (Dakic, 2000), в которой она определила, каким условиям должны удовлетворять входные данные, чтобы задача решалась за полиномиальное время.
Важнейшие из них — уникальность решения и отсутствие дублирования в наборе входных данных.
.
Уровень ее кандидатской диссертации очень высок.
Жаль, что эта студентка ограничилась только проблемой магистрали; Я убежден, что если бы она обратила свой интерес на проблему кольцевой дороги, она была бы давно решена.
Получение полиномиального по времени алгоритма решения задачи кольцевой дороги
Случайно удалось обнаружить данные, для которых можно было построить нужный алгоритм.Требовалось больше идей.
Основная идея возникла из наблюдения (см.
выше), что спектр циклического пептида представляет собой сумму спектров всех линейных пептидов, образованных одиночными разрывами колец.
Поскольку последовательность аминокислот в пептиде можно восстановить по любому такому линейному пептиду, общее количество линий в спектре значимо (в
времена, когда
- количество аминокислот в пептиде) избыточно.
Вопрос только в том, какие линии нужно исключить из спектра, чтобы не потерять возможность восстановления последовательности.
Поскольку математически обе задачи (восстановление последовательности циклического пептида по масс-спектру и задача кольцевой дороги) изоморфны, можно также проредить множество
.
Прореживающие операции
были построены с использованием локальных симметрий множества
(Фомин, 2016а).
- Симметризация.
Первая операция – выбор произвольного элемента множества
и удалить из
все элементы, кроме тех, которые имеют симметричные пары относительно точек
И
, Где
— окружность (напомню, что в случае кольцевой дороги все точки расположены на окружности). - Свертка частичным решением.
Вторая операция использует наличие предположения о решении, т. е.
знания отдельных точек, принадлежащих решению, так называемого частичного решения.
Здесь из многих
все элементы также удаляются кроме тех, которые удовлетворяют условию - если измерить расстояния от проверяемой точки до всех точек частичного решения, то все полученные значения доступны в
.Уточню, что если хотя бы одно из полученных расстояний отсутствует в
, то точка игнорируется.
, но он все равно будет содержать достаточно элементов для восстановления решения
.
С помощью этих операций был построен и реализован на языке C++ алгоритм решения кольцевой задачи (Фомин, 2016б).
Алгоритм мало чем отличается от классического алгоритма поиска с возвратом (то есть мы пытаемся построить решение путем перебора возможных вариантов и делаем возвраты, если при построении получаем ошибку).
Разница лишь в том, что для подсчета сужения множества
У нас значительно меньше вариантов, которые мы можем попробовать.
Вот пример того, как резко сужается множество
во время прореживания.
Вычислительные эксперименты проводились для случайно сгенерированных циклических пептидов длиной
от 10 до 1000 аминокислот (ось ординат в логарифмическом масштабе).
По оси абсцисс также в логарифмическом масштабе отложено количество элементов в наборах, прореженных в результате различных операций.
в единицах
.
Эта идея совершенно необычна, поэтому я объясню, как она читается, на примере.
Посмотрите на левую схему.
Пусть пептид имеет длину 
.
Для него количество элементов в множестве
равно 
(это точка на верхнем пунктиру 
).
После удаления из набора
повторяющиеся элементы, количество элементов в
уменьшается до 
(круги с крестами).
После симметризации число элементов уменьшается до 
(черные кружки), а после свертки частичным решением 
(кресты).
Итого, общий объем набора
сокращается всего в 20 раз.
Для пептида такой же длины, но на правой диаграмме, аббревиатура происходит от
до 
, то есть в 100 раз.
Обратите внимание, что генерация тестовых примеров для левой диаграммы выполняется таким образом, чтобы уровень дублирования 
В
находился в пределах от 0,1 до 0,3, а для правого – менее 0,1. Уровень дублирования определяется как 
, Где 
- количество уникальных элементов в наборе
.
Это определение дает закономерный результат: при отсутствии дубликатов в множестве
его мощность равна 
И 
, с максимально возможным дублированием 
И 
.
Как обеспечить разные уровни дублирования, я расскажу чуть позже.
На диаграммах видно, что чем ниже уровень дублирования, тем больше прореживается
, в 
количество элементов в прореженном
обычно достигает своего предела 
, так как в прореженном множестве меньше 
элементы получить невозможно (операции хранят достаточно элементов для получения решения, в котором
элементы).
Факт сужения мощности набора
до нижнего предела очень важен, именно он приводит к резким изменениям вычислительной сложности получения решения.
После вставки операций прореживания в алгоритм обратного отслеживания и решения проблемы кольцевой дороги был обнаружен полный аналог того, о чем говорила Тамара Дакис относительно проблемы магистрали.
Позвольте мне напомнить вам.
Она сказала, что для проблемы магистрали можно получить решение за полиномиальное время, если решение уникально и нет дублирования в
.
Оказалось, что полное отсутствие дублирования не обязательно (вряд ли это возможно для реальных данных); достаточно, чтобы его уровень был достаточно небольшим.
На рисунке ниже показано, сколько времени потребуется для решения проблемы кольцевой дороги в зависимости от длины пептида и уровня дублирования в
.
На рисунке оси абсцисс и ординат даны в логарифмическом масштабе.
Это позволяет наглядно увидеть, зависит ли время счета от длины последовательности.
экспоненциальный (прямая линия) или полиномиальный (логарифмическая кривая).
Как видно на диаграммах, при малом уровне дублирования (правая диаграмма) решение получается за полиномиальное время.
Ну, если быть точнее, то решение получается за квадратичное время.
Это происходит, когда операции прореживания уменьшают мощность набора до нижнего предела.
, точек в нем осталось мало, возвраты при опробовании вариантов становятся единичными, и фактически алгоритм прекращает опробовать варианты, а просто конструирует решение из того, что осталось.
P.S. Ну и открою последний секрет, касающийся генерации наборов с разным уровнем дублирования.
Это связано с разной точностью представления данных.
Если данные формируются с низкой точностью (например, округление до целых чисел), то уровень дублирования становится высоким, более 0,3. Если данные формируются с хорошей точностью, например, до 3 знаков после запятой, то уровень дублирования резко снижается, менее 0,1. И отсюда следует последнее важнейшее замечание.
Для реальных данных, в условиях постоянно возрастающей точности измерений, задача кольцевой дороги становится решаемой в реальном времени.
Литература.
1. Дакич Т.
(2000).
О проблеме магистрали.
Докторская диссертация, Университет Саймона Фрейзера.
2. Фомин.
E. (2016a) Простой подход к восстановлению набора точек из мультимножества n ^ 2 попарных расстояний за n ^ 2 шагов для задачи секвенирования: I. Теория.
J Компьютерная Биол.
2016, 23(9):769-75. 3. Фомин.
E. (2016b) Простой подход к восстановлению набора точек из мультимножества n ^ 2 попарных расстояний за n ^ 2 шагов для задачи секвенирования: II. Алгоритм.
J Компьютерная Биол.
2016, 23(12):934-942. 4. Лемке П.
, Скиена С.
и Смит В.
(2003).
Реконструкция множеств по расстояниям между точками.
Алгоритмы дискретной и вычислительной геометрии и комбинаторика, 25:597–631. 5. Скиена С.
, Смит В.
и Лемке П.
(1990).
Реконструкция множеств по расстояниям между точками.
В материалах шестого симпозиума ACM по вычислительной геометрии, страницы 332–339. Беркли, Калифорния 6. Чжан З.
1982. Экспоненциальный пример алгоритма отображения частичного дайджеста.
Дж.
Комп.
Биол.
1, 235–240. Теги: #Алгоритмы #алгоритмы биоинформатики #масс-спектрометрия #проблемы с кольцевой дорогой и магистралью
-
История Математики
19 Oct, 24 -
Обзор Ноутбука Sony Vaio Vpc-Ec3L1E/Wi
19 Oct, 24 -
Еженедельный Геймдев: #70 — 15 Мая 2022 Г.
19 Oct, 24 -
Междугородние Путешествия – На Ракете
19 Oct, 24 -
Протезы Пальцев
19 Oct, 24 -
Фрагментация Android
19 Oct, 24
