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

Question

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

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

(редактирование для осветления)

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

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

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

Надеюсь, это разъяснит, что необходимо и почему текущие решения не освещены.

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Удачи вам!

-Adam

Answer 4

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

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

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