基于动态规划算法的DNA序列比对函数,给出两条序列(v和w)的打分矩阵

2024-05-24 11:36

本文主要是介绍基于动态规划算法的DNA序列比对函数,给出两条序列(v和w)的打分矩阵,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.什么是动态规划算法

1.1总体思想

·动态规划算法与分治法类似,基本思想也是将待求解的问题分成若干个子问题

·经过分解得到的子问题往往不是互相独立的,有些子问题被重复计算多次

·如果能够保存已解决的子问题答案,在需要时再找出来已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法(备忘录)

1.2使用动态规划求解的问题需要具备的基本要素

1)重复子问题

·递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次,这种性质被称为子问题的重叠性质

·动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。

·通常不同的子问题个数随问题的大小呈多项式增长,用动态规划算法只需要多项式时间,从而获得较高的解题效率。

2)最优子结构

·一个问题的最优解包含着其子问题的最优解,这种性质称为最优子结构性质

·分析问题的最优子结构性质,首先假设由问题的最优解导出的子问题的解不是最优,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾

·利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解

·最优子结构是一个问题能用动态规划算法求解的前提

1.3动态规划求解的基本步骤

1)找出最优解的性质,并刻画其结构特征

2)递归地定义最优质

3)以自底向上的方式计算出最优值

4)根据计算最优值时得到的信息,构造最优解

二.打分矩阵代码

import random  # 1. 生成一个指定长度的随机DNA序列  
def generate_dna(length):  dna_bases = 'ACGT'  # DNA的四个碱基  sequence = ''  # 初始化空序列  for _ in range(length):  # 循环length次  sequence += random.choice(dna_bases)  # 每次从四个碱基中随机选一个添加到序列中  return sequence  # 返回生成的DNA序列  # 2. 在DNA序列中随机位置插入一个可能突变的motif  
def insert_motif(dna, motif, mutation_rate):  mutated_motif = ''  # 初始化突变的motif为空字符串  for base in motif:  # 遍历motif中的每个碱基  if random.random() < mutation_rate:  # 如果随机数小于突变率  mutated_motif += random.choice('ACGT')  # 则该位置碱基随机突变  else:  mutated_motif += base  # 否则保持原样  insert_point = random.randint(0, len(dna))  # 在DNA序列中随机选择一个插入点  return dna[:insert_point] + mutated_motif + dna[insert_point:]  # 插入突变的motif  # 3. 生成多条带有随机插入motif的DNA序列  
def generate_sequences(num_sequences, dna_length, motif_length, mutation_rate):  sequences = []  # 初始化一个空列表来存储生成的序列  motif = generate_dna(motif_length)  # 生成一个随机的motif  for _ in range(num_sequences):  # 循环生成指定数量的序列  dna = generate_dna(dna_length)  # 生成一个DNA序列  dna_with_motif = insert_motif(dna, motif, mutation_rate)  # 插入motif  sequences.append(dna_with_motif)  # 将序列添加到列表中  return sequences  # 返回生成的序列列表  # 使用函数生成序列并打印  
sequences = generate_sequences(5, 20, 5, 0.1)  
for seq in sequences:  print(seq)

三.编写一个函数,生成m条DNA序列,每条序列长度为k,然后对每条序列随机插入一个长度为L的motif,motif的突变率为n

import random  # 1. 生成一个指定长度的随机DNA序列  
def generate_dna(length):  dna_bases = 'ACGT'  # DNA的四个碱基  sequence = ''  # 初始化空序列  for _ in range(length):  # 循环length次  sequence += random.choice(dna_bases)  # 每次从四个碱基中随机选一个添加到序列中  return sequence  # 返回生成的DNA序列  # 2. 在DNA序列中随机位置插入一个可能突变的motif  
def insert_motif(dna, motif, mutation_rate):  mutated_motif = ''  # 初始化突变的motif为空字符串  for base in motif:  # 遍历motif中的每个碱基  if random.random() < mutation_rate:  # 如果随机数小于突变率  mutated_motif += random.choice('ACGT')  # 则该位置碱基随机突变  else:  mutated_motif += base  # 否则保持原样  insert_point = random.randint(0, len(dna))  # 在DNA序列中随机选择一个插入点  return dna[:insert_point] + mutated_motif + dna[insert_point:]  # 插入突变的motif  # 3. 生成多条带有随机插入motif的DNA序列  
def generate_sequences(num_sequences, dna_length, motif_length, mutation_rate):  sequences = []  # 初始化一个空列表来存储生成的序列  motif = generate_dna(motif_length)  # 生成一个随机的motif  for _ in range(num_sequences):  # 循环生成指定数量的序列  dna = generate_dna(dna_length)  # 生成一个DNA序列  dna_with_motif = insert_motif(dna, motif, mutation_rate)  # 插入motif  sequences.append(dna_with_motif)  # 将序列添加到列表中  return sequences  # 返回生成的序列列表  # 使用函数生成序列并打印  
sequences = generate_sequences(5, 20, 5, 0.1)  
for seq in sequences:  print(seq)

四.对生成的已插入突变motif的序列集合,编写一套函数,寻找其中的motif,可指定motif长度;

# 定义一个名为 find 的函数,它接受两个参数:  
# sequence_set 是一个包含多个 DNA 序列的列表  
# motif_length 是我们想要查找的子序列(也称为 motif)的长度  
def find(sequence_set, motif_length):    # 初始化一个空集合 motifs,用于存储找到的所有唯一的 motif  motifs = set()    # 遍历 sequence_set 中的每一条序列  for sequence in sequence_set:    # 对于每一条序列,我们从其第一个碱基开始,直到剩下的碱基数量少于 motif_length 为止  # 这样确保我们可以从序列中提取出完整长度的 motif  for i in range(len(sequence) - motif_length + 1):    # 从当前位置 i 开始,提取长度为 motif_length 的子序列  motif = sequence[i:i+motif_length]    # 将提取到的 motif 添加到 motifs 集合中  # 由于 motifs 是一个集合,所以重复的 motif 会被自动去除  motifs.add(motif)    # 函数返回包含所有唯一 motif 的集合  return motifs    # 测试数据:一个包含三条 DNA 序列的列表和一个 motif 长度值  
sequence_set = ['ACGTTAGC', 'GTATCGAG', 'CGTACGTA']    
motif_length = 4    # 调用 find 函数,传入测试数据,并将返回的结果存储在变量 motifs 中  
motifs = find(sequence_set, motif_length)    
# 打印出找到的所有唯一 motif  
print(motifs)

五.对生成的已插入突变motif的序列集合,编写一套函数,基于分支界定法寻找指定长度的motif,并与遍历法比较计算效率

import itertools  
import time  # 计算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长度  
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")

这篇关于基于动态规划算法的DNA序列比对函数,给出两条序列(v和w)的打分矩阵的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/998294

相关文章

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序