DNA 对比问题求解

Monox

Sevk 发表于 2012-12-23 13:43
好复杂,应该用脚本写:输出:

一般DNA复制出现每种错误的概率是不相同的，特别是插入/删除与变成其他碱基的概率是不一样的，你的脚本不但没有考虑这些因素，你自己也注释有很多情形略掉了，我可以保证你没考虑的情况比你注释的要多的多。

To 楼主，如果你想要最优解的话，这种问题一般是用动态规划算法来实现，先把每种突变打个分，写成打分矩阵的形式，然后进行动态规划比对，最后反推遗传距离，甚至可以反推出到底发生了怎样的突变。一般动态规划算法比较费时间和空间，我曾经用 C 语言和 Perl 语言都写过，Perl 版的处理十几个碱基的形式就得花不少时间，所以这种问题肯定是不能用脚本语言来做的。至于你想让速度和内存进一步优化的话，如果你不需要最优解，次优解也可以接受的话，有很多基于动态规划算法的启发式方法。

动态规划算法及相关次优解的算法在网上以及书本上有很多例子和解释。现成的比对软件有不少，而且很多比对软件都可以输出遗传距离的，因此我这里就不直接给你代码了，也没时间为你写这样的代码。不过，看你提的要求就知道你连用户接口部分的工作也想交给别人写，或许这个论坛里会有一两个好事之徒帮你写也说不定。Anyway，祝你好运了。