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

Если я ещё не надоел, то в качестве тренировки мозгов предлагаю подумать над задачей. Вообще, я искренне верю, что любые, даже столь маленькие шаги вперёд, как, к примеру, ускорение работы по поиску оптимальных праймеров, нахождение новых мутаций, которые были сделаны в том числе благодаря RU.SOF, способствует тому, что человек живёт чуточку дольше и проживает жизнь чуточку здоровее и моложе (о противодействующих факторах я умолчу).

Краткое традиционное отступление:
"Новые" болезнетворные организмы появляется не так часто, как о них трубит пресса. Зачастую это либо мутация, либо перенос у вполне себе обычных вирусов, либо всплывает что-то очень хорошо забытое. Ряд вирусов ввиду очень "неразборчивой" полимеразы с высокой степенью ошибочности вообще при воспроизводстве могут изменяться на 10-20% (представляете, сколько нежизнеспособных копий при этом воспроизводится!), при этом не называясь новым видом. Но не будем лезть в глубины систематики.
При разработке практических наборов диагностики заболеваний есть несколько методик. Одна из них, часто называемая "мартышкин труд", - наиболее затратная по усилиям и иногда по материалам, зато запускать её в процесс можно на самых ранних стадиях, когда уже начал оформляться сиквенс ДНК возбудителя.

Итак, задача:
по существующему набору последовательностей ДНК (геном болезнетворного организма, для краткости - геном) создать массив уникальных праймеров (это строки длиной 8 - 30 символов, состоящие из литер A, G, T или C. Вырожденность пока опустим. Длину праймера сразу обозначим как L). Сам геном представляет из себя файл/файлы со строками, состоящими из тех же литер и дополнительно литеры N (неизвестно, пропуск, ошибка прочтения). Для задачи его можно представлять входным массивов строк со словарём из 5 литер.

То есть, фактически, необходимо найти ВСЕ варианты строк заданной длины, которые могут быть найдены во входном массиве строк. При этом N не должно входить ни в одну строку.

Сразу в голову приходит 2 алгоритма:

Перебор
Цикл (возможно, рекурсивный), в котором генерируются все варианты (это 4 в степени L), а затем проводится поиск сгенерированной подстроки в геноме. Нашли - заносим в результат, переходим к следующему варианту, не нашли во всём геноме - просто идём дальше.

Плюсы:

• Всегда знаем, "где находимся" - это иногда полезно в комбинированных исследованиях
  Нет необходимости в сортировке (спорно: учитывая, что алфавит содержит лишь 4 литеры, сортировка даже больших массивов очень быстра, главное - не использовать стандартные алгоритмы)
• Великолепная масштабируемость по потокам: задача легко раскидывается на любое количество ядер в случае большого объёма данных

Минусы:

• очень медленно. Каждый вариант ищется во всём геноме. Методы поиска для малобуквенных алфавитов быстрее, чем стандартные, но всё же для больших геномов и они "тормозят".

Словарь
Создаём словарь вида TDictionary<string, integer>, вводим рамку считывания (строка длиной L, её первое значение = L первых символов генома, затем она сдвигается на один символ и так далее), каждый раз заносим её в словарь. Если рамка уникальна - заводим новый ключ, если нет - увеличиваем счётчик integer. Если в рамке повстречалась литера N, перескакиваем по геному на L символов, чтобы её избежать.

Плюсы:

• Высокая скорость (в том числе и за счёт того, что мы быстро обходим сплошные N-области генома, а они часты, особенно у недавно отсеквенированных организмов).
• Мы получаем ещё и частоту встречаемости праймеров в геноме

Минусы:

• Нужно делать сортировку (слабый минус)
• Очень сложно делить на несколько потоков, поскольку чтение из строк генома легко разруливается по потокам, а вот запись в словарь, увы, приходится разделять, поэтому более чем 2 потока бессмысленны. Да и 2 потока, если честно, не сильно быстрее, чем 1.

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

В качестве примера: на входе "зеленый штамм" вируса иммунодефицита человека в формате FASTA (член массива начинается со следующей строки после знака ">"), на выходе - набор праймеров L=11

Для тех, кому неинтересна биологическая подоплёка :) :

На входе - массив строк с алфавитом от 4 до 16 литер (в качестве примера можно брать 4 литеры, как самый распространённый вариант - в примере на загрузку именно он и есть, но, чтобы алгоритм можно было растянуть на все варианты, стоит помнить, что эти варианты есть) и лишней литерой N. Найти все уникальные строки длиной L (задана конкретно, от 8 до 30), входящие в исходный массив строк и включающие только алфавитные литеры (т.е. без N).

Хороший вариант: быстрый, легко масштабируемый на потоки алгоритм.

Идеальный вариант: то же, что и хороший, но которому можно задать маску, к примеру, все праймеры вида A??G??TC?????? (это именно тот плюс, что есть у первого варианта).