C++-输出给定长度的所有可能的DNA kmers

“kmer”是长度为K的DNA序列。有效的DNA序列(出于我的目的)只能包含以下4个碱基:A，C，T，G。我正在寻找一种C++算法，该算法仅将这些基数的所有可能组合按字母顺序输出到字符串数组中。例如，如果K = 2，则程序应生成以下数组:

kmers[0]  = AA
kmers[1]  = AC
kmers[2]  = AG
kmers[3]  = AT
kmers[4]  = CA
kmers[5]  = CC
kmers[6]  = CG
kmers[7]  = CT
kmers[8]  = GA
kmers[9]  = GC
kmers[10] = GG
kmers[11] = GT
kmers[12] = TA
kmers[13] = TC
kmers[14] = TG
kmers[15] = TT

如果我正确地考虑了这个问题，那么问题就可以分解为将十进制整数转换为以4为基数，然后替换为适当的基数。我以为可以使用itoa，但是itoa不是C标准的，并且我的编译器不支持它。我欢迎任何聪明的主意。这是我的示例代码:

#include <iostream>
#include <string>
#include <math.h>

#define K 3

using namespace std;

int main() {

  int num_kmers = pow(4,K);
  string* kmers = NULL;

  /* Allocate memory for kmers array */
  kmers = new string[num_kmers];

  /* Populate kmers array */
  for (int i=0; i< pow(4,K); i++) {

    // POPULATE THE kmers ARRAY HERE

  }

  /* Display all possible kmers */
  for (int i=0; i< pow(4,K); i++)
    cout << kmers[i] << "\n";

  delete [] kmers;
}

最佳答案

您将需要使用递归来提高灵活性(即可以轻松更改K)。

void populate(int depth, string base, string* kmers, int* kmers_offset)
{
    if(depth == K)
    {
        kmers[*kmers_offset].assign(base);
        (*kmers_offset)++;
    }
    else
    {
        static char bases[] = { 'A', 'C', 'G', 'T' };
        for(int i = 0; i < 4; ++i)
            populate(depth + 1, base + bases[i], kmers, kmers_offset);
    }
}

然后这样称呼它:

int kmers_offset = 0;
populate(0, "", kmers, &kmers_offset);

干杯。

关于C++-输出给定长度的所有可能的DNA kmers，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5569453/