15

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

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

4

4 に答える 4

3
  1. シーケンス X でサフィックス ツリーS を構築します。
  2. シーケンス Y の開始位置 i ごとに、S で文字列 Y[i..i+75] を探します。位置 i で開始する一致が見つからない場合 (つまり、j < 75 ヌクレオチドが一致した後で検索が失敗した場合)、次のようになります。 Y に固有の長さ j の文字列が見つかりました。
  3. すべての開始位置 i で最小のそのような文字列は、最短の一意の文字列です (または、長さを最小化することに関心がない場合は、そのような文字列を見つけたら停止します)。

合計時間: O(|X| + m|Y|) ここで、m は文字列の最大長です (例: m = 75)。

一般化されたサフィックス ツリーに基づく、さらに効率的なアルゴリズムが存在する可能性があります。

于 2010-08-27T03:51:21.303 に答える
2

比較する単一の X と単一の Y があると想定しています。それらを連結し、どちらにも現れないマーカー文字で区切って、例えば XoY を形成します。http://en.wikipedia.org/wiki/Suffix_arrayを線形時間で形成します。

得られるのは、連結された文字列内の位置へのポインターの配列です。ポインターは、ポインターが指す部分文字列が配列内でアルファベット順に表示されるように配置されています。また、LCP 配列を取得し、サフィックスと配列内のその直前のサフィックスの間で共有される最長の共通プレフィックスの長さを示します。これは実際には、その位置とそれよりも小さい部分文字列の間で共有される最長の共通プレフィックスです。これは、共通プレフィックスが長く、string[i] より小さいものはすべて、それと現在の文字列 [i - 1] の間でソートされるためです。

X は Y の前にあるため、ポインターが指している元の文字列をその位置から判断できます。配列を X ポインターと Y ポインターのサブセクションに交互に分割できます。pos[i] と pos[i - 1] の間で共有される共通のプレフィックスの長さは lcp[i] です。pos[i] と pos[i-2] の間で共有されるプレフィックスの長さは、min(lcp[i], lcp[i-1]) です。したがって、X の範囲の直前の Y 値から開始すると、各ステップで min 操作を実行してセクションをステップ ダウンすることで、その Y とすべての X の間のプレフィックスの文字数を計算できます。同様に、これらすべての X と接尾辞配列で次に現れる Y の間で共有される接頭辞の文字数を、X ごとに 1 分のコストで計算できます。もちろん、Y 範囲についても同様です。

同じ位置から始まるこれより1文字長い文字列は他の性別にはまったく表示されないため、XまたはYのいずれか内の部分文字列が必要だと思います。上記の min() 計算を実行したら、ヒープを使用して N 個の最小プレフィックス部分文字列を抽出し、N 個の最小エントリを追跡できると思います。ここではすべて、|X| に比例して時間がかかると思います。+ |Y| (N が |X| または |Y| に匹敵する場合を除く)。

于 2010-08-27T05:19:25.723 に答える
1

この論文には、BLASTを適応させてパフォーマンスを向上させるためのいくつかの代替案があるかもしれません（問題空間を細分化することによって）。

于 2010-08-27T02:53:53.330 に答える
0

興味深い答えがあります。それは技術的なものになります。最新のビデオカードのGPUは高度に並列処理される環境（小さなスーパーコンピューターなど）であるため、主なアイデアは、サブシーケンスの比較をGPUで実行する必要があるということです。したがって、X染色体が1億5400万ペアであるとすると、塩基対を1ピクセルとしてエンコードできます。つまり、1億5400万ピクセルで構成されるX染色体の画像が得られます。この画像サイズは、約500MBになります。Y染色体の場合、160MBのサイズの画像が得られます。したがって、これら2つの（500 + 160）MB画像は、降下ビデオカードで非常に効果的に処理できます。（1 GB以上のビデオRAMを搭載したビデオカードを入手するだけです）。

次のステップは、おそらくPixel Shader、Cuda、またはOpenCLを使用してGPUプログラムを作成することです。

GPUプログラムは単純です。基本的に、Y染色体画像の50〜75個の隣接ピクセルをX染色体画像のすべてのピクセルと比較します。したがって、このGPUプログラムには最大75 * 154百万の操作が必要であり、これは最新のGPUで1時間程度で計算されます。Yのすべてのサブシーケンスが並行してテストされるためです。

それが役立つことを願っています

于 2010-08-27T09:40:49.673 に答える