On Disk Substring Index

Question

Ich habe eine Datei (Fasta-Datei, um genau zu sein), die ich indizieren möchte, so dass ich schnell einen Teilstring innerhalb der Datei finden und dann den Speicherort innerhalb der ursprünglichen Fasta-Datei finden kann.

Dies wäre in vielen Fällen einfach zu tun, mit einem Trie oder Teilstring-Array, leider sind die Zeichenfolgen, die ich indizieren muss 800 + MBs, was bedeutet, dass sie in Speicher in inakzeptabel machen, so suche ich nach einem vernünftigen Möglichkeit, diesen Index auf dem Datenträger mit minimaler Speicherauslastung zu erstellen.

(edit Klärungs)

Ich bin nur in den Headern von Proteinen interessiert, so dass für die größte Datenbank mich interessiert, das etwa 800 MBs von Text ist.

Ich möchte in der Lage sein, eine genaue Teilzeichenfolge innerhalb von O (N) Zeit basierend auf der Eingabezeichenfolge zu finden. Dies muss auf 32-Bit-Rechnern nutzbar sein, da es an zufällige Personen verschickt wird, von denen nicht erwartet wird, dass sie 64-Bit-Maschinen haben.

Ich möchte in der Lage sein, gegen jeden Wortwechsel innerhalb einer Zeile, bis zum Ende der Zeile (obwohl Zeilen mehrere MBs lang sein können) zu indizieren.

Dies verdeutlicht hoffentlich, was benötigt wird und warum die aktuellen Lösungen nicht aufleuchten.

Ich sollte auch hinzufügen, dass dies innerhalb von Java getan werden muss, und muss auf Client-Computern auf verschiedenen Betriebssystemen erfolgen, so dass ich keine OS-spezifische Lösung verwenden kann, und es muss eine programmatische Lösung sein.

Answer 1

Ich habe mit ein paar Kollegen gesprochen und sie benutzen einfach VIM/Grep, um zu suchen, wenn sie müssen. Die meiste Zeit würde ich nicht erwarten, dass jemand nach einem Teilstring wie diesem sucht.

Aber ich sehe nicht, warum MS Desktop-Suche oder Spotlight oder Google Äquivalent kann Ihnen hier nicht helfen.

Meine Empfehlung ist das Aufteilen der Datei - durch Gen oder Spezies, hoffentlich sind die Eingabefolgen nicht verschachtelt.

Answer 2

In einigen Sprachen Programmierern haben Zugriff auf "direkten Byte-Arrays" oder "memory maps", die vom Betriebssystem bereitgestellt werden. In Java haben wir . Dies ermöglicht es, mit den Daten so zu arbeiten, als wäre es ein Byte-Array im Speicher, während es sich tatsächlich auf dem Datenträger befindet. Die Größe der Datei, mit der man arbeiten kann, ist nur durch die virtuellen Speicherfähigkeiten des Betriebssystems begrenzt und beträgt typischerweise ~ < 4GB für 32-Bit-Computer. 64-Bit? In der Theorie 16 Exabytes (17,2 Milliarden GBs), aber ich denke, dass moderne CPUs auf einen 40-Bit (1 TB) oder 48-Bit (128 TB) Adressraum beschränkt sind.

Damit können Sie leicht mit der einen großen Datei arbeiten.

Answer 3

Die FASTA file format ist sehr spärlich. Das erste, was ich tun würde, ist ein kompaktes Binärformat zu erzeugen, und Index , dass - es sollte vielleicht 20-30% der Größe Ihrer aktuellen Datei, und der Prozess für die Codierung/Decodierung der Daten sollte schnell genug sein (sogar mit 4GB), dass es kein Problem sein wird.

An diesem Punkt sollte Ihre Datei in den Speicher passen, sogar auf einem 32-Bit-Rechner. Lassen Sie das OS es pagen, oder machen Sie eine Ramdisk, wenn Sie sicher sein wollen, dass alles im Speicher ist.

Denken Sie daran, dass der Speicher nur etwa 30 US-Dollar pro GB beträgt (und billiger wird). Wenn Sie also ein 64-Bit-Betriebssystem haben, können Sie sogar mit der gesamten Datei arbeiten, ohne sie in ein kompakteres Format zu konvertieren.

Viel Glück!

-Adam

Answer 4

Ich kann mir nicht vorstellen, dass das ursprüngliche Plakat noch dieses Problem hat, aber jeder FASTA Datei Indizierung und Teilfolge Extraktion benötigen, sollten fastahack check out: http://github.com/ekg/fastahack

Es verwendet eine Indexdatei zu zählen Zeilenumbrüche und Sequenz starten Offsets. Sobald der Index generiert ist, können Sie Subsequenzen schnell extrahieren. Die Extraktion wird von fseek64 gesteuert.

Es funktioniert sehr, sehr gut in dem Fall, dass Ihre Sequenzen so lang wie die des Posters sind. Wenn Sie jedoch viele Tausende oder Millionen von Sequenzen in Ihrer FASTA-Datei haben (wie bei den Ausgaben von Short-Read Sequencing oder einigen Baugruppen), sollten Sie eine andere Lösung, z. B. eine Festplatte, verwenden Schlüssel-Wert-Speicher.