Max Home IndustryС усовершенствованием технологии секвенирования мы быстро приближаемся к биоинформатической перегрузке. Биологам нужны новые методы для хранения и доступа к огромной волне данных, которая вот-вот поразит объект, и одним из решений может быть использование сжатия.
В настоящее время секвенирование ДНК следует закону удвоения с удвоением скорости каждые несколько месяцев. Это намного превышает скорость роста вычислительной мощности. Количество геномных данных, по оценкам, увеличивается в десять раз каждый год, и в настоящее время секвенирование полного генома человека занимает около недели и стоит менее 10 000 долларов. Скоро полное секвенирование станет обычным делом.
Совершенно очевидно, что нам нужны новые способы обработки этой горы данных. Основная проблема заключается в поиске похожих целевых последовательностей в длинных последовательностях. Вы можете подумать, что поиск одной строки для целевой строки — это простой алгоритм, но критерий соответствия не точен. Могут быть несовпадающие точечные мутации и отсутствующие или дополнительные единицы, инделки (вставки / удаления). Это очень затрудняет сопоставление последовательностей, потому что вы ищете не точное совпадение, а хорошее совпадение. Ситуацию усугубляет размер области поиска и цели. Мы знаем точные решения проблемы, основанные на динамическом программировании, но в большинстве случаев практический анализ зависит от эвристики.
Проще говоря, анализ последовательности генома — сложная алгоритмическая проблема.
Ключ к поиску решения — заметить, что большинство геномных последовательностей очень мало отличаются. Вполне может быть, что количество хранимых полных последовательностей генома быстро увеличивается, но фактический объем новых данных очень мал. Другими словами, отдельная последовательность ДНК не особенно сжимаема, но набор последовательностей имеет так много общего, что избыточность может быть использована для их хранения в гораздо меньшем пространстве хранения.
По достигнутому сжатию видно, что добавление большего количества геномов добавляет очень мало информации.
Этот формат сжатых данных не только экономит место для хранения, но и может значительно ускорить анализ последовательности. Уловка состоит в том, чтобы использовать формат сжатия, который учитывает основную структуру ситуации, сохраняя детали замены, удаления, вставки и так далее. Если у вас есть сжатая последовательность форматов, ее можно искать за время, пропорциональное размеру файла, без необходимости распаковывать ее.
В недавней статье в Nature Biotechnology По-Ру Ло, Майкл Бэйм и Бонни Бергер (Массачусетский технологический институт и Гарвардская медицинская школа) продемонстрировали, что это можно заставить работать. Геномная база данных была сжата с использованием сходства последовательностей, а затем стандартные алгоритмы BLAST и BLAT были реализованы на сжатых данных без выполнения декомпрессии.
BLAST, например, работает путем поиска небольших маркерных «слов», взятых от цели в поисковой последовательности. Если слова найдены и у них одинаковый интервал как в целевой, так и в поисковой последовательности, то у нас есть потенциальное совпадение. Сжатая версия алгоритма сначала выполняет поиск любых частей поисковой последовательности, которые не были сжаты, с использованием низкого порога совпадения. Затем области, которые были идентифицированы как возможные области, эффективно распаковываются и ищутся с более высоким порогом. Полученный алгоритм оказался в четыре раза быстрее стандартного.
Есть проблемы с методом. В частности, по мере добавления в базу данных большего количества последовательностей сжатие становится менее эффективным, поскольку уменьшается избыточность.
Очевидно, что предстоит еще много работы. В частности, необходимо изучить методы сжатия, которые можно использовать, и то, как они взаимодействуют с поиском. Очевидно, что предварительное вычисление сходства между последовательностями как часть сжатия словарного стиля должно ускорить поиск.