当前位置: 首页 > news >正文

Python-77:古生物DNA序列血缘分析

问题描述

小U是一位古生物学家,正在研究不同物种之间的血缘关系。为了分析两种古生物的血缘远近,她需要比较它们的DNA序列。DNA由四种核苷酸A、C、G、T组成,并且可能通过三种方式发生变异:添加一个核苷酸、删除一个核苷酸或替换一个核苷酸。小U认为两条DNA序列之间的最小变异次数可以反映它们之间的血缘关系:变异次数越少,血缘关系越近。

你的任务是编写一个算法,帮助小U计算两条DNA序列之间所需的最小变异次数。

  • dna1: 第一条DNA序列。
  • dna2: 第二条DNA序列。

代码

def solution(dna1, dna2):

    # Please write your code here

    n = len(dna1)

    m = len(dna2)

    if n * m == 0:

        return n + m

    f = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):

        f[i][0] = i

    for j in range(m + 1):

        f[0][j] = j

    for i in range(1, n + 1):

        for j in range(1, m + 1):

            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + (dna1[i - 1] != dna2[j - 1]))

    return f[n][m]

if __name__ == "__main__":

    #  You can add more test cases here

    print(solution("AGT", "AGCT") == 1)

    print(solution("", "ACGT") == 4)

    print(solution("GCTAGCAT", "ACGT") == 5)

http://www.xdnf.cn/news/378217.html

相关文章:

  • 网络世界的“快递站”:深入浅出OSI七层模型
  • Python 包管理新选择:uv
  • 便签软件哪个好用?2025年桌面记事本便签软件推荐大全
  • 【ospf综合实验】
  • ffmpeg 写入avpacket时候,即av_interleaved_write_frame方法是如何不需要 业务层释放avpacket的 逻辑分析
  • 【LeetCode 热题 100】206. 反转链表
  • 洛谷P7528 [USACO21OPEN] Portals G
  • Android开发-Activity启停
  • Halcon之计算抓取螺母的位姿
  • 《Python星球日记》 第54天:卷积神经网络进阶
  • Python 核心概念速查清单
  • LeetCode --- 448 周赛
  • Java Bean容器详解:核心功能与最佳使用实践
  • 自动泊车技术—相机模型
  • OSPF综合实验报告
  • SpringCloud之Ribbon基础认识-服务负载均衡
  • vue3 无缝列表循环
  • 深圳SMT贴片加工厂制造流程解析
  • PaddleOCR本地部署
  • 【Linux系统调试】内存错误检测工具AddressSanitizer (ASan)
  • 基于协同过滤的音乐推荐系统(源码+lw+部署文档+讲解),源码可白嫖!
  • Duplicati:一款跨平台的备份客户端,支持加密、增量、压缩的备份存储在云存储服务和远程文件服务器
  • VBA即用型代码手册:字体Font与插入Insert
  • 卡尔曼滤波算法简介与 Kotlin 实现
  • en_text_100_words
  • leetcode504.七进制数
  • 联邦学习图像分类实战:基于FATE与PyTorch的隐私保护机器学习系统构建指南
  • cadence -- allegro汉化
  • UE5 PCG学习笔记
  • C++笔记-set和map的使用(包含multiset和multimap的讲解)