Теоретический анализ расширяет возможности ускоренного поиска в биологии и других областях
Генетические секвенаторы более десяти лет развиваются быстрее, чем компьютеры для анализа их данных. Поиск последовательностей ДНК в геномных базах данных уже занимает часы, и проблема усугубляется.
Группа Бонни Бергер из Лаборатории компьютерных наук и искусственного интеллекта MIT (CSAIL) исследует методы "сжатия" биологических и химических данных для упрощения анализа.
В новом выпуске журнала Cell Systems Бергер и коллеги представили теоретический анализ, объясняющий успех их методов сжатия. Они выявили свойства наборов данных, делающие их пригодными для сжатия, и предложили алгоритм для проверки этих свойств. Анализ показал, что несколько существующих баз данных химических соединений и биологических молекул обладают такими свойствами.
На основе измерений этих свойств исследователи могут рассчитать повышение эффективности поиска. Для анализируемых наборов данных эффективность масштабируется сублинейно: чем больше набор, тем эффективнее должен быть поиск.
Бонни Бергер: "Эта работа предоставляет основу для применения алгоритмов сжатия к крупномасштабным биологическим данным. У нас также есть доказательства того, насколько мы можем повысить эффективность".
Ключ к сжатию — эволюционная "скупость". В геномах родственных (и даже отдалённо родственных) организмов много избыточности. Из всех возможных последовательностей четырёх букв ДНК (A, T, C, G) в реальных организмах представлено лишь очень небольшое подмножество. Более того, эти реальные геномы распределены не случайно, а образуют непрерывные паттерны, отражающие медленную скорость расхождения видов.
Принцип сжатия и поиска
Алгоритмы сжатия группы Бергер кластеризуют сходные геномные последовательности (отличающиеся на несколько букв), выбирая одну последовательность как представителя кластера. Поиск концентрируется только на наиболее вероятных кластерах; большая часть данных не проверяется.
Если представить данные как непрерывный путь в пространстве возможностей, то кластеры — это сферы, наложенные на данные. Точки внутри одной сферы тесно связаны.
Исследователи показали, что наборы данных пригодны для их методов сжатого поиска, если соответствуют двум критериям:
- Метрическая энтропия: данные занимают лишь малую часть большего пространства возможностей.
- Низкая фрактальная размерность: плотность точек данных не сильно меняется при движении по набору. Если поиск требует изучения трёх сфер вместо одной, время увеличится лишь втрое, а не в 10 или 100 раз.
В работе проанализированы три набора данных: два описывают белки (по последовательностям аминокислот и по форме), третий — органические молекулы. В отдельной статье (на рассмотрении) тот же анализ применён к сегментам ДНК длиной от 32 до 63 букв.
Масштабирование и применимость
Эффективность алгоритма поиска масштабируется не с количеством точек данных, а с метрической энтропией набора — формальной мерой непрерывности данных и их разреженности относительно пространства возможностей.
Поскольку эволюция консервативна, метрическая энтропия геномных данных, вероятно, будет расти по мере секвенирования новых геномов. Новые данные будут заполнять пробелы в существующем паттерне, а не создавать новые ветви, увеличивая метрическую энтропию.
Многие другие крупные наборы данных могут быть столь же "консервативными". Например, поведение пользователей в сети, вероятно, ограничено биологией и культурной историей. Таким образом, методы сжатия MIT могут найти применение в широком спектре областей за пределами биологии.