Журнал Компьютерра - Журнал «Компьютерра» №31 от 30 августа 2005 года

Другая задача, которая составляла основу проекта по реконструкции генома человека, - составление единой последовательности нуклеотидов из данных обрывков (задача возникает потому, что существующие биотехнологии не позволяют выявить структуры длинных последовательностей нуклеотидов - их приходится «разрезать» на кусочки и потом собирать по частям). Нечто вроде сборки паззла, только неизвестно, как сильно перекрываются кусочки и дают ли они в сумме полную картину.

Главная сложность, которая и делает подобные задачи интересными, - это, конечно, их размер[Мы никоим образом не хотим умалить трудности сугубо биологического характера: до середины 1970-х никто и мечтать не мог о том, что такие задачи вообще возникнут, и современное положение дел создано в первую очередь руками биологов. И сейчас биологические проблемы получения и интерпретации данных для комбинаторных задач стоят очень остро, но мы сейчас сконцентрируемся на математических трудностях]. Длина генома человека - более трех миллиардов нуклеотидов; собирать паззлы такого размера могут только компьютеры. А, например, пространство поиска для задачи sequence alignment для двух последовательностей длины 100 содержит порядка 1030 вариантов! Кроме того, задач еще и очень много (конечно, геном у человека один, но ведь есть и другие задачи, и другие организмы): база данных GenBank, содержащая практически всю известную на сей момент генетическую информацию, насчитывает в общей сложности около 50 млрд. нуклеотидов (желающие могут скачать базу с ftp.ncbi.nih.gov/genbank - только будьте готовы к тому, что в ней больше сотни гигабайт).

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

Например, одна из связанных с sequence alignment задач - найти минимальное количество операций разворота подпоследовательности (reversals), с помощью которых можно получить данную перестановку из единичной. Поскольку эта задача NP-полна (это означает, что, вероятнее всего, никакого алгоритма быстрее экспоненциального существовать для неё не может), теоретическая борьба шла за создание аппроксимационных алгоритмов, которые бы работали полиномиальное время и давали результат с приемлемой точностью. В 1995 году появился алгоритм, вычисляющий это количество с точностью 2 (т.е. он мог ошибаться в 2 раза). В течение последующих трёх лет этот результат различными исследователями улучшался трижды (!): сначала до 1.75, затем до 1.5, и, наконец, до 1.375.

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

Линейное программирование (ЛП) - это задача оптимизации линейной функции при линейных же на нее ограничениях. В наиболее простой переформулировке она сводится к тому, разрешима ли данная система линейных неравенств. Эта кажущаяся абстрактной задача имеет огромное количество применений и возникает в самых разных оптимизационных приложениях. В клиентах у крупнейшего производителя софта для решения задач ЛП - французской компании - ходят такие индустриальные гиганты, как Siemens, IBM, Visa International, France Telecom, United Airlines и многие другие. Говорят, что когда-то советская государственная программа развития Госплана фактически сводилась к тому, чтобы закодировать всю экономику СССР в виде огромной задачи линейного программирования, а потом ее решить и получить оптимальный план[Об этом Л. В. Канторович говорил в своей Нобелевской лекции. Кстати, векторы, лежащие в ограниченном задачей многограннике, в русской терминологии до сих пор называют планами].

Хотя о пользе решения систем линейных неравенств размышлял еще Фурье, впервые о применениях ЛП заговорили во второй четверти XX века. Начавшиеся исследования сразу же привели к успеху: по всей видимости, независимо друг от друга американец Джордж Данциг (George Dantzig) и советский математик Леонид Витальевич Канторович пришли (для разных, но эквивалентных формулировок исходной задачи) фактически к одному и тому же результату. Этот результат называется сейчас симплекс-методом; суть его - в обходе вершин соответствующего задаче многогранника в поиске оптимума. Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач. Важность его столь велика и бесспорна, что после того, как работы Канторовича были опубликованы, его приоритет доказан, а сам математик начал активно пропагандировать применение оптимизационных задач на практике, Л. В. Канторович получил Нобелевскую премию - по экономике, разумеется.