免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3928 | 回复: 7

[算法] DNA 对比问题求解 [复制链接]

论坛徽章:
0
发表于 2012-12-22 21:32 |显示全部楼层

    脱氧核糖核酸即常说的DNA,是一类带有遗传信息的生物大分子。它由4种主要的脱氧核苷酸(dAMP、dGMP、dCMT和dTMP)通过磷酸二酯键连接而成。这4种核苷酸可以分别记为:A、G、C、T。

    DNA携带的遗传信息可以用形如:AGGTCGACTCCA.... 的串来表示。DNA在转录复制的过程中可能会发生随机的偏差,这才最终造就了生物的多样性。

    为了简化问题,我们假设,DNA在复制的时候可能出现的偏差是(理论上,对每个碱基被复制时,都可能出现偏差):

  1. 漏掉某个脱氧核苷酸。例如把 AGGT 复制成为:AGT

    2. 错码,例如把 AGGT 复制成了:AGCT

    3. 重码,例如把 AGGT 复制成了:AAGGT


    如果某DNA串a,最少要经过 n 次出错,才能变为DNA串b,则称这两个DNA串的距离为 n。

    例如:AGGTCATATTCC 与 CGGTCATATTC 的距离为 2

    你的任务是:编写程序,找到两个DNA串的距离。


【输入、输出格式要求】

    用户先输入整数n(n<100),表示接下来有2n行数据。

    接下来输入的2n行每2行表示一组要比对的DNA。(每行数据长度<10000)

    程序则输出n行,表示这n组DNA的距离。

    例如:用户输入:
3
AGCTAAGGCCTT
AGCTAAGGCCT
AGCTAAGGCCTT
AGGCTAAGGCCTT
AGCTAAGGCCTT
AGCTTAAGGCTT

    则程序应输出:
1
1
2

论坛徽章:
3
寅虎
日期:2013-11-27 07:53:29申猴
日期:2014-09-12 09:24:152015年迎新春徽章
日期:2015-03-04 09:48:31
发表于 2012-12-23 13:43 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2012-12-23 17:26 |显示全部楼层
编辑距离问题,复杂度O(nm)

论坛徽章:
7
巳蛇
日期:2014-04-10 08:54:57白羊座
日期:2014-04-22 20:06:262015年亚洲杯之沙特阿拉伯
日期:2015-02-10 14:18:532015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之吉达阿赫利
日期:2015-06-02 11:34:112015亚冠之武里南联
日期:2015-06-24 12:13:082015亚冠之阿尔纳斯尔
日期:2015-08-03 09:08:25
发表于 2012-12-23 18:32 |显示全部楼层
Sevk 发表于 2012-12-23 13:43
好复杂,应该用脚本写:输出:

一般DNA复制出现每种错误的概率是不相同的,特别是插入/删除与变成其他碱基的概率是不一样的,你的脚本不但没有考虑这些因素,你自己也注释有很多情形略掉了,我可以保证你没考虑的情况比你注释的要多的多。

To 楼主,如果你想要最优解的话,这种问题一般是用动态规划算法来实现,先把每种突变打个分,写成打分矩阵的形式,然后进行动态规划比对,最后反推遗传距离,甚至可以反推出到底发生了怎样的突变。一般动态规划算法比较费时间和空间,我曾经用 C 语言和 Perl 语言都写过,Perl 版的处理十几个碱基的形式就得花不少时间,所以这种问题肯定是不能用脚本语言来做的。至于你想让速度和内存进一步优化的话,如果你不需要最优解,次优解也可以接受的话,有很多基于动态规划算法的启发式方法。

动态规划算法及相关次优解的算法在网上以及书本上有很多例子和解释。现成的比对软件有不少,而且很多比对软件都可以输出遗传距离的,因此我这里就不直接给你代码了,也没时间为你写这样的代码。不过,看你提的要求就知道你连用户接口部分的工作也想交给别人写,或许这个论坛里会有一两个好事之徒帮你写也说不定。Anyway,祝你好运了。

论坛徽章:
3
寅虎
日期:2013-11-27 07:53:29申猴
日期:2014-09-12 09:24:152015年迎新春徽章
日期:2015-03-04 09:48:31
发表于 2012-12-23 20:08 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
3
巳蛇
日期:2013-10-03 10:41:48申猴
日期:2014-07-29 16:12:04天蝎座
日期:2014-08-21 09:24:52
发表于 2012-12-23 20:18 |显示全部楼层
在pku acm上做过这道题。。

论坛徽章:
0
发表于 2012-12-23 22:13 |显示全部楼层
回复 4# Monox


    不是想将问题交给别人写     这不是什么任务    而是偶然遇到这个题     想了好久想不出思路   也找不到相关的解决方法


     就贴上来    看看大家有什么好的思路

论坛徽章:
0
发表于 2012-12-23 22:40 |显示全部楼层
去年竞赛做过这道题
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP