1

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

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

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

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

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

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

AAATT = -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-hard 问题，并且与 TSP 有关。我见过一种方法使用模拟退火算法。我很好奇是否还有其他有见地的方法来考虑这个问题以及相应的算法和启发式方法来产生所需的输出。

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

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

4

2 回答 2

1

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

于 2012-10-14T00:27:19.337 回答
0

为特定序列获得最快（或最慢）的编码应该是一个简单的动态规划问题。将每个 3 个氨基酸组视为 64 个字符字母表中的一个字符。然后在结果字符串中的每个点，您都可以选择产生所需氨基酸的几个字母，并且您希望最大化（最小化）与每对相邻字母相关的总和。

从左到右，在每个点，对于每个可能的字符，计算出以该字符结尾的最大（最小）序列。每个字符最多有 64 种可能性。给定最多 n 个字符的解决方案，您可以在此处使用该答案来计算最多 n+1 个字符的解决方案 - 只需将字符 n 和 n+1 的分数添加到已经计算出的最佳答案中最多 n 个字符 - 在 n+1 处保留您为每个可能的字符找到的最佳答案。

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

于 2012-10-14T04:51:39.240 回答