Индекс подстроки на диске

Question

У меня есть файл (точнее, файл fasta), который я хотел бы проиндексировать, чтобы я мог быстро найти любую подстроку в файле и затем найти местоположение в исходном файле fasta.

Это было бы легко сделать во многих случаях, используя массив Trie или подстроку, к сожалению, строки, которые мне нужно индексировать, имеют размер 800+ МБ, что означает, что выполнение их в памяти недопустимо, поэтому я ищу разумный способ создать этот индекс на диске с минимальным использованием памяти.

(редактировать для уточнения)

Меня интересуют только заголовки белков, поэтому для самой большой базы данных, которая меня интересует, это около 800 МБ текста.

Я бы хотел найти точную подстроку в течение O (N) времени на основе входной строки. Это должно быть применимо на 32-битных машинах, так как оно будет отправлено случайным людям, которые не должны иметь 64-битные машины.

Я хочу иметь возможность индексировать любой разрыв слова в строке до конца строки (хотя длина строки может составлять несколько МБ).

Надеемся, что это проясняет, что нужно и почему нынешние решения не освещают.

Я должен также добавить, что это должно быть сделано изнутри java и должно выполняться на клиентских компьютерах в различных операционных системах, поэтому я не могу использовать какое-либо решение для конкретной ОС, и это должно быть программным решением.

Answer 1

На некоторых языках программисты имеют доступ к "прямым байтовым массивам" или " карт памяти " , которые предоставляются ОС. В java у нас есть java.nio.MappedByteBuffer . Это позволяет работать с данными, как если бы они были байтовым массивом в памяти, тогда как на самом деле они находятся на диске. Размер файла, с которым можно работать, ограничен только возможностями виртуальной памяти ОС и обычно составляет ~ <4 ГБ для 32-разрядных компьютеров. 64-битный? Теоретически 16 эксабайт (17,2 млрд. ГБ), но я думаю, что современные процессоры ограничены 40-битным (1 ТБ) или 48-битным (128 ТБ) адресным пространством. </p>

Это позволит вам легко работать с одним большим файлом.

Answer 2

Формат файла FASTA очень разреженный. Первое, что я хотел бы сделать, это сгенерировать компактный двоичный формат и индексировать , что - это должно быть, возможно, 20-30% размера вашего текущего файла, и процесс кодирования / декодирования данных должен быть быстрым достаточно (даже с 4 ГБ), чтобы это не было проблемой.

В этот момент ваш файл должен уместиться в памяти даже на 32-битной машине. Позвольте странице ОС это сделать или создайте виртуальный диск, если хотите быть уверенным, что он находится в памяти.

Имейте в виду, что объем памяти составляет всего около 30 долларов США (и удешевляется), поэтому, если у вас 64-разрядная ОС, вы можете даже обработать весь файл в памяти, не кодируя его в более компактный формат.

Удачи!

-Adam

Answer 3

Я не думаю, что оригинальный постер все еще имеет эту проблему, но любой, кому нужна индексация файла FASTA и извлечение подпоследовательности, должен проверить fastahack: http://github.com/ekg/fastahack

Он использует индексный файл для подсчета новых строк и смещений начала последовательности. После создания индекса вы можете быстро извлечь подпоследовательности; извлечение осуществляется с помощью fseek64.

Это будет работать очень и очень хорошо в том случае, если ваши последовательности такие же, как у постера. Однако, если в вашем файле FASTA имеется много тысяч или миллионов последовательностей (как в случае с выходными данными из кратко читаемого секвенирования или некоторых de novo сборок), вы можете использовать другое решение, например хранилище значений ключей на основе диска.

Answer 4

Я разговаривал с несколькими коллегами, и они просто используют VIM / Grep для поиска, когда это необходимо. Хотя в большинстве случаев я бы не ожидал, что кто-то будет искать такую ​​подстроку.

Но я не понимаю, почему поиск по MS Desktop или прожектор или эквивалент Google не могут помочь вам здесь.

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