一.什么是動(dòng)態(tài)規(guī)劃算法

1.1總體思想

·動(dòng)態(tài)規(guī)劃算法與分治法類似，基本思想也是將待求解的問(wèn)題分成若干個(gè)子問(wèn)題

·經(jīng)過(guò)分解得到的子問(wèn)題往往不是互相獨(dú)立的，有些子問(wèn)題被重復(fù)計(jì)算多次

·如果能夠保存已解決的子問(wèn)題答案，在需要時(shí)再找出來(lái)已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法（備忘錄）

1.2使用動(dòng)態(tài)規(guī)劃求解的問(wèn)題需要具備的基本要素

1）重復(fù)子問(wèn)題

·遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次，這種性質(zhì)被稱為子問(wèn)題的重疊性質(zhì)

·動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。

·通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)，用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。

2）最優(yōu)子結(jié)構(gòu)

·一個(gè)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解，這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)

·分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾

·利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解

·最優(yōu)子結(jié)構(gòu)是一個(gè)問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提

1.3動(dòng)態(tài)規(guī)劃求解的基本步驟

1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征

2）遞歸地定義最優(yōu)質(zhì)

3）以自底向上的方式計(jì)算出最優(yōu)值

4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解

二.打分矩陣代碼

import random  # 1. 生成一個(gè)指定長(zhǎng)度的隨機(jī)DNA序列  
def generate_dna(length):  dna_bases = 'ACGT'  # DNA的四個(gè)堿基  sequence = ''  # 初始化空序列  for _ in range(length):  # 循環(huán)length次  sequence += random.choice(dna_bases)  # 每次從四個(gè)堿基中隨機(jī)選一個(gè)添加到序列中  return sequence  # 返回生成的DNA序列  # 2. 在DNA序列中隨機(jī)位置插入一個(gè)可能突變的motif  
def insert_motif(dna, motif, mutation_rate):  mutated_motif = ''  # 初始化突變的motif為空字符串  for base in motif:  # 遍歷motif中的每個(gè)堿基  if random.random() < mutation_rate:  # 如果隨機(jī)數(shù)小于突變率  mutated_motif += random.choice('ACGT')  # 則該位置堿基隨機(jī)突變  else:  mutated_motif += base  # 否則保持原樣  insert_point = random.randint(0, len(dna))  # 在DNA序列中隨機(jī)選擇一個(gè)插入點(diǎn)  return dna[:insert_point] + mutated_motif + dna[insert_point:]  # 插入突變的motif  # 3. 生成多條帶有隨機(jī)插入motif的DNA序列  
def generate_sequences(num_sequences, dna_length, motif_length, mutation_rate):  sequences = []  # 初始化一個(gè)空列表來(lái)存儲(chǔ)生成的序列  motif = generate_dna(motif_length)  # 生成一個(gè)隨機(jī)的motif  for _ in range(num_sequences):  # 循環(huán)生成指定數(shù)量的序列  dna = generate_dna(dna_length)  # 生成一個(gè)DNA序列  dna_with_motif = insert_motif(dna, motif, mutation_rate)  # 插入motif  sequences.append(dna_with_motif)  # 將序列添加到列表中  return sequences  # 返回生成的序列列表  # 使用函數(shù)生成序列并打印  
sequences = generate_sequences(5, 20, 5, 0.1)  
for seq in sequences:  print(seq)

三.編寫一個(gè)函數(shù)，生成m條DNA序列，每條序列長(zhǎng)度為k，然后對(duì)每條序列隨機(jī)插入一個(gè)長(zhǎng)度為L(zhǎng)的motif，motif的突變率為n

import random  # 1. 生成一個(gè)指定長(zhǎng)度的隨機(jī)DNA序列  
def generate_dna(length):  dna_bases = 'ACGT'  # DNA的四個(gè)堿基  sequence = ''  # 初始化空序列  for _ in range(length):  # 循環(huán)length次  sequence += random.choice(dna_bases)  # 每次從四個(gè)堿基中隨機(jī)選一個(gè)添加到序列中  return sequence  # 返回生成的DNA序列  # 2. 在DNA序列中隨機(jī)位置插入一個(gè)可能突變的motif  
def insert_motif(dna, motif, mutation_rate):  mutated_motif = ''  # 初始化突變的motif為空字符串  for base in motif:  # 遍歷motif中的每個(gè)堿基  if random.random() < mutation_rate:  # 如果隨機(jī)數(shù)小于突變率  mutated_motif += random.choice('ACGT')  # 則該位置堿基隨機(jī)突變  else:  mutated_motif += base  # 否則保持原樣  insert_point = random.randint(0, len(dna))  # 在DNA序列中隨機(jī)選擇一個(gè)插入點(diǎn)  return dna[:insert_point] + mutated_motif + dna[insert_point:]  # 插入突變的motif  # 3. 生成多條帶有隨機(jī)插入motif的DNA序列  
def generate_sequences(num_sequences, dna_length, motif_length, mutation_rate):  sequences = []  # 初始化一個(gè)空列表來(lái)存儲(chǔ)生成的序列  motif = generate_dna(motif_length)  # 生成一個(gè)隨機(jī)的motif  for _ in range(num_sequences):  # 循環(huán)生成指定數(shù)量的序列  dna = generate_dna(dna_length)  # 生成一個(gè)DNA序列  dna_with_motif = insert_motif(dna, motif, mutation_rate)  # 插入motif  sequences.append(dna_with_motif)  # 將序列添加到列表中  return sequences  # 返回生成的序列列表  # 使用函數(shù)生成序列并打印  
sequences = generate_sequences(5, 20, 5, 0.1)  
for seq in sequences:  print(seq)

