DNA比对

【编程题】(满分27分)

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <string>
 8 #include <vector>
 9 #include <set>
10 #include <stack>
11 #include <queue>
12 #include <map>
13 #include <ctime>
14 #include <iomanip>
15 using namespace std;
16 const int INF=0x7ffffff;
17 const double EXP=1e-8;
18 const int MS=10005;
19 typedef long long LL;
20 int dp[MS][MS];
21
22 int minv(int a,int b,int c)
23 {
24     return a>b?(b>c?c:b):(a>c?c:a);    //  min(a,min(b,c))
25 }
26 /*
27 ACT
28 ACTT        dp[i][j]=dp[i][j-1]+1;
29
30
31 ACTT
32 ACT        dp[i][j]=dp[i-1][j]+1    丢失等效于增加
33
34
35 ACT
36 ACG      dp[i][j]=d[i-1][j-1]+1
37
38 */
39
40
41
42
43 void solve(string &s1,string &s2)
44 {
45     int len1=s1.length();
46     int len2=s2.length();
47     for(int i=0;i<=len1;i++)
48         dp[i][0]=i;
49     for(int i=0;i<=len2;i++)
50         dp[0][i]=i;
51     for(int i=1;i<=len1;i++)
52     {
53         for(int j=1;j<=len2;j++)
54         {
55             if(s1[i-1]==s2[j-1])
56                 dp[i][j]=dp[i-1][j-1];
57             else
58             {                //  增加         减少          修改
59                 dp[i][j]=minv(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1);
60             }
61         }
62     }
63     cout<<dp[len1][len2]<<endl;
64     return ;
65 }
66
67 int main()
68 {
69     int n;
70     string str1,str2;
71     cin>>n;
72     while(n--)
73     {
74         cin>>str1>>str2;
75         solve(str1,str2);
76     }
77     return 0;
78 }
时间: 02-16

DNA比对的相关文章

UVA - 1368 DNA Consensus String

DNA Consensus String Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description  Figure 1. DNA (Deoxyribonucleic Acid) is the molecule which contains the genetic instructions. It consists of four different nuc

[LeetCode]Repeated DNA Sequences

题目:Repeated DNA Sequences 给定包含A.C.G.T四个字符的字符串找出其中十个字符的重复子串. 思路: 首先,string中只有ACGT四个字符,因此可以将string看成是1,3,7,20这三个数字的组合串: 并且可以发现{ACGT}%5={1,3,2,0};于是可以用两个位就能表示上面的四个字符: 同时,一个子序列有10个字符,一共需要20bit,即int型数据类型就能表示一个子序列: 这样可以使用计数排序的思想来统计重复子序列: 这个思路时间复杂度只有O(n),但是

POJ2778 DNA Sequence Trie+矩阵乘法

题意:给定N个有A C G T组成的字符串,求长度为L的仅由A C G T组成的字符串中有多少个是不含给定的N个字符串的题解: 首先我们把所有的模式串(给定的DNA序列)建Trie,假定我们有一个匹配串,并且在匹配过程到S[i]这个字符时匹配到了Trie上的某个节点t,那么有两种可能: 匹配失败:t->child[S[i]]为空,跳转到t->fail,因此t->fail一定不能是某个模式串的结尾: 匹配成功:跳转到t->child[S[i+1]],因此t->child[S[i

CodeForces 520C DNA Alignment

题意: 一段DNA序列(10^5长度)  定义h函数为两序列相同碱基个数  p函数为分别移动两个DNA序列后所有可能的h函数之和  问使p最大的序列有多少个 思路: 根据p函数的定义  我们发现p这个函数其实就是A序列每个碱基和B序列每个碱基比较再乘一个n 因此可以贪心构造B序列  即每次新加一个碱基必定是A序列中出现次数最多的碱基 那么最后的答案就是A序列中出现次数最多的碱基种类数的n次方 代码: #include<cstdio> #include<iostream> #incl

HDU - 1560 DNA sequence

给你最多8个长度不超过5的DNA系列,求一个包含所有系列的最短系列. 迭代加深的经典题.(虽然自己第一次写) 定一个长度搜下去,搜不出答案就加深大搜的限制,然后中间加一些玄学的减枝 //Twenty #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<

DNA Pairing

DNA 链缺少配对的碱基.依据每一个碱基,为其找到配对的碱基,然后将结果作为第二个数组返回. Base pairs(碱基对) 是一对 AT 和 CG,为给定的字母匹配缺失的碱基. 在每一个数组中将给定的字母作为第一个碱基返回. 例如,对于输入的 GCG,相应地返回 [["G", "C"], ["C","G"],["G", "C"]] 字母和与之配对的字母在一个数组内,然后所有数组再被组织

如何使用3D MAX建造出DNA双螺旋结构

首先,在基本上掌握了DNA双螺旋结构以及3DMAX的简单的使用方法之后,我们便可以建造DNA双螺旋结构了. 在 3DMAX中利用基本标准形状来建造单个碱基配对的情况,即利用基本形状中的球体和圆柱体来构造两颗求和圆柱连接在一起,调整好自己想要的形状即可.之后,先调整一下轴,也就是选中索要调整轴心的对象,然后点击层次那个按钮,之后点击仅影响轴,在对象上可以移动到自己想要的轴心的位置.(提示,如果想要精确的移动轴心的话,可以打开捕捉,然后点击右键,点击轴心,就可以轻松地捕捉轴心的位置了).然后选中所要

HBV DNA level _data analysis

HBV 表明抗原阳性是HCC最重要风险因子 Seropositivity for the hepatitis B surface antigen (HBsAg) is one of the most important risk factors for hepatocellular carcinoma hbv e 抗原阳性会增加HCC风险 In our previous study, seropositivity for the hepatitis B e antigen (HBeAg) was

Share data between VSTO and Excel DNA App domains

Is there a way to share data between a VSTO add in and an Excel DNA add in? Or can the Excel DNA add in be loaded into the VSTO's app domain? The Excel-DNA add-in will always be in a separate AppDomain. You might try to pass an object via the AddIn's

ThoughtWorks 2016年第1期DNA活动总结

今天受邀参加了2016年ThoughtWorks公司成都分公司的2016年第一期DNA活动. 什么是DNA? DNA 即 Design And Analysis.设计与分析.这个活动主要是针对产品经理的,我一个码农也去参加了,多多少少还是有一些收获. ThoughtWorks这家公司给我的印象是很不错的,没参加该活动之前也对这家公司有一定的了解,公司的氛围也是很不错的.美女很多哈,据说该公司招聘比较均衡,男女比例近乎1:1,对码农是多么幸福的事情. 好了,废话不多说了.先看看我画的一张图,第一次