基因DNA序列优化的算法选择？(与TSP有关，动态规划)

Question

以下问题专门适用于生物技术应用，但也可能说明其他领域中类似问题的一般原则。这是一个NP难问题，可以与旅行推销员问题相关，我很好奇可以使用什么算法来获得解。

简介生物背景：蛋白质由20个氨基酸组成。DNA由4个碱基组成- A，C，G，T。蛋白质的DNA序列决定了氨基酸的序列，每个连续的3个DNA碱基(该单位称为密码子)编码一个氨基酸。一个氨基酸可以由多个密码子编码，例如Valine有4种编码方式。

并非所有密码子都是平等的--有些密码子的处理速度比其他密码子快。而且，并非所有密码子对都是相等的--有些密码子对比另一些密码子对慢。

这意味着，对于含有100个氨基酸(300个DNA碱基)的特定基因，有许多方法可以编码相同的氨基酸序列，但具有非常不同的特性，例如处理速度。

给定一个具有相应速度值的密码子对表，我们想要编写一个算法，使能够输出一个期望速度的序列，例如最快和最慢的序列，以及两者之间的梯度。输入是编码一个基因的DNA序列，以及密码子对的字典，以及它们各自的速度分数(-1比1)。输出是最优的DNA序列及其整个速度分数(可以表示为所有密码子对分数之和)。氨基酸序列必须保持不变。

示例：如果我们有编码3个氨基酸的AAATTTGGG序列，并且我们有带有分数的密码子对：

AAATTT = -0.5

TTTGGG = -0.5

那么这个序列的分数可能是-1。

现在，如果我们也有两个备选方案，我们可以评估不同的可能性：

AAATTG = -0.7 AAATTC = -0.3

TTGGGC = +0.2 TTCGGA = -1.0

人们会发现，基于这一信息的最佳序列是AAATTCGGA，因为它给出的总价值为-1.3。

当然，这个问题的复杂性在于密码子对对周围所有密码子对的影响。

完整的密码子配对图将包含61*61条条目(因为有3个密码子阻止了基因的阅读)。

====

问题

我认为这是一个NP难题，与TSP有关。我见过一种方法使用模拟退火算法。我很好奇是否有其他有洞察力的方法来考虑这个问题，以及相应的算法和启发式来产生期望的输出。

如果是动态规划，哪些方法是合适的？

此外，我们如何使用算法来创建一个速度分数的梯度，而不仅仅是最大值和最小值？

Answer 1

使用遗传算法，你应该能够得到达到预期目标的序列。假设你的目标是x的速度，你可以创建一个基因群体--每个基因都编码相同的基因，但编码的密码子不同。然后选择，交配，变异几代，直到x达到(或足够接近)。突变/重组的元素必须在密码子水平(相对于核苷酸水平)。为了实现一系列不同速度的序列，在不同的目标x下多次运行该算法。

Answer 2

获取特定序列的最快(或最慢)编码应该是一个简单的动态规划问题。把每3个氨基酸组想象成64个字符中的一个字符.然后，在产生的字符串中的每一点，你将有几个字母的选择，产生所需的氨基酸，你想要最大化(最小化)与每一对相邻的字母相关的和。

从左到右，在每一点上，为每个可能的字符，计算出在该字符中终止的最大(最小)序列。每个字符最多有64种可能性。给定最多n个字符的解决方案，您可以使用这里的答案为n+1以下的字符计算出解决方案--只需取n和n+1字符的分数，并将其添加到已经计算到n个字符的最佳答案中--在n+1保存为每个可能的字符找到的最佳答案。

要获得中等分数的答案，一种方法是生成随机答案，生成正确的氨基酸序列。另一种方法是将产生最大分数的部分与产生最小分数的答案混合起来。