В документе, представленном в прошлом месяце на 39-й Международной конференции по очень большим базам данных (VLDB2013) в Рива-дель-Гарда, Италия, Сифэн Ян, кафедра компьютерных наук Венкатеша Нараянамурти в Калифорнийском университете в Санта-Барбаре, объясняет, как он использовал SDSC. Вычислительный кластер Trestles помогает разработать новый алгоритм под названием MSP (минимальное разбиение подстроки), который помогает собирать геномы с максимальной эффективностью. MSP — важная часть конвейера или группы программного обеспечения, которое собирает целые геномы, при этом каждая часть программного обеспечения выполняет свою часть работы.
Ян и его коллеги смогли оптимизировать один из двух шагов, чтобы использовать всего 10 гигабайт памяти без замедления времени выполнения.«Высококачественное секвенирование генома является основой многих критических биологических и медицинских проблем», — сказал Ян. «С появлением технологий массового параллельного секвенирования ДНК, как управлять и обрабатывать большие данные о последовательностях стало важной проблемой. Экспериментальные результаты показали, что MSP может не только успешно выполнять задачи с очень большими наборами данных в небольшом объеме памяти, но и достичь более высокой производительности, чем существующие современные алгоритмы ".По словам Яна, его экспериментальные результаты демонстрируют, что повышение эффективности MSP может вскоре сделать возможным сборку больших геномов, используя меньшие, менее дорогие товарные кластеры, вместо того, чтобы требовать дорогостоящих и высокопроизводительных ресурсов.
Знание всего генома различных видов лежит в основе биологических и медицинских исследований, таких как понимание путей эволюции или определение причины болезней. Однако существующие методы секвенирования производят огромные количества — миллиарды для более высокого организма, такого как человек, — перекрывающихся коротких последовательностей, случайно выбранных из генома.
Основная задача в исследовании генома — собрать эти короткие считывания, длина которых варьируется от десяти до нескольких сотен оснований, обратно во весь геном, что требует огромного объема памяти. Это было бы похоже на склеивание энциклопедии из стога сена слов и фрагментов предложений.Используя Trestles, Ян и его коллеги продемонстрировали, что MSP сокращает один из требуемых шагов, так что он использует значительно меньше памяти, чем широко используемые алгоритмы, устраняя одно из узких мест при обработке целых геномов. Алгоритмы, такие как Velvet и SOAPdenovo, борются за компьютерную подготовку виртуального каркаса, на котором можно собрать последовательность в полные геномы.
MSP, метод дисковых разделов, упрощает создание таких каркасов, известных как граф Де Брёйна. Геном размером с млекопитающее, обработанный с использованием других алгоритмов, потреблял бы сотни гигабайт памяти, в то время как MSP позволяет исследователям завершить ключевой этап до десяти гигабайт памяти без замедления времени выполнения.
Ян и его коллеги работают над вторым этапом, который также потребляет значительный объем памяти, и до сих пор сократили использование памяти на две трети с целью дальнейшего сокращения в будущем. В число дополнительных исследователей входят Ян Ли, Пегах Камуси, Фангцю Хан, Шэнци Ян и Субхаш Сури, все из Калифорнийского университета в Санта-Барбаре.Статья: http://dl.acm.org/citation.cfm?id=2448951