От науки к интернет-играм-
коллективное решение биоинформатических задач
М.С.Гельфанд
В биоинформатике есть много задач, которые наиболее эффективно решаются сочетанием компьютерного и экспертного анализа. В методических разделах научных статей этап «сделали вручную» обычно не афишируется, потому что его трудно строго описать, в то же время ручная подгонка, например, выравниваний последовательностей считается совершенно естественной и приемлемой. Однако есть случаи, в которых такая обработка — основной технический прием, причем производится она не группой специалистов, а большим сообществом пользователей Интернета. Это связано с тем, что для многих задач относительно легко построить функционал, оценивающий качество решения, но вычислительно очень сложно его оптимизировать: пространство решений велико и имеет множество локальных оптиму-мов. Оказалось, что, если оформить задачу поиска оптимального решения как интернет-игру, найдется множество желающих в ней поучаствовать.
Первый проект
Исторически первым проектом такого рода стала игра «Foldit» (от англ. fold it — сложи это), направленная на решение тради-
© Гельфанд М.С., 2014
Михаил Сергеевич Гельфанд, доктор биологических наук, профессор, член Европейской академии, заместитель директора Института проблем передачи информации им.А.А.Харкевича РАН, профессор факультета биоинженерии и биоинформатики МГУ им.М.В.Ломоносова. Область научных интересов — биоинформатика, сравнительная и функциональная геномика, молекулярная эволюция, системная биология, метагеномика.
ционной задачи вычислительной биологии и биофизики — предсказание пространственной структуры белка по его аминокислотной последовательности. Экспериментальные методы анализа белковой структуры, кристаллография и ЯМР-спектроскопия, очень трудоемки. Компьютерное же прогнозирование полезно при определении функции белка, поиске взаимодействующих с ним малых молекул (а значит, конструировании лекарств) и анализе белок-белковых взаимодействий. Кроме того, для предсказаний, сделанных с помощью компьютерных программ, уровень соответствия действительности показывает, насколько хорошо мы понимаем механизмы образования пространственной структуры. Все началось с проекта «Rosetta@home». Создатели алгоритма «Rosetta», который предсказывал пространственную структуру белка ab initio, без учета информации о структурах родственных ему белков, построили такую функцию вычисления свободной энергии, которая, как правило, имела минимум для нативной структуры молекулы [1]. Но, как это часто бывает в биоинформатике, высокое качество функционала привело к сложностям его оптимизации для конкретных белков: вычисления занимали слишком много времени. Тогда авторы обратились к опыту проекта «SETI@home», в котором владельцам персональных компьютеров предлагали пожертвовать свободное время своих процессоров для поиска сигналов внеземных цивилизаций. Аналогичная программа распределенных вычислений была разработана и на основе алгоритма «Rosetta». Компьютерная заставка показывала текущую структуру белка, и пользователи часто наблюдали, как алгоритм подолгу блуждает в окрестности локального оптимума, не делая очевидных
с точки зрения человека шагов (например, таких, как перемещение внутрь молекулы торчащего наружу большого гидрофобного остатка). Дело в том, что разложение этого действия на элементарные составляющие, которыми оперирует алгоритм, требует отклонения в область высоких энергий, так как молекулу надо локально «распутать» (что энергетически невыгодно), переместить гидрофобный остаток, а потом «свернуть» заново. Поэтому, пообщавшись с такими пользователями, авторы проекта решили привлечь их к решению содержательных научных задач.
Для этого был разработан простой веб-интерфейс (рис.1) с естественным набором элементарных операций. Некоторыми участник игры управлял с помощью компьютерной мыши. Так, можно было перемещать индивидуальный аминокислот-
ный остаток (и связанные с ним остатки — с сохранением стерических ограничений) или целый элемент молекулярной структуры. Другие операции представляли собой упрощенные (для сокращения времени) версии процедур базового алгоритма «Rosetta» — это глобальная оптимизация свободной энергии либо, наоборот, ее локальная минимизация за счет движений основной цепи в заданном интервале или за счет поворотов боковых остатков. Кроме того, визуальный интерфейс выделял пространственные конфликты между боковыми остатками, которые необходимо разрешить, а также энергетически невыгодные пустоты в структуре и торчащие наружу гидрофобные остатки. Был разработан набор учебных задач, который вводил элементарные операции и давал возможность пользователям понять, как они работают.
Рис.1. Снимок экрана компьютера с загруженной игрой <^о1сИЪ> [2]. Стрелками отмечено, что программа показывает пользователю в процессе его работы над пространственной структурой белка (изображенного в центре): атомы, находящиеся слишком близко друг к другу (1); водородные связи (2); открытые гидрофобные (3), гидрофильные (4) и обладающие высокой энергией (5) аминокислотные остатки. Игрок может вносить модификации в структуру, например, вводя связи (6), ограничивающие применение каких-либо операций, или «замораживая» степени свободы (7), что препятствует их изменению. Графический интерфейс пользователя также показывает текущие баллы игрока (8), рекорды других участников (9), панель с доступными операциями (10), средство общения с другими игроками (11) и инструменты создания новых «рецептов» (12).
На веб-сайте проекта регулярно появлялись новые аминокислотные последовательности белков, а за каждую предсказанную структуру в соответствии с абсолютной величиной ее свободной энергии пользователю начислялись игровые баллы.
Видимо, ключевым элементом успеха проекта (рис.2) стало то, что его авторы не ограничились просто игрой, а создали целое сообщество игроков. Для каждого белка велись записи текущих рекордов, отмечались суммарные достижения конкретного участника за все время игры. Более того, были созданы средства для общения игроков, обмена удачными находками и формирования команд, совместно работающих над новыми задачами. Примечательно, что в числе авторов первой
опубликованной работы, посвященной проекту, значится некто под именем Foldit players (игроки «Foldit»; если точнее — указано, что их более 57 тыс.) [2]. В этой статье сопоставлялись результаты автоматического предсказания пространственной структуры белка с помощью алгоритма «Rosetta» и прогнозы, сделанные коллективом игроков. Эталоном служили соответствующие структуры, определенные кристаллографическими методами. Во многих случаях результаты, полученные участниками проекта, оказались существенно лучше, чем чисто автоматические (а качество оценивается близостью структуры к нативной). Игроки проявляли себя с наиболее сильной стороны в ситуациях, когда уже есть автоматически пред-
-100 -
среднеквадратичное отклонение от нативной структуры
0.5 10 1.5 время, ч
среднеквадратичное отклонение от нативной структуры
IJS -rfjV
Ф №
$$ — ¿ts
а
в
г
б
д
Рис.2. Примеры задач, в решении которых игроки <^о1сИЪ> превзошли компьютер [2]. Решение задачи №986875, которая была посвящена предсказанию пространственной структуры белка 2кро (а—в), и задачи №986698 о белке 2кку (г, д). Кон-формации, полученные игроками, показаны зелеными точками, а программой «^ейа» — желтыми. По горизонтальной оси отложено полноатомное среднеквадратичное отклонение предсказанной структуры от нативной (опубликованной), по вертикальной — ее энергия (а, г). Черной точкой отмечено начальное приближение (4.28 А от нативной конформации). Наилучшие результаты <^о1С1Ъ> отличаются от нативной структуры на 1.4 А, а в случае программы «1^о$еШ» — на 2 А. Голубые линии соответствуют траектории одного из игроков (а). Наложение предсказания <^о1С1Ъ> (изображено зеленым) на структуру белка 2кро, экспериментально определенную с помощью ЯМР (синим). Стартовое приближение, в котором концевой тяж переставлен с соседним (и образует неправильную конформацию), показано красным. 8% игроков смогли верно расположить эти тяжи (б). Траектория самого успешного в задаче №986875 игрока показывает, как он проходил области высоких энергий в поисках оптимальной структуры белка 2кро (снизу изображены переходы 1—6). По вертикали отложена энергия предсказанной конформации, по горизонтали — истекшее время (в). Сравнение структур, полученных игроками и программой «^еИа» для белка 2кку: игрокам удалось выбрать из множества стартовых конформаций (отмечены черным) ближайшую к нативной структуре и улучшить ее (г). Наложение предсказания <^о1С1Ъ> (изображено зеленым) на нативную структуру белка 2кку (синим). Стартовое приближение показано желтым (д).
сказанная конформация белка с правильно определенными основными элементами его вторичной структуры и их взаимным расположением и требуется провести доработку, например, убрать торчащие гидрофобные остатки или уточнить ориентацию элементов вторичной структуры. Более тонкая работа по уточнению положений боковых аминокислотных остатков производится компьютером, причем участники неоднократно делают это в процессе игры. Таким образом, успех работы критическим образом зависит от того, удается ли автоматической процедуре угадать общие черты структуры и оказаться в достаточно близкой окрестности оптимальной конформации. К счастью, часто современные алгоритмы способны это сделать. Интересно, что в командах игроков само собой происходит разделение ролей: каждый делает то, что у него лучше получается, — от анализа структуры «с высоты птичьего полета» до уточнения мелких деталей.
Успехи игроков
Предсказание пространственной структуры белка — область, где очевидны критерии качества (заметим, что не все биоинформатические задачи таковы), а значит, возможно и соревнование. Раз в два года такой конкурс действительно проводится, он называется CASP (Critical Assessment of protein Structure Prediction). Для него выбирают белки, структуры которых уже определены, но еще не опубликованы. Участники делают свои пре
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.