2

私はたくさんの (何百万もの) 小さな実験からのログを持っています。

各ログには、エントリのリスト (数十から数百) が含まれています。各エントリは、タイムスタンプとイベント ID です (数千のイベント ID があり、それぞれがログで何度も発生する可能性があります)。

1403973044 アルファ
1403973045 ベータ版
1403973070 ガンマ
1403973070 アルファ
1403973098 デルタ

あるイベントが後で別のイベントを引き起こす可能性があることを知っています。

私はこのデータセットを研究しています。実験で十分頻繁に発生する「安定した」一連のイベントを探しています。

あまり多くのコードを記述せず、独自のソフトウェアを使用せずにこれを行う方法はありますか? ソリューションは十分にスケーラブルで、大規模なデータセットで機能する必要があります。

この作業は、バイオインフォマティクスが行うこと、つまり DNA の配列を見つけることなどに似ていると思います。私のタスクだけがアルファベットに4文字以上含まれています...（@JayInNycのおかげで更新：プロテオミクスは私のものよりも大きなアルファベットを扱っています。）

（ところで、シーケンスがどれだけ安定して類似しているか、シーケンスの最小長などは事前にわからないことに注意してください。データセットを調査しているため、外出先でこれを把握する必要があります。）

とにかく、使用できるアプローチ/ツール/ライブラリに関する提案はありますか?

更新: コメントの質問に対するいくつかの回答:

安定したシーケンス:実験全体で十分な頻度で見つかりました。（どれくらいの頻度で十分ですか？まだわかりません。チェーンのトップを計算し、最もレアなものを捨てる必要があるようです。）

類似シーケンス: 似ているシーケンス。「シーケンス 'ABCD E' と 'ABCE D' (シーケンスのわずかな違い) は似ていますか?あなたへ？" — どちらの質問にもはい。より抜本的な変異もおそらく問題ありません。繰り返しますが、トップを計算して、最も似ていないものを破棄できるようにしたいと思います...

タイミング:現時点ではタイミング情報を破棄できます (ただし、注文はできません)。しかし、それを類似性指数の公式に入れたらクールだろう。

更新 2: 期待される出力。

最後に、最も人気のある最長の安定したチェーンの評価をしたいと思います。3 つの要素すべての組み合わせが、評価スコアの計算に影響を与えるはずです。

そのような評価のチェーンは、明らかに、かなり類似したチェーンのクラスターです。

チェーンクラスターの合成例:

アルファ
ベータ
ガンマ
[ごみ]
[ごみ]
デルタ

別：

アルファ
ベータ
ガンマ|ゼータ|イプシロン
デルタ

（または、今のところ思い浮かばなかったバリアントは何でも。）

したがって、最終的な出力は次のようになります (この例では数字は完全にランダムです)。

チェーン クラスター ID | 見つかった時間 | 時間刺し。因子 | チェーン刺し。因子 | 長さ | スコア
あ | 12345 | 123 | 3 | 5 | 100000
ビ | 54321 | 12 | 30 | 3 | 700000
4

2 に答える 2

0

ウィキペディアは、アルゴリズムを「正確なステップの正確なリスト」と定義しています。「実験で十分頻繁に発生する「安定した」一連のイベントを探しています。」定義のない「安定」と「十分な頻度」は、アルゴリズムを提供するタスクを不可能にします。

そこで、長さ 2 のシーケンスの頻度を計算する簡単なものを示します。タイムスタンプは無視します。awk コードは次のとおりです (pW は前の Word を表し、pcs はペア カウンターを表します)。

#!/usr/bin/awk -f

BEGIN { getline; pW=$2; }

{ pcs[pW, $2]++; pW=$2; }

END {
    for (i in pcs)
        print i, pcs[i];
}

意味のあるものを表示するためにサンプルを複製しました

1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 alpha
1403973098 delta
1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 beta
1403973098 delta
1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 beta
1403973098 delta
1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 beta
1403973098 delta

上記のコードを実行すると、次のようになります。

gammaalpha 1
alphabeta 4
gammabeta 3
deltaalpha 3
betagamma 4
alphadelta 1
betadelta 3

これは、アルファの後にベータが続き、ベータの後にガンマが続くと解釈でき、サンプル内でそれぞれ 4 回発生する最も頻度の高い長さの 2 つのシーケンスです。それは、十分に頻繁に発生する安定したシーケンスの定義になると思います。

次は何ですか？

(1) 上記のコードを長さ N のシーケンスに簡単に適用でき、頻繁に発生するシーケンスを見つけるには、2 列目の出力をソート (-k2nr) できます。

(2) N に制限を設けるには、イベントがそれ自体をトリガーしないことを規定できます。これにより、カットオフ ポイントが提供されます。または、タイムスタンプ、つまり連続するイベント間の差に制限を設けることができます。

(3) これまでのところ、これらのシーケンスは実際には文字列であり、それらの間の完全一致 (CLRS 用語) を使用しました。代わりに、お気に入りの類似度を使用することを妨げるものは何もありません。

{ pcs[CLIFY(pW, $2)]++; pW=$2; }

CLIFY は、k 個の連続するイベントを取り、それらをビンに入れる関数です。つまり、ABCDE と ABDCE を同じビンに入れたいと思うかもしれません。CLIFY はもちろん、これまでのビンのセットを追加の引数として取ることができます。

awk の選択は便宜上のものです。飛ぶことはありませんが、簡単に並行して実行できます。

これを何に使用したいかは不明ですが、マルコフ連鎖の Google 検索、Mark V Shaney がおそらく役立つでしょう。

于 2014-06-30T10:09:13.473 に答える
0

私はこのセットアップについて、過去 1 日ほど考えてきました。bash などで健全なスケーラブルな方法でそれを行う方法です。答えは、データから引き出したいリレーショナル情報と見かけのサイズによって決まります。現在持っているデータセットの。xleanest ソリューションは、データセットをリレーショナル データベースにロードすることです (MariaDB をお勧めします)。

データはすでにかなりきれいな形式で存在するため、データベースにデータを取得するためのオプションは 2 ですLOAD DATA INFILE。 ; または (2) シナリオで bash を使用してファイルをwhile read line; do解析し、データを解析して目的のテーブル形式のデータを取得し、mysql バッチ モードを使用して 1 回のパスで情報を mysql に直接ロードします。bash コマンドの一般的な形式はmysql -uUser -hHost database -Bse "your insert command".

リレーショナル データベースに入ると、毎回異なる方法でデータを処理するために bash スニペットを継続的に作成/再作成するのではなく、適切な方法でデータに対して柔軟なクエリを実行できる適切なツールが得られます。それはおそらくあなたが探している最高のスケーラブルなソリューションです。事前にもう少し作業が必要ですが、今後のセットアップははるかに優れています。

于 2014-06-30T09:53:33.200 に答える