基因 DNA 序列优化的算法选项？ (涉及到TSP，动态规划)

Question

以下问题专门针对生物技术应用，但可以说明其他领域类似问题的一般原则。这是一个 NP 难问题，可能与旅行商问题有关，我很好奇可以使用哪些算法来得出解决方案。

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

并非所有密码子都相同 - 其中一些密码子的处理速度比其他密码子快。此外，并非所有密码子对都相等 - 有些密码子对比其他密码子对慢。

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

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

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

AAATTT = -0.5

TTTGGG = -0.5

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

现在如果我们也有成对选择，我们可以评估不同的可能性:

AAATTG = -0.7AAATTC = -0.3

TTGGGC = +0.2TTCGGA = -1.0

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

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

完整的密码子对图表将有 61*61 个条目(因为 3 个密码子停止了基因的读取)。

====

问题

我相信这是一个 NP-hard 问题并且与 TSP 有关系。我见过一种方法使用模拟退火算法。我很好奇是否有其他有见地的方法来考虑这个问题以及相应的算法和启发式方法来产生所需的输出。

如果是动态规划，什么方法合适？

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

Answer 1

使用遗传算法，您应该能够获得达到预期目标的序列。假设你的目标是速度 x，你可以创建一个基因群——每个基因编码相同的基因，但由不同的密码子编码。然后选择、交配和变异几代，直到达到 x(或足够接近)。突变/重组的元素必须在密码子水平(与核苷酸水平相反)。要获得一系列具有不同速度的序列，请使用不同的目标 x 多次运行该算法。