以下の質問は、特にバイオテクノロジーアプリケーションに適用されますが、他の分野での同様の問題の一般的な原則を示している場合があります。これは巡回セールスマン問題に関連する可能性のあるNP困難な問題であり、解決策に到達するためにどのアルゴリズムを使用できるのか興味があります。
簡単な生物学的背景：タンパク質は20個のアミノ酸で構成されています。DNAは4つの塩基（A、C、G、T）で構成されています。タンパク質のDNA配列によって、アミノ酸の配列が決まります。3つのDNA塩基（単位はコドンと呼ばれます）の連続する各配列は、1つのアミノ酸をコードします。単一のアミノ酸は複数のコドンでコード化できます。たとえば、バリンには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
この情報に基づく最適なシーケンスは、全体の値が-1.3になるため、AAATTCGGAであることがわかります。
もちろん、この問題の複雑さは、周囲のすべてのコドンペアに対するコドンペアの影響にあります。
完全なコドンペアチャートには61*61のエントリがあります（3つのコドンが遺伝子の読み取りを停止するため）。
====
質問
これはNP困難な問題であり、TSPと関係があると思います。シミュレーテッドアニーリングアルゴリズムを使用するアプローチを見てきました。この問題とそれに対応するアルゴリズムおよびヒューリスティックを考慮して目的の出力を生成する他の洞察に満ちた方法があるかどうか知りたいです。
動的計画法の場合、どのようなアプローチが適切でしょうか？
また、アルゴリズムを使用して、最大値と最小値だけでなく、速度スコアの勾配を作成するにはどうすればよいですか？