1

特定のアルファベットを指定して、長さ k のシーケンスの可能なすべての組み合わせを生成しようとしています (これは、バイオインフォマティクス プロジェクトのクエリ シーケンスを生成するためです)。

シーケンスは次の形式です。

ACGU (これらを Y と呼ぶ) のいずれかである最初の文字と最後の文字、およびその間の k - 2 文字は、ACGU または ? のいずれかである可能性があります。(これらを X と呼びます)。

たとえば、k = 3 の場合、パターンは YXY の形式になり、k = 5 の場合、YXXXY の形式になります。

k が既知の場合、可能なすべてのシーケンスを生成するのは簡単です。k をネストされた for ループで使用できるからです。ただし、k が事前にわからない場合、この実装は適切ではありません。

可能なシーケンスの総数は、4^2 * 5^(k-2) で表すことができます。k = 3 の場合、これは 80 の組み合わせしか得られませんが、k = 9 までスケールアップすると、1,250,000 になります!

ヒント、アイデア、提案をいただければ幸いです。

生成されたすべてのシーケンスを使用する必要があるため、配列に格納するか、作成/生成時に別の関数に渡す必要がありますが、すべてを格納する必要はありませんが、どちらでもかまいません。

どうもありがとう。

注意: 私は Objective-C で書いていますが、C スタイルのコード、疑似コード、またはアルゴリズムの単純な英語の説明が役に立ちます。

アップデート：

これは、Analog File による素晴らしい回答に基づいて作成した objc コードです。現在、1 行につき 1 つのシーケンスを stdout に出力するだけですが、文字列の配列を生成するように変更します。

貢献してくれたすべての人に感謝します。

    NSArray *yAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", nil];
    NSArray *xAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", @"?", nil];
    int i, v;
    int count = 0;
    int numberOfCases = 16 * pow(5 , (k - 2));
    for (int n = 0; n < (numberOfCases); n++) {
        i = n;
        v = i % 4;
        i = i / 4;
        count++;
        printf("\n%s", [[yAlphabet objectAtIndex:v] cStringUsingEncoding:NSUTF8StringEncoding]);
        for (int m = 1; m < (k - 1); m++) {
            v = i % 5;
            i = i / 5;
            printf("%s", [[xAlphabet objectAtIndex:v] cStringUsingEncoding:NSUTF8StringEncoding]);
        }
        printf("%s", [[yAlphabet objectAtIndex:i] cStringUsingEncoding:NSUTF8StringEncoding]);
    }
    printf("\n");
    NSLog(@"No. Sequences: %i", count);

更新 2:

生成されたシーケンスを文字列の配列に出力するコードは次のとおりです。k は目的のシーケンスの長さであり、他の場所でパラメーターとして指定されることに注意してください。これを k=9 (1,250,000 シーケンス) までテストしました。また、私のコードは ARC を使用しているため、メモリの割り当て解除は示されていません。

    NSArray *yAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", nil];
    NSArray *xAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", @"?", nil];
    NSMutableArray *sequences = [[NSMutableArray alloc] init];
    int i, v;
    int count = 0;
    int numberOfCases = 16 * pow(5 , (k - 2));
    for (int n = 0; n < (numberOfCases); n++) {
        i = n;
        v = i % 4;
        i = i / 4;
        count++;
        NSMutableString *seq = [[NSMutableString alloc] initWithString:[yAlphabet objectAtIndex:v]];
        for (int m = 1; m < (k - 1); m++) {
            v = i % 5;
            i = i / 5;
            [seq appendString:[xAlphabet objectAtIndex:v]];
        }
        [seq appendString:[yAlphabet objectAtIndex:i]];
        [sequences addObject:seq];
    }
    NSLog(@"No. Sequences looped: %i", count);

    //print the array to confirm
    int count1 = 0;
    for (NSMutableString *str in sequences) {
        fprintf(stderr, "%s\n", [str cStringUsingEncoding:NSUTF8StringEncoding]);
        count1++;
    }
    NSLog(@"No. Sequences printed: %i", count1);
    NSLog(@"Counts match? : %@", (count == count1 ? @"YES" : @"NO"));
4

3 に答える 3

1

どれだけのケースが発生するかがわかります。これは疑似コードです (k はシーケンス長)

 for n = 0 to num_of_cases - 1

    i = n

    v = i % length_of_alphabeth_Y
    i = i / length_of_alphabeth_Y
    output vth char in alphabeth Y

    for m = 1 to k-1
       v = i % length_of_alphabeth_X
       i = i / length_of_alphabeth_X
       output vth char in alphabeth X

    output ith char in alphabeth Y
    output end of sequence

外側のループの反復ごとにケースが生成されます。私が書きoutputましたが、動的に割り当てられた構造にデータを「格納」するのは簡単です (roes の n 個のインデックス、最初のケースは列 0、次に列の m 個のインデックス、最後のケースは列です)。 k-1. その場合、「シーケンスの終わり」は n のインクリメントに含まれるため、出力する必要はありません)。

数字に応じて異なる基数を使用することを除いて、基数 length_of_alphabeth で効果的に「カウント」する方法に注意してください。モジュロは最下位桁を提供し、整数除算はそれを取り除き、次の桁を最下位桁にシフトします。

n が単なる値であると想像できれば、特定の基数はなく、ロジックはかなり単純です。理解したら、おそらくこれを最初から自分で書くことができます。

于 2012-08-14T01:12:32.960 に答える
0

k がパラメーターとして渡されるように聞こえるので、このようなもの (Python 風の疑似コード) が機能するはずです。

Y_alphabet = ['A','C','G','U']
X_alphabet = ['A','C','G','U','?']

outputs = []

for i in range(k):
    if i == 0 or i == k-1:
        current_alphabet = Y_alphabet
    else:
        current_alphabet = X_alphabet

    last_outputs = outputs
    outputs = []

    for next_character in current_alphabet:
        # This just replaces outputs with a new list that consists
        # of all the possible sequences of length i appended with
        # the current character
        outputs += [seq + next_character for seq in last_outputs]
于 2012-08-14T01:28:09.957 に答える
0

これを行うための基本的な形式は次のようになります (Java っぽい疑似コード)

char[] output = new char[k];
pubilc void go(cur_k){
   if(cur_k>k) // do something - copy the array and store it, etc.
   for( char letter : alphabet ){
       output[cur_k]=char_letter;
       go(cur_k+1);
   }
}
于 2012-08-14T01:19:53.357 に答える