Доказательство того, что 40-летний алгоритм является оптимальным, будет облегчением для специалистов по вычислительным системам

Пишет Ларри Хардести | Новостное бюро MIT

Сравнение геномов различных видов или различных представителей одного вида — основа большей части современной биологии. Последовательности ДНК, встречающиеся у разных видов, могут оказаться функционально важными, в то время как различия в генах представителей одного вида могут указывать на восприимчивость к разным болезням.

Основному алгоритму для определения того, сколько у двух последовательностей символов общего, то есть так называемого редакционного расстояния между ними, уже больше 40 лет. И на протяжении 40 лет никому так и не удалось улучшить его.

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

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

«Я пытался улучшить алгоритмы для вычисления редакционного расстояния с тех пор, как был аспирантом в середине 90–х», — говорит Петр Индык, профессор компьютерных наук и инженерии в Массачусетском технологическом институте и соавтор доклада для STOC. «Я потратил на этого много бессонных ночей и так и не достиг никакого прогресса. По крайней мере, теперь можно спать спокойно».

Кроме того, по словам Индыка, несмотря на то, что доклад еще не был официально представлен, уже написаны две статьи, применяющие подход доклада к похожим задачам. «У этого доклада есть и техническая сторона, рассказывающая о конструкции некоторого гаджета, который оказался полезным для других целей», — говорит Индык.

Редакционное расстояние — это минимальное количество правок, то есть удалений, вставок и замен, необходимых для превращения одного ряда символов в другой. Стандартный алгоритм для определения редакционного расстояния, известный как алгоритм Вагнера — Фишера, присваивает каждый символ одной последовательности к столбцу в гигантской сетке, а каждый символ другой — к строке в этой сетке. Затем, начиная с верхнего левого угла и двигаясь по диагонали, он заполняет каждую ячейку количеством редакций, необходимых для превращения ряда символов, заканчивающегося соответствующим столбцом, в ряд, заканчивающийся соответствующей строкой

Специалисты по вычислительным системам эффективностью алгоритма считают отношение времени вычисления к количеству числа элементов, с которыми работает данный алгоритм. Так как алгоритм Вагнера — Фишера должен заполнить каждую ячейку сетки, время его работы прямо пропорционально длине двух последовательностей, которые он сравнивает. Если удвоить длины этих последовательностей, время выполнения увеличивается в четыре раза. Говоря языком компьютерщиков, алгоритм выполняется в квадратичное время.

Это вряд ли покажется вам очень эффективным, но квадратичная сложность гораздо лучше экспоненциальной сложности, когда время выполнения пропорционально 2N, где N — количество элементов, с которыми работает алгоритм. Если на определенном аппарате у алгоритма, работающего в квадратичном времени, ушла сотая секунды на обработку ста элементов, у алгоритма с экспоненциальной сложностью это займет около 100 квинтиллионов лет.

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

Основная NP-полная задача известна как «задача выполнимости»: учитывая множество логических ограничений, можно ли выполнить их все? Представим, что вы хотите организовать званый ужин и пытаетесь решить, кого пригласить. Вы можете столкнуться с рядом ограничений: либо Алисе, либо Бобу придется остаться дома с детьми, поэтому оба они прийти не смогут; если вы пригласите Синди или Дейва, вам придется также пригласить всех остальных участников книжного клуба, чтобы никто не почувствовал себя обделенным; Эллен придет либо с мужем Фредом, либо с любовником Джорджем, но не с обоими; и т.д. Существует ли список гостей, который учтет все эти ограничения?

Индык и Бачкурс в своем доказательстве предполагают, что столкнувшись с проблемой выполнимости, вы должны разделить переменные на две группы примерно одинакового размера: Алису, Боба и Синди надо поместить в одну, а Уолта, Ивонн и Зака — в другую. Затем для обеих групп вы должны решить эту задачу, учитывая все соответствующие ограничения. Такое вычисление может оказаться невероятно трудоемким, но зато намного менее сложным, чем вычисления для всей группы в целом. То, что, например, Заку нельзя приближаться к Алисе из-за запретительного судебного приказа, не имеет никакого значения, так как они находятся в разных подгруппах. Это ограничение не нужно учитывать.

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

«Это отличная работа», — говорит Барна Саха, доцент компьютерных наук в Университете штата Массачусетс в Амхерсте. «Много людей работали над этой задачей, потому что у нее есть значимое практическое применение. Но они уже не будут пытаться разработать субквадратичный алгоритм, потому что положительный результат маловероятен, если верить выводам этой работы».

Что касается предположения, на котором основано доказательство ученых MIT, что NP-полные задачи не могут быть решены в субэкспоненциальное время, Саха объясняет: «Многие ученые верят в эту гипотезу. Существует много других работ в области сложности низкого полиноминального времени, которые полагаются на эту гипотезу».

Перевод  «Longstanding problem put to rest. Proof that a 40-year old algorithm is the best possible will come as relief to computer scientists»