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

Конечный (совсем небольшой) алфавит, дискретные объекты, четкие правила - ситуация идеально укладывается в общую концепцию computer science. Осталось лишь понять, что нужно сделать. Вот типичная задача (так называемая sequence alignment problem): предположим, что даны две последовательности нуклеотидов и набор возможных операций (мутаций) - например, удаление одного нуклеотида или замена одного нуклеотида на другой. Требуется определить минимальную (относительно весов, отражающих вероятности появления тех или иных мутаций) последовательность таких операций, которые первую последовательность переведут во вторую. Иным словами, нужно найти наиболее вероятную цепочку мутаций, которые привели к появлению слона из мухи или человека из обезьяны.

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

Главная сложность, которая и делает подобные задачи интересными, - это, конечно, их размер[Мы никоим образом не хотим умалить трудности сугубо биологического характера: до середины 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.