使用两个“字母”的不同长度的序列组合

2012-08-14 objective-c algorithm permutation combinations bioinformatics

我正在尝试生成给定某个字母的长度为k的序列的所有可能组合(这是为生物信息学项目生成查询序列)。

序列的形式为:

可以是ACGU中的任何一个的第一个字符和最后一个字符(称为Y),介于两者之间的k-2个字符可以是ACGU或?中的任何一个。 (称为X)。

例如,如果k = 3,则图案的形式为YXY,如果k = 5,则图案为YXXXY。

如果已知k,则生成所有可能的序列很容易,因为您可以只使用k个嵌套的循环。但是,如果k事先未知,则此实现不适合。

可能的序列总数可以用4 ^ 2 * 5 ^(k-2)表示。在k = 3的情况下,仅给出80种组合,但将其扩展到k = 9则您有1,250,000!

任何提示,想法或建议将不胜感激。

我需要使用生成的每个序列,因此它们既可以存储在数组中,也可以在创建/生成时传递给另一个函数,尽管我不希望不必存储所有的序列,但这并不重要。

非常感谢。

注意:我使用的是Objective-C语言,但是任何C风格的代码,伪代码或简单的算法英语描述都将有所帮助。

更新:

这是我根据Analog File出色的回答编写的objc代码。当前,它仅将每行一个序列输出到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"));

Answers

您知道您将要得到多少个案件。 这是伪代码(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

外循环的每次迭代都会生成一个case。我编写了output但是很容易将数据“存储”在动态分配的结构中(子程序中n个索引,第一种情况是第0列,然后m个索引在列中,最后一种情况是第k-1列。如果执行该操作,则不必输出“序列末尾”,因为它包含了n)的增量。

注意我们如何有效地“计算” baselength_of_alphabeth的底数,除了我们根据数字使用不同的底数。模数给出最低有效位,整数除法将其除掉,然后将下一位移至最低有效位。

如果您可以将n想象成只是一个没有特定底数的 ,那么逻辑就很简单。一旦理解,您可能可以从头开始编写。

这样做的基本形式如下(Java式的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);
   }
}

听起来好像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]

Related