0

インデックスを作成したいファイル (具体的には fasta ファイル) があるので、ファイル内の部分文字列をすばやく見つけて、元の fasta ファイル内の場所を見つけることができます。

これは多くの場合、Trie または部分文字列配列を使用して簡単に実行できますが、残念ながら、インデックスを作成する必要がある文字列は 800 MB 以上であるため、メモリ内でそれらを実行することは受け入れられないため、これを作成する合理的な方法を探しています。メモリ使用量を最小限に抑えて、ディスク上にインデックスを作成します。

(明確にするために編集)

私が関心があるのはタンパク質のヘッダーだけなので、関心のある最大のデータベースの場合、これは約 800 MB のテキストになります。

入力文字列に基づいて、O(N) 時間以内に正確な部分文字列を見つけられるようにしたいと考えています。これは 32 ビット マシンで使用できる必要があります。これは、64 ビット マシンを使用することが想定されていないランダムな人々に出荷されるためです。

行内の任意の単語区切りに対して、行の最後までインデックスを作成できるようにしたいと考えています (ただし、行の長さは数 MB になる場合があります)。

これにより、何が必要であり、現在の解決策が明らかにされていない理由が明確になることを願っています。

また、これはJava内から実行する必要があり、さまざまなオペレーティングシステムのクライアントコンピューターで実行する必要があるため、OS固有のソリューションを使用できず、プログラムソリューションでなければならないことも付け加えておく必要があります.

4

4 に答える 4

1

一部の言語では、プログラマは、OS によって提供される「ダイレクト バイト配列」またはメモリ マップ」にアクセスできます。Java にはjava.nio.MappedByteBufferがあります。これにより、実際にはディスク上にある場合でも、メモリ内のバイト配列であるかのようにデータを操作できます。操作できるファイルのサイズは、OS の仮想メモリ機能によってのみ制限され、通常、32 ビット コンピューターの場合は ~<4GB です。64ビット?理論上は 16 エクサバイト (172 億 GB) ですが、最新の CPU は 40 ビット (1 TB) または 48 ビット (128 TB) のアドレス空間に制限されていると思います。

これにより、1 つの大きなファイルを簡単に操作できます。

于 2008-09-10T07:03:43.627 に答える
1

FASTA ファイル形式は非常にまばらです。私が最初に行うことは、コンパクトなバイナリ形式を生成し、それをインデックス化することです。現在のファイルのサイズの 20 ~ 30% である必要があり、データのコーディング/デコードのプロセスは十分に高速である必要があります (4GB の場合でも)。問題にならないということです。

その時点で、ファイルは 32 ビット マシンでもメモリ内に収まるはずです。OSにページングさせるか、すべてがメモリ内にあることを確認したい場合はRAMディスクを作成します。

メモリは 1 GB あたり約 30 ドル (さらに安くなりつつあります) であるため、64 ビット OS を使用している場合は、よりコンパクトな形式にエンコードすることなく、メモリ内の完全なファイルを処理することもできます。

幸運を!

-アダム

于 2008-09-13T13:25:57.317 に答える
0

私は数人の同僚と話をしましたが、彼らは必要なときにVIM/Grepを使用して検索します。しかし、ほとんどの場合、誰かがこのような部分文字列を検索することは期待していません。

しかし、MSデスクトップ検索、スポットライト、またはグーグルの同等のものがここであなたを助けることができない理由はわかりません。

私の推奨事項は、ファイルを遺伝子または種ごとに分割することです。入力シーケンスがインターリーブされていないことを願っています。

于 2008-09-10T00:02:25.823 に答える
0

元のポスターにまだこの問題があるとは思いませんが、FASTA ファイルのインデックス作成とサブシーケンスの抽出が必要な人は、fastahack をチェックしてください: http://github.com/ekg/fastahack

インデックス ファイルを使用して、改行とシーケンス開始オフセットをカウントします。インデックスが生成されると、サブシーケンスをすばやく抽出できます。抽出は fseek64 によって駆動されます。

シーケンスがポスターと同じくらい長い場合、非常にうまく機能します。ただし、FASTA ファイルに数千または数百万のシーケンスがある場合 (ショートリード シーケンスまたは一部のde novoアセンブリからの出力の場合のように)、ディスクにバックアップされたキーなどの別のソリューションを使用する必要があります。バリューストア。

于 2010-05-07T17:16:44.740 に答える