Поиск в геномных данных ускорился благодаря новому алгоритму

В 2001 году проект «Геном человека» и Celera Genomics объявили, что после 10 лет работы и затрат около $400 млн они завершили черновой вариант последовательности человеческого генома. Сегодня секвенирование человеческого генома может выполнить один исследователь за пару недель менее чем за $10 000.

С 2002 года скорость секвенирования геномов удваивается примерно каждые четыре месяца, тогда как вычислительная мощность удваивается только каждые 18 месяцев. Без новых аналитических инструментов способность биологов генерировать геномные данные скоро превзойдет их способность извлекать из них пользу.

В новом выпуске Nature Biotechnology исследователи из MIT и Гарварда описывают новый алгоритм, который резко сокращает время поиска конкретной генной последовательности в базе данных геномов. Более того, чем больше геномов он ищет, тем больше ускорение, поэтому его преимущества будут только нарастать по мере генерации данных.

Использование избыточности

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

Схема сжатия исследователей использует тот факт, что эволюция скупа на удачные конструкции. Геномы близкородственных видов сильно перекрываются, и есть некоторое перекрытие даже у далеких видов: поэтому эксперименты на дрожжевых клетках могут рассказать нам что-то о реакциях человека на лекарства.

Бергер, её бывший аспирант Майкл Бейм (PhD '09), а ныне приглашенный исследователь на математическом факультете MIT и постдок в системной биологии Гарвардской медицинской школы, и её нынешний аспирант По-Ру Ло разработали способ математического представления геномов разных видов (или разных особей внутри вида), при котором перекрывающиеся данные хранятся только один раз. Поиск по множеству геномов может таким образом концентрироваться на их различиях, экономя время.

«Если я хочу выполнить вычисление на моем геноме, это занимает определенное время, — объясняет Бейм. — Если я затем захочу выполнить то же вычисление на вашем геноме, тот факт, что мы так похожи, означает, что я уже проделал большую часть работы».

Сравнение с BLAST

В экспериментах с базой данных из 36 дрожжевых геномов исследователи сравнили свой алгоритм с алгоритмом BLAST (Basic Local Alignment Search Tool), одним из наиболее часто используемых в биологии алгоритмов поиска в геномах. При поиске определенной генетической последовательности всего в 10 дрожжевых геномах новый алгоритм был в два раза быстрее BLAST; но при поиске по всем 36 геномам он был в четыре раза быстрее. Это расхождение будет только увеличиваться по мере роста геномных баз данных, объясняет Бергер.

Области применения

Новый алгоритм был бы полезен в любых приложениях, где центральный вопрос, как выразился Бейм: «У меня есть последовательность; на что она похожа?». Примеры:

• Идентификация микробов: Помощь клиницистам в определении причин инфекций или биологам в характеристике «микробиомов» — сообществ микробов в тканях животных или конкретных микро-средах. Вариации человеческого микробиома связывают с рядом медицинских состояний.
• Анализ почвы: Характеристика микробов в особенно плодородной или бесплодной почве.
• Криминалистика: Определение географического происхождения вещественных доказательств по их микробным сигнатурам.

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