计算直到给定长度的所有可能的序列

Question

我的问题涉及生物信息学，特别是蛋白质序列，然而，实际上并不需要生物学知识。我试图在Perl中找到一种有效的方法来解决这个问题：

蛋白质序列基本上是长度不同的序列或字符串，由20个氨基酸或字符的组合组成。

因此，在长度为1时，将有20种可能性。问题是，每增加1个字符，可能性的数量就会大幅增加。

我想对每个长度的序列进行另一次计算。蛋白质序列可以是成百上千个氨基酸。我只需要得到所有可能的序列来做这件事。

编辑:我意识到不可能计算每一个长度，我不需要这样做，但我想要计算一个合理的长度，不会花费任何接近宇宙的长度。

对最有效的编码方式有什么建议吗？

编辑:我真的不需要为1000个序列这样做，我只是对我不知道的想法、资源、函数等感兴趣，这可能有助于我理解最有效的方法。

Answer 1

推荐的Math::Combinatorics模块不支持置换置换，这是您解决此问题所需的，否则您的蛋白质长度永远不会超过20个氨基酸。

Algorithm::Combinatorics将完成这项工作，并且部分是用C语言编写的，因此它应该可以很好地执行。

这是一个生成所有氨基酸对的例子。我只展示了输出的前几行，因为即使这样也会产生400种变体！

use strict;
use warnings;

use Algorithm::Combinatorics 'variations_with_repetition';

my @acids = qw/ ala arg asn asp cys gln glu gly his ile leu lys met phe pro ser thr trp tyr val /;

my @proteins = variations_with_repetition(\@acids, 2);

print "@$_\n" for @proteins;

输出

ala ala
ala arg
ala asn
ala asp
ala cys
ala gln
ala glu
ala gly
ala his
ala ile
ala leu
ala lys
ala met
ala phe
ala pro
ala ser
ala thr
ala trp
ala tyr
ala val
arg ala
arg arg
arg asn
arg asp
arg cys
arg gln
arg glu
arg gly
...

Answer 2

20^1000是一个真正的large number。您说您需要对每个序列进行一些计算，如果不向外扩展到多台计算机，这是不可能的。即使每秒进行一百万次计算，也需要使用many times the age of the universe才能完成计算。

Answer 3

考虑到你的语法涉及每一个已知长度的序列，这个问题永远不会收敛到一个合理的结果-你会一直走到无限长的长度。此外，你的计算将包括许多与现实无关的序列，或者二肽和巨型分子之间的比较。即使你将你的计算限制在已知最大的蛋白质(titin，~34350个氨基酸)的长度上，它仍然是一个令人望而却步的计算。

作为另一种建议:你是否考虑过将其限制在已知存在或可以从遗传数据库中预测到的蛋白质上？这将把工作量减少到几千个与生物相关的序列，并且对于大多数生物信息学应用来说，遗传或序列数据可以从结构良好的数据库中广泛获得。