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 代码。目前它只将每行一个序列输出到标准输出，但我将对其进行修改以生成一个字符串数组。

非常感谢所有做出贡献的人。

    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) 的增量中。

请注意我们如何有效地“计算”base length_of_alphabeth，除了我们根据数字使用不同的基础。模数为您提供最低有效位，整数除法摆脱它并将下一位移动到最低有效位置。

如果您可以将 n 想象为一个value，没有特定的基础，那么逻辑就相当简单。一旦你理解了它，你可能可以自己从头开始编写它。

于 2012-08-14T01:12:32.960 回答
0

执行此操作的基本形式如下所示（Java-ish psuedocode）

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 回答
0

听起来 k 将作为参数传入，所以这样的东西（在 Python-ish 伪代码中）应该可以工作

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 回答