問題タブ [dna-sequence]

私は長さ25のDNA配列を扱っています（以下の例を参照）。私は230,000のリストを持っており、ゲノム全体（toxoplasma gondii寄生虫）の各配列を探す必要があります。ゲノムの大きさはわかりませんが、23万配列よりはるかに長いです。

たとえば、（AGCCTCCCATGATTGAACAGATCAT）のように、25文字のシーケンスをそれぞれ探す必要があります。

ゲノムは連続した文字列としてフォーマットされます。つまり、（CATGGGAGGCTTGCGGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTTGCGGAGTGCGGAGCCTGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTT....）

どこに何回あるかは気にせず、見つけられるかどうかだけです。
これは簡単だと思います-

しかし、私はまた、任意の場所で間違っている（不一致）と定義されている厳密な一致を見つけて、その場所を1つの場所だけに記録し、その場所を順番に記録します。これをどのように行うのかわかりません。私が考えることができる唯一のことは、ワイルドカードを使用し、各位置でワイルドカードを使用して検索を実行することです。つまり、25回検索します。

例えば、

位置13での不一致との密接な一致。

スピードは3回しかないので大した問題ではありませんが、速ければいいのですが。

これを行うプログラムがあります-一致と部分一致を検索します-しかし、私はこれらのアプリケーションでは検出できないタイプの部分一致を探しています。

これはperlの同様の投稿ですが、シーケンスを比較しているだけで、連続した文字列を検索していません。

関連記事

可能であれば効率的な方法で、複数回出現する文字列の部分文字列を識別し、その部分文字列のすべての出現箇所をトークンに置き換える、ある種の「検索と置換」アルゴリズムを実行したいと思います。

たとえば、文字列「AbcAdAefgAbijkAblmnAbAb」が与えられた場合、「A」が繰り返されることに注意してください。そのため、パス 1 を「#1bc#1d#1efg#1bijk#1blmn#1b#1b」に減らします。ここで、#_ はインデックス付きパターンです (インデックス付きテーブルのパターン)、「#1b」が繰り返されることに注意してください。したがって、「#2c#1d#1efg#2ijk#2lmn#2#2」に縮小されます。文字列にこれ以上パターンが発生しないので、完了です。

「最長の共通サブシーケンス」と圧縮アルゴリズムに関する情報をいくつか見つけましたが、これを行うと思われるものは何もありません。これらは、2 つの文字列を比較するため、または何らかの種類のストレージに最適な結果を取得するためのものです。

一方、私の目的は、ゲノムを「文字」ではなく「言葉」に還元することです。つまり、gatcatcgatc の代わりに 2c1c2c を見たいのです。後で正規表現を実行して、「#42*#42」のようなものを見つけることができます。DNA に括弧が繰り返されるのを見るのはクールだろう。

オンラインでそれを見つけることができれば、自分でそれを行うことをスキップしますが、明らかにすることができたという点で、この質問に対する答えは以前には見られませんでした. 私を正しい方向に向けることができる人に感謝します。

X 染色体と Y 染色体の DNA 配列を比較し、Y 染色体に固有のパターン (約 50 ～ 75 塩基対で構成される) を見つける必要があります。これらの配列部分は染色体内で繰り返されることに注意してください。これは迅速に行う必要があります (BLAST には 47 日かかり、数時間以内で済みます)。この種の比較に特に適したアルゴリズムやプログラムはありますか? 繰り返しますが、ここではスピードが重要です。

私がこれを SO に置いた理由の 1 つは、特定のアプリケーション ドメインの外にいる人々からの視点を得ることでした。彼らは、日常的な使用で文字列比較に使用するアルゴリズムを提示でき、それが私たちの使用に適用される可能性があります。だから恥ずかしがらないでください！

基本的な DNA シーケンサーを作成しようとしています。その中で、同じ長さの 2 つのシーケンスが与えられると、最小長が 3 の同じ文字列が出力されます。

戻ります

問題を解決する方法がわかりません。2 つの文字列を比較して、それらが完全に等しいかどうかを確認できます。そこから、長さ 1 の文字列サイズを比較できdfeabcますabcde。ただし、最小サイズの 3 文字まで、考えられるすべての文字列をプログラムに実行させるにはどうすればよいでしょうか? 1 つの問題は、長さ 1 の上記の例です。文字列 bcdef も実行して比較する必要があります。

このマイクロソフトのブログ投稿によるとMS Office 2010 の場合、セルあたりの文字列の最大長は 32k です。これもテストで確認しました。問題は、その長さをはるかに超える文字列 (DNA シーケンス) があり、メイン シーケンスのどこにでも一致する可能性がある 32k+ シーケンス全体で DNA のサブシーケンスを照合していることです。つまり、「サブ文字列シーケンス」を「メイン文字列シーケンス」全体に文字列一致させる必要があるため、メインシーケンスを 32k チャックに単純に分割することはできません。明確でないことの 1 つは、VBA が 32k を超える文字列の処理をサポートするかどうか、または VBA が 32k を超える文字列の連結をサポートするかどうかです。つまり、「メイン文字列シーケンス」を行の N 列目に 32k のチャンクにチャンクします。

