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

Question

“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;
}

Answer 1

您需要使用递归来保持灵 active (即，以便您可以轻松更改 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);

干杯。