四.對(duì)生成的已插入突變motif的序列集合，編寫一套函數(shù)，尋找其中的motif,可指定motif長(zhǎng)度;

# 定義一個(gè)名為 find 的函數(shù)，它接受兩個(gè)參數(shù)：  
# sequence_set 是一個(gè)包含多個(gè) DNA 序列的列表  
# motif_length 是我們想要查找的子序列（也稱為 motif）的長(zhǎng)度  
def find(sequence_set, motif_length):    # 初始化一個(gè)空集合 motifs，用于存儲(chǔ)找到的所有唯一的 motif  motifs = set()    # 遍歷 sequence_set 中的每一條序列  for sequence in sequence_set:    # 對(duì)于每一條序列，我們從其第一個(gè)堿基開(kāi)始，直到剩下的堿基數(shù)量少于 motif_length 為止  # 這樣確保我們可以從序列中提取出完整長(zhǎng)度的 motif  for i in range(len(sequence) - motif_length + 1):    # 從當(dāng)前位置 i 開(kāi)始，提取長(zhǎng)度為 motif_length 的子序列  motif = sequence[i:i+motif_length]    # 將提取到的 motif 添加到 motifs 集合中  # 由于 motifs 是一個(gè)集合，所以重復(fù)的 motif 會(huì)被自動(dòng)去除  motifs.add(motif)    # 函數(shù)返回包含所有唯一 motif 的集合  return motifs    # 測(cè)試數(shù)據(jù)：一個(gè)包含三條 DNA 序列的列表和一個(gè) motif 長(zhǎng)度值  
sequence_set = ['ACGTTAGC', 'GTATCGAG', 'CGTACGTA']    
motif_length = 4    # 調(diào)用 find 函數(shù)，傳入測(cè)試數(shù)據(jù)，并將返回的結(jié)果存儲(chǔ)在變量 motifs 中  
motifs = find(sequence_set, motif_length)    
# 打印出找到的所有唯一 motif  
print(motifs)

五.對(duì)生成的已插入突變motif的序列集合，編寫一套函數(shù)，基于分支界定法尋找指定長(zhǎng)度的motif,并與遍歷法比較計(jì)算效率

import itertools  
import time  # 計(jì)算motif在序列中的得分  
def calculate_score(motif, sequences):  score = 0  for seq in sequences:  min_distance = float('inf')  for i in range(len(seq) - len(motif) + 1):  distance = sum(motif[j] != seq[i + j] for j in range(len(motif)))  min_distance = min(min_distance, distance)  score += min_distance  return score  # 分支界定法  
def find_motif_branch_bound(sequences, motif_length):  best_motif = None  best_score = float('inf')  def search(motif, depth):  nonlocal best_motif, best_score  if depth == motif_length:  score = calculate_score(motif, sequences)  if score < best_score:  best_score = score  best_motif = motif  return  for base in 'ACGT':  search(motif + base, depth + 1)  start_time = time.time()  search('', 0)  end_time = time.time()  return best_motif, end_time - start_time  # 遍歷法  
def find_motif_brute_force(sequences, motif_length):  best_motif = None  best_score = float('inf')  start_time = time.time()  for motif in itertools.product('ACGT', repeat=motif_length):  motif = ''.join(motif)  score = calculate_score(motif, sequences)  if score < best_score:  best_score = score  best_motif = motif  end_time = time.time()  return best_motif, end_time - start_time  # 示例序列集合和motif長(zhǎng)度  
sequences = ['ACGTAGCTAG', 'ACGGATCGTA', 'TAGCTAGCTA', 'TCGATCGATT']  
motif_length = 3  # 使用分支界定法尋找motif  
motif_bb, time_bb = find_motif_branch_bound(sequences, motif_length)  
print(f"Branch and Bound Motif: {motif_bb}, Time: {time_bb:.4f}s")  # 使用遍歷法尋找motif  
motif_bf, time_bf = find_motif_brute_force(sequences, motif_length)  
print(f"Brute Force Motif: {motif_bf}, Time: {time_bf:.4f}s")