ImageVerifierCode 换一换
格式:PPT , 页数:22 ,大小:346.50KB ,
资源ID:1267157      下载积分:10 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-1267157.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(病毒的DNA剖析一道字符匹配问题解析过程.PPT)为本站会员(国***)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

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

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个工作日内予以改正。