Создать все возможные перестановки данного набора переменных
У меня есть проблема, связанная с обратным переводом.
Саму проблему можно сформулировать так: При заданном наборе символов из 20 уникальных алфавитов (соответствующих 20 аминокислотам) каждый алфавит генерируется кодом, состоящим из 3 символов [любые 3 из A, T, G, C]. Генерация всех возможных нуклеотидных последовательностей, кодирующих данную аминокислотную последовательность / последовательности.
Существует 64 возможных комбинации нуклеотидов [ATGC] для 20 аминокислот.
Например: лизин, который представлен буквой K, кодируется двумя триплетами (= кодоны), AAA и GAA.
Прямая трансляция хороша, так как я могу просто отобразить триплеты на коды аминокислот, но проблема заключается в обратной трансляции, где возможны различные комбинации триплетов, поскольку большинство аминокислот могут кодироваться несколькими кодонами.
Это основной каркас моей программы:
//Map all Amino Acids with their corresponding codons.
std::map<std::string, string, std::less<std::string> > somevar;
somevar["K"]="AAA|GAA";......so on.
//Take input in string of Amino Acid single letter codes.
//Split each Amino acid into corresponding codons using stringstream
while(std::getline(ss, token, '|')){}
//Store the values in vector.
Первая проблема: поскольку я не знаю, каков будет размер входной строки, мне нужны динамические массивы векторов или вектор векторов. (Проще говоря, если происходит что-то вроде KK, будут две переменные типа массива, хранящие все триплеты для KK.) Есть ли способ удалить эту избыточность (заглядывая непосредственно в некоторую таблицу)?
//Pass the arrays to a function which will return all possible permutations.
Вторая проблема: после решения первой проблемы я хочу создать все возможные комбинации нуклеотидной последовательности, возможные с данной аминокислотной цепочкой (то есть все возможные комбинации, полученные из каждого вновь созданного массива (наборов)).
KK приведет к: AAAGAA, AAAAAA, GAAAAA, GAAGAA.
Единственное ограничение заключается в том, что сложность должна быть ~ O (n ^ 2), и мне было интересно, могу ли я сделать это рекурсивно, или есть какая-то встроенная функция / библиотека в c ++, которая может помочь мне в генерации всех возможных перестановок из заданный (переменный) набор данных.
Изменить: еще один пример
Скажем, если случайная буква A имеет 3 кодона, а буква Y — 5, то общее количество комбинаций будет 3 * 5.
Если M = AAT, ATA и N = GTT, AGT, TGT, то результатом будет 1) AATGTT, 2) ATAGTT, 3) AATAGT, 4) AATTGT, 5) ATAAGT, 6) ATATGT
Решение
Следующее может помочь:
std::vector<std::string> translate(const std::vector<std::string>& v,
const std::map<std::string, std::vector<std::string>>& mapping)
{
if (v.empty()) {
return {};
}
std::vector<std::string> res = {""};
for (const auto& s : v) {
std::vector<std::string> tmp;
for (const auto& seq : mapping.at(s)) {
for (const auto& old: res) {
tmp.push_back(old + seq);
}
}
res = std::move(tmp);
}
return res;
}
с:
vпоследовательность переводаmappingотображение между"K"а также{"AAA", "GAA"}
Другие решения
Вы действительно хотите получить все перестановки (все возможные упорядочения кодонов) или все возможные переводы букв в кодоны (больше похоже на гомофоническую замену)?
Если это последний, для вашего вопроса 2 количество выходных строк будет O (2 ^ n), если все буквы имеют 2 возможных кодона (намного больше, чем O (n ^ 2)).
Вы все еще можете сделать это относительно просто с помощью рекурсивной функции (или нет, как @ Jarod42).
На ваш вопрос 1, я думаю, что ввод вашей процедуры на самом деле является компактным способом хранения вывода …
Ваш тип возврата может быть std::vector<std::string> для одной входной строки, так что вы можете пойти на std::vector<std::vector<std::string> > для всех выходных строк?