病毒的DNA剖析一道字符匹配问题解析过程.PPT

上传人:国*** 文档编号:1270513 上传时间:2019-01-25 格式:PPT 页数:22 大小:346.50KB
下载 相关 举报
病毒的DNA剖析一道字符匹配问题解析过程.PPT_第1页
第1页 / 共22页
病毒的DNA剖析一道字符匹配问题解析过程.PPT_第2页
第2页 / 共22页
病毒的DNA剖析一道字符匹配问题解析过程.PPT_第3页
第3页 / 共22页
病毒的DNA剖析一道字符匹配问题解析过程.PPT_第4页
第4页 / 共22页
病毒的DNA剖析一道字符匹配问题解析过程.PPT_第5页
第5页 / 共22页
点击查看更多>>
资源描述

1、 病毒的DNA剖析一道字符匹配问题解析过程长沙长郡中学 饶向荣题目描述有一 奇特的病毒, 的种 它 DNA序列是 的,而一般环状的生物的DNA都是 的,且由科 家 :生物被此 病毒线状 学 发现 种侵 的可能性 生物和病毒的袭 与 DNA序列最大公共 度有 ,由长 关于病毒是 的,所以 可以循 重 的匹配。科 家 大环状 它 环 复 学 们经过量的 :如果生物和病毒试验发现 DNA序列的最大公共部分的长度 有病毒的还没 DNA ,病毒是无法安身的,也就是 生长 说这个物被侵染的几率是0,否 ,最 公共部分的 度和被侵染的几则 长 长率 足下面的 系式:满 关生物被侵染几率=最大公共部分 度 长

2、 / 生物DNA 度。长任务在已知病毒的现 DNA序列和某生物的DNA序列, 必你 须求出此生物被侵染的几率是多少。题目描述数据范围病毒的DNA序列 度长 =1000,生物DNA序列 度长=105。样例病毒的DNA序列(环状)为abc,生物的DNA序列为abbcabcabb,那 的最 的公共 度么它们 长 长 为7,最 公共部分长 为色部分:红 bcabcab。分析和求解设A 病毒的为 环状DNA字串,A的 度长 为N。设B 生物的为 线状DNA字串,B的 度长 为M。那 目所求: 串么题 环 A和 串线 B的最大可循 公共环子串 度长 。 设f i, j 表示以 串线 B的第i位和 串环 A

3、的第j位 尾的最大公共子串的 度。结 长根据平 的解 ,很容易想到用 解此时 题经验 动态规划来 类求公共最大 度的 目,而且稍加分析就可 相 的长 题 设计 应 动态:规划分析和求解)1,1,max( njmijifAns 最后的答案:空 度间复杂 为O(N)。01,1,11,11,1,iBjAjiBjAnifnjiBjAjifjif 且且那 移方程:么动态转分析和求解分析,不必求出依次所有的经过 f i, j ,只有当Bi=Aj ,才有必要求时 f i, j,其余的f 全值 为0。又因为A,B中的字符只有a.z,A.Z,那么只需在 始 用 表开 时 链 记录a.z,A.Z出 的现位置, 的

4、 程中就可以 化。动态规划 过 实现这个优优化:时间复杂度:O(M*N)。n=1000, m=105。时间复杂度太高了!分析和求解很 找到在 度上有难 时间复杂 质的 的其 的 。飞跃 它 动态规划的 症 有解 :问题 结 没 决是否有其他的更 的 动态规划算法的时间复杂度还是没有降低。 问题转化只有最大公共子串的长度大于等于N时,才有必要计算这个长度。 a b cCac bA因 串的匹配 始位置是不 的, 一般的字符匹配为环 与是不 的。所以不 串问题 将环 A , 串断开 设为线 C。用到 一 动态规划 条 :如 用此 运 条 ,又可以 :此 上 一般字符转换 发现 题实际 较类匹配 ,不

5、 在于此 有 串 在 问题 题 环求解的变换如果最 公共部分 度大于 于长 长 N,那 此公共部分中 么 C中所有字符。)1,1max( MiiRiLAns 如果最大公共部分的 度 于长 N的, 可 出输 0。 只需 最大公共 度大于 于们 虑 长 N的 。况那 如果求出么 从B的第i位和C的第一位 后循 匹配的最大环度长 ,记为Ri。 abc abbcabcabbRiLi-1BiBi-1abbcabcabbbcabbcabbcabbc=52=C1Cn求出从B的第i-1位和C的最后一位 循 匹配的最大环 长度,记为Li-1。Ri的求解Ri的 求法 :为举B中位置i,和C 后匹配到不能匹配 , 匹为 显配的 度可 到长 达 M,那 此法的 度么 复杂 为O(M2),复杂度有增无减!必 不必要的匹配须 虑 :如果从I 始后currency1字 ,已匹配的 度已 到开 较时 长 经达N,那 就 有必要 后 ,必有么 没 较 Ri=Ri+n+n“。abbcabcabbi i+nRi Ri+nnabc abcabc

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 企业管理资料库 > 人力资源

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。