問題タブ [dna-sequence]

長さ 100 文字の文字列の膨大なリスト (N = ~100 万) があり、それらの間の重複を見つけようとしています。たとえば、1 つの文字列は次のようになります。

すべての文字列と他のすべての文字列の最長重複値を含む N 行 N 列の行列を作成する必要があります。私の現在の方法は（疑似コード）です

すべての文字列を配列に読み込む

空の NxN 行列を作成する

各文字列をより高い配列インデックスを持つすべての文字列と比較します (比較のやり直しを避けるため)

最長オーバーラップを行列に書き込む

他にも多くのことが行われていますが、マトリックスを構築するためのより効率的な方法が本当に必要です。最も強力なコンピューティング クラスターを使用しても、この方法を手に入れるには数日かかります。

ご想像のとおり、これらは DNA フラグメントです。X は「ワイルドカード」 (しきい値の品質スコアを下回るプローブ) を示し、他のすべてのオプションは塩基 (A、C、T、または G) です。四分木アルゴリズムを書き込もうとしましたが、この方法はメモリを大量に消費します。

より効率的な方法についてご提案いただければ幸いです。私は C++ で作業していますが、疑似コード/アイデアまたは他の言語コードも非常に役立ちます。

編集:私の現在の方法を説明するいくつかのコードの抜粋。コンセプトに特に関係のないものはすべて削除されました

私はpythonが初めてで、複数のシーケンスを含むfastaファイルを読み取り、シーケンスの逆補完を含む新しいfastaファイルを作成する方法を見つけようとしています。ファイルは次のようになります。

>ホモサピエンス ACGTCAGTACGTACGTCATGACGTACGTACTGACTGACTGACTGACGTACTGACTGACTGACGTACGTACGTACGTACGTACGTACTG

>Canis_lupus CAGTCATGCATGCATGCAGTCATGACGTCAGTCAGTACTGCATGCATGCATGCATGCATGACTGCAGTACTGACGTACTGACGTCATGCATGCAGTCATG

>Pan_troglodytus CATGCATACTGCATGCATGCATCATGCATGCATGCATGCATGCATGCATCATGACTGCAGTCATGCAGTCAGTCATGCATGCATCAT

for および while ループの使用方法を学習しようとしているので、ソリューションにそれらのいずれかを組み込むことができれば、それが優先されます。

これまでのところ、次のように非常に洗練されていない方法でそれを行うことができました。

file1 = open('/path/to/file', 'r')

file1.close()

これはうまくいきましたが、その最後の部分を反復するより良い方法があることを私は知っています。より良い解決策はありますか？

各セルが 1 または 0 のいずれかを含むことができる 2 次元の m*n グリッドを考えてみましょう。このグリッドを移動することにより、トラバーサルが取得できる最大値を見つけます。値は、1 セルを斜めにトラバースすることで増加できます。グリッドの走査は、次の規則に従います。

1. 左上のセルから開始します。
2. 各セルで、走査は 1 グリッド下に移動するか、1 グリッド右に移動するか、斜めに移動します (1 グリッド下に移動し、1 グリッド右に移動します)。セルに 1 が含まれていて、トラバーサルが斜めに移動する場合、トラバーサル値は 1 増加します。
3. トラバーサルはグリッドから移動できません (右端で右に移動できない場合、下端で下に移動できない場合)。
4. 右下隅で終了します。

単純なアルゴリズムは、3*m*n 回のトラバーサルをすべて考慮し、最大値を選択します。誰かがより良い解決策を考え出すのを手伝ってくれますか? 同様の問題を解決するアルゴリズムはありますか?

これはインタビューの質問ではありません。Smith-Waterman アルゴリズムを最適化するために必要です。

例:

次のグリッドの最大値は 2 です。

これの最大値は 7 です。

DNA を操作する場合、配列のペア間の非同一部位の割合を含む三角形の p 距離行列が必要になることがよくあります。したがって：

1. AGGTT
2. アグクタ
3. アグタ

収量:

p 距離の計算は特定の R パッケージで利用できますが、文字 (C、T、A、G) ではなく数値コード (-1、0、1、2) を使用する必要があるとします。「my.matrix」から三角形の p 距離行列を生成するにはどうすればよいですか?

次の内容のプレーン テキスト ファイルがあります。

そして、これをIDコードに従ってアイテムに分割されたリストに読みたいと思います@M00964。

使ってみました

ただし、これにより ID シーケンスが削除されます@M00964。この ID シーケンスを保持する方法はありますか?

追加の質問として、リスト内の空白を維持する方法はありますか (/n 記号を使用するのではなく)。

私の全体的な目的は、この一連の項目を読み取り、たとえば最初の 2 つを取得して、元の書式設定をすべて維持したままテキスト ファイルに書き戻すことです。

ペアワイズ シーケンス アラインメントを行う際のシーケンス ファイルの一般的なサイズはどれくらいですか? 生物のゲノム全体を整列させることはできますか?