accelerate 2012

Обработка строк с SSE 4.2 STTNI на практике

В рамках задачи Accelerate 2012 необходимо было найти максимизированные общие подстроки reference строки и input строк длиннее, чем некоторое minLength. Размеры строк ограничены по условиям конкурса 4 Gb и загрузка их в память и их парсинг съедает действительно много времени. Рекомендация использовать SSE 4.2 в обработке строк подтолкнула нас к её изучению.

Практическое введение в строковые операции SSE4.2 (STTNI)

В рамках конкурса Accelerate 2012 нам всем пришлось хорошенько поработать со строками.
Сначала от участников, а затем и от организаторов прозвучала идея, что использование набора инструкций SSE4.2 может придать значительное ускорение.

Скажу честно, мы с некоторым недоверием посмотрели на эту идею:
- Как мы применим SSE в нашем, еще не существующем, решении?
Но внесли её в список todo и, когда код уже начал обретать законченный вид, мы нашли места "приложения рычага".

Решение задачи конкурса Accelerate 2012 при помощи классического суффиксного дерева

Мы выбрали суффиксное дерево в качестве базовой структуры данных для решения задачи конкурса Accelerate 2012, потому что во многих источниках, начиная с английской википедии и заканчивая рефератами, непосредственно касающихся поиска совпадающих частей в геномах, рекомендуется именно суффиксное дерево.

Интересные подробности решения команды X!

Привет всем!

Я решила рассказать о том, что не вошло в наше отправленное решение на конкурс Accelereate 2012 из-за ограничения на размер.
Для начала рекомендую прочитать краткую версию, чтобы быть в контексте.

Итак:

Вариант решения задачи конкурса Accelerate 2012

Совсем недавно закончился конкурс Accelerate Your Code 2012. Решил поделиться своим решением. Конечно, вряд ли оно будет оптимальным, но некоторые идеи могут пригодиться…
Не буду приводить условие задачи, его можно найти на этой странице.
Идея моего решения, заключалась в постройке хэш-таблицы для ref-строки. Хэш строил по 6 символам, это связано с тем, что минимальная длина M равна 6.

Поиск одинаковых участков в нуклеотидных цепочках с помощью индексации

Данный пост написан в рамках конкурса Accelerate Your Code 2012.

Самый простой и самый не быстрый из методов поиска одинаковых участков в нуклеотидных цепочках - "наивный" перебор строк со смещением. Он хорошо подходит для коротких цепочек, так как не требует предварительной обработки и дополнительных объемов памяти.

Использование s-дерева для нахождения общих подстрок генетических последовательностей


В этой статье мы опишем разработанный нами метод решения задачи с конкурса параллельного программирования Accelerate 2012. В задаче требовалось найти наибольшие общие подстроки у двух генетических последовательностей (то есть строк, состоящих из символов A,G,T,C), превосходящие по длине наперёд заданную величину M ≥ 6.

Поваренная книга "Accelerate 2012", рецепт "фильтрация строк"

Решая задачу конкурса Accelerate 2012, наверное, мы все столкнулись с проблемой выполнения условия фильтрации строк. В статье мы расскажем как мы решили эту проблему.
В референсном коде за это отвечают строки:
//this match can be shifted on i and j

if(i + 1 < refSeq.length() && j + 1 < otherSeq.length() && L[i][j] <= L[i+1][j+1])

     continue;

//this match can be shifted on j

Модификация Алгоритма Рабина-Карпа для поиска общих подстрок

Вот и подошел к концу период отправки решений на конкурс Accelerate Your Code 2012 и мы наконец-то можем поделиться своими идеями, использованными в решении задачи и пригласить остальных участников к обсужднию.

Apache Hadoop и топ самых частотных слов

Всем привет!
Как и обещал, продолжу рассказ про MapReduce описанием реализации Apache Hadoop и примером реальной программы.

Задача, которую мы будем рассматривать - построение списка наиболее частоупотребимых слов в наборе документов (входными данными послужит список статей википедии).

Подписаться на accelerate 2012