Chinaunix

标题: DNA 对比问题求解 [打印本页]

作者: 1053304571 时间: 2012-12-22 21:32
标题: DNA 对比问题求解

脱氧核糖核酸即常说的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

作者: Sevk 时间: 2012-12-23 13:43
提示: 作者被禁止或删除内容自动屏蔽

作者: _Rayx 时间: 2012-12-23 17:26
编辑距离问题，复杂度O(nm)

作者: Monox 时间: 2012-12-23 18:32

Sevk 发表于 2012-12-23 13:43
好复杂,应该用脚本写:输出:

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

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

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

作者: Sevk 时间: 2012-12-23 20:08
提示: 作者被禁止或删除内容自动屏蔽

作者: pandaiam 时间: 2012-12-23 20:18
在pku acm上做过这道题。。

作者: 1053304571 时间: 2012-12-23 22:13
回复 4# Monox

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

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

作者: zwh8800 时间: 2012-12-23 22:40
去年竞赛做过这道题

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)