Intel corporate blog
1 July 2010

Суперкомпьютеры на страже генетики

   В преддверии нового поста программы "5 недель с компанией Intel", предлагаю ознакомиться с интересным текстом, в котором рассказывается о применений высокопроизводительных систем (HPC) на примере нескольких российских разработок.

image

   В мае компания Intel проводила конкурс 32 Core Testing Plan, предлагающий научному сообществу протестировать свои приложения на многоядерной вычислительной системе — среди пяти победителей из России аж три команды. Ниже пара слов о сложной и красивой математике, стоящей за работами финалистов.

   Антон Панкратов работает в Институте математических проблем биологии, который занимается целым рядом задач (на главной странице института есть полный список): начиная от исследования первичных структур биополимеров и моделирования динамики биомолекулярных систем, заканчивая нейросетевыми моделями и проблемами биоразнообразия.

image

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

image   Генетика для чайников: ДНК это очень длинный полимер, состоящий из большого количества строительных кирпичиков — нуклеотидов. Нуклеотиды в своей основе имеют четыре повторяющихся нуклеиновых основания: аденин, тимин, гуанин и цитозин, сокращенно — A, T, G, и C. Серьезные генетические исследования минуют химические процессы и работают напрямую с этими четырьмя буквами, которыми зашифрованы практически все живые организмы на Земле: ATCGATTG, примерно так выглядит продолжающийся код ДНК. Продолжающийся и продолжающийся, потому что эти последовательности очень длинны: самая длинная человеческая хромосома, номер один, длиной около 220 миллионов пар нуклеотидов.

   Одна из крупных проблем современной вычислительной генетики — распознавание образов, то есть нахождение повторяющихся частей ДНК. Одно дело просто записать весь геном человека, совершенно другое — найти в нем повторяющиеся или похожие части и попытаться установить между ними связи, соотношения. Этим и занимается команда Антона, продолжая двадцатилетний проект института ИМПБ, начатый наставниками Антона и опирающийся на работы великого русского математика Пафнутия Чебышёва. «Мы называем наш метод NASCA, Numeric Analytical Spectral Comparing Approach: метод аппроксимации спектрального анализа», рассказывает Антон, пока мы прогуливаемся по залитому солнцем второму учебному корпусу МГУ на Воробьевых горах, alma mater Антона.

   «Пользуясь формулами ортогональных многочленов Чебышёва, сделавшего большой вклад в теорию аппроксимации, мы можем обрабатывать очень большие последовательности, чего не могут общепринятые методы динамического программирования, устанавливающие прямое соответствие буквы с буквой». Это и есть «гомология», то есть похожесть, но не точное соответствие — команда Антона ищет подобные, но не точные повторы внутри кода ДНК. «Мы абстрагировались от буквенного текста и перешли к его статистическим профилям: мы больше не видим отдельных букв A, T, G и C, но видим некую статистику вдоль текста, которую можем обрабатывать методами аппроксимации спектрального анализа».

image
   Фрагмент матрицы, рассматривающей последовательность из полутора миллионов пар нуклеотидов; каждый цветной пиксель матрицы это не единичный повтор, а повтор 500 нуклеиновых оснований. Схожие отрезки отмечены красным цветом (красная диагональ это, разумеется, повторы матрицы, замыкающиеся сами на себя), обратные последовательности показаны зеленым цветом.

   Эта карта — готовый научный инструмент для исследования генома. Команда Антона уже нашла повтор, который очень трудно обнаружить при помощи общеизвестных методов: «Руслан отправил нашу находку в базу данных Genetic Information Research Institute, и мы надеемся, что наш метод тоже займет свое место в арсенале современного генетика».

   «Мы узнали о конкурсе по линии лаборатории Intel в МГУ. Для нас интересны многоядерные архитектуры, поскольку наш метод очень хорошо распараллеливается на них благодаря методу вычисления коэффициентов разложения, который мы разработали. Текущая реализация нашей работы использует популярные пакеты OpenMP и Intel IPP и на мультиядерных архитектурах ускоряется практически линейно. На тестовой 32-ядерной системе Intel мы добились 27-кратного ускорения алгоритмической части нашей программы».

image

   «Уже сейчас видно, что пока мы тестировали наши алгоритмы на удаленной 32-ядерной машине, предоставленной Intel, мы довольно многому научились. Параллельное программирование заставляет думать и стремиться к красивым решениям».

   Екатерина Жмудь из Новосибирского Государственного Университета тоже использует многоядерные системы для чрезвычайно красивого кода. «Наш проект связан с теорией кодирования и занимается алгоритмами вычисления групп автоморфизмов Q-значных кодов. Звучит не очень понятно, но вообще группы автоморфизмов широко используются в современной криптографии, которая сейчас становится все более и более важной частью технического мира. Моя часть работы на этом проекте касается обнаружения симметричных групп комбинаторных объектов, необязательно кодов. В дальнейшем мы собираемся сделать специальный инструмент, который мог бы использоваться учеными-криптографами».

image
Автор фотографии: Майя Шелковникова

   Как и команда Антона, Екатерина использует матрицы для проверки кода; отдельные строки матрицы или части строк могут просматриваться независимо, так что алгоритм может быть чрезвычайно параллельным. «Мы используем vTune и Thread Checker для анализа параллелизации нашего кода», добавляет Екатерина.

   Антон Панкратов и его команда раздумывают об использовании интеловских инструментов тестирования и оптимизации программ, но «пока что мы не пользуемся какими-то специализированными средствами отладки наших программ — просто очень аккуратно их пишем. Наши наблюдения подтверждают расхожее мнение, что память является узким местом в высокопроизводительных вычислительных системах, так что мы используем индексирование, сжатие информации, чем снимаем нагрузку на память и что в свою очередь положительно сказывается на распараллеливании. Помощь Intel была важна и в организационном смысле — в 2006 году я съездил на конференцию по параллельным вычислениям и там сориентировался в существующих инструментах и средах параллельного программирования».

   Алексей Николаев, директор образовательных программ Intel в России, резюмирует тему: «И конкурс, и деятельность лаборатории показывает, что мы находимся на переднем крае тенденций индустрии, тенденций науки и вопросов образования; их совокупность позволяет нам открывать и новые методические аспекты, и давать новые знания, и определять наиболее эффективный путь движения образования».

* * *


image Текст взят с проекта Intel Galaxy.

+ А во второй половине дня в рамках программы "5 недель с компанией Intel" будет размещен еще один материал, касающийся темы суперкопьютеров (HPC), так что уже можно начинать готовить каверзные вопросы.

Продолжение следует.

+51
14.1k 10
Support the author
Comments 81
Top of the day