1431-DNA基因鉴定


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:2 提交数:5 难度:2


题目描述:

我们经常会听说DNA亲子鉴定是怎么回事呢?人类的DNA4个基本字母{ACGT}构成,包含了多达30亿个字符。如果两个人的DNA序列相差0.1%,仍然意味着有300万个位置不同,所以我们通常看到的DNA亲子鉴定报告上结论有:相似度99.99%,不排除亲子关系。

怎么判断两个基因的相似度呢?生物学上给出了一种编辑距离的概念。

例如两个字符串FAMILYFRAME,有多种对齐方式:

F   -   A  M  I  L  Y    -   F  A  M  I   L  Y    -   F  A  M  I  L  Y

F   R  A  M  E          F   R  A  M  E           F   R  A  M  -  -  E

第一种对齐需要付出的代价:4,插入RI替换为E,删除L,Y

第二种对齐需要付出的代价:5,插入FF替换为RI替换为E,删除L,Y

第三种对齐需要付出的代价:5,插入FF替换为R,删除I, LY替换为E

编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。

怎么找到两个字符串x[1,…,m]y[1,…,n]的编辑距离呢?


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个字符串s1(0<字符串长度<1000)。
第2行,是一个字符串s2(0<字符串长度<1000)。

输出描述:

对于每一组输入,输出s1和s2的编辑距离。
每组的输出占一行。

样例输入:

2
family
frame
abcdefg
acehg

样例输出:

4
3

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!