したがって、基本的に問題は、MS-Office 2010 がセルあたり最大 32k までの文字列しかサポートしていないことです。文字列の一致が機能するためには、フォーム全体で処理する必要がある文字列よりもはるかに大きな文字列があります。

ちょっと奇妙に思えるかもしれませんが、複数の配列アラインメントの問題に対する JavaScript コードを見たことがある人がいるかどうか疑問に思っていました。そうでない場合 (私が思うに)、簡単に移植できるコード (つまり、台所の流しは必要ありません) で十分です。シンボル長が 100 ～ 200 未満のシーケンスを 4 ～ 5 個以上並べることはしないことに注意してください。

注: JavaScript がこの種の処理に最適な選択ではないことはわかっています。私を信じてください、JavaScriptでそれをしなければならないのには十分な理由があります。

私は、DNAを読み取ってそのRNAを見つけるプロジェクト（Perlで実装する必要がありますが、得意ではありません）に取り組んでいます。そのRNAをトリプレットに分割して、同等のタンパク質名を取得します。手順を説明します。

1）次のDNAをRNAに転写し、遺伝暗号を使用してアミノ酸の配列に翻訳します

例：

2）DNAを転写するには、最初に各DNAを対応するものに置き換えます（つまり、CをG、GをC、AをT、TをA）。

次に、チミン（T）ベースがウラシル（U）になることを思い出してください。したがって、シーケンスは次のようになります。

遺伝暗号の使用はそのようなものです

次に、各トリプレット（コドン）を遺伝暗号表で調べます。したがって、AGUはSerとして記述できるSerineになるか、S。AUUはIとして記述されるIsoleucine（Ile）になります。このように続けると、次のようになります。

タンパク質の表を示します。

では、どうすればそのコードをPerlで書くことができますか？質問を編集して、自分が行ったことのコードを記述します。

ウイルスの塩基対配列が2k塩基対であるため、ウイルスのDNA配列に基づいてランダムウォークを生成する必要があります。シーケンスは「ATGCGTCGTAACGT」のようになります。パスは、Aの場合は右に、Tの場合は左に、Gの場合は上に、Cの場合は下に曲がる必要があります。この目的でMatlab、Mathematica、またはSPSSを使用するにはどうすればよいですか？

これが私の問題です（私はCでプログラミングしています）：

DNA配列を含む巨大なテキストファイルがいくつかあります（各ファイルには6500万行のようなものがあり、サイズは約4〜5 GBです）。これらのファイルには多くの重複があり（まだいくつあるかはわかりませんが、何百万もあるはずです）、異なる値のみを含むファイルを出力に戻したいと思います。各文字列には品質値が関連付けられているため、たとえば、品質値が異なる5つの等しい文字列がある場合は、最良の文字列を保持し、残りの4つを破棄します。

私ができる限りメモリ要件を減らし、速度効率を改善することは重要です。私のアイデアは、ハッシュ関数を使用してJudyHS配列を作成し、文字列DNAシーケンス（長さ76文字、可能な7文字）を整数に変換してメモリ使用量を削減することでした（多くの場合、76バイトではなく4バイトまたは8バイト）何百万ものエントリはかなりの成果になるはずです）。このようにして、整数をインデックスとして使用し、そのインデックスの最高品質の値のみを格納できます。問題は、そのような長い文字列をUNIVOCALLYで定義し、整数またはlonglong内に格納できる値を生成するハッシュ関数が見つからないことです。

ハッシュ関数についての私の最初のアイデアは、Javaのデフォルトの文字列ハッシュ関数のようなものでした：s [0] * 31 ^（n-1）+ s [1] * 31 ^（n-2）+ ... + s [ n-1]ですが、最大値は8,52 * 10 ^59..大きすぎます。同じことをして、それをダブルに保存するのはどうですか？計算はかなり遅くなりますか？衝突を回避して、文字列を一意に定義する方法が必要であることに注意してください（または、衝突のたびにディスクにアクセスする必要があるため、少なくとも非常にまれなはずです。非常にコストのかかる操作です...）

したがって、リンクされたリストに DNA 文字 (A、G、T、C) のチェーンがあり、次のようなファイルから読み取ることになっています。

ここで、単一の文字は、3 つの a、t、g、c の組み合わせから得られるものです。(AGT で) 開始する必要がある場所から開始する方法を理解しましたが、文字列を読み取り、ファイルと比較して一致するものを確認する方法を定式化することはできません。これは私がこれまでに持っているものです: