计算DNA序列
答
这里是the Wikipedia page on Levenshtein distances算法：
int LevenshteinDistance(char s[1..m], char t[1..n])
{
// d is a table with m+1 rows and n+1 columns
declare int d[0..m, 0..n]
for i from 0 to m
d[i, 0] := i // deletion
for j from 0 to n
d[0, j] := j // insertion
for j from 1 to n
{
for i from 1 to m
{
if s[i] = t[j] then
d[i, j] := d[i-1, j-1]
else
d[i, j] := minimum
(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + 1 // substitution
)
}
}
return d[m, n]
}
（我敢肯定，你可以让Java出来，随着一点点的工作。）
通在你的两个DNA序列s和t它会返回一个int的距离。从Levenshtein Distance Algorithm
答
复制/粘贴功能，并使用它像这样：
String a = "AAAAAAAAAAAAAAAAAA";
String b = "AAAAAAAAACTAAAAAAA";
int d = getLevenshteinDistance(a,b);
System.out.println(d);
答
如果您是计算两个DNA序列之间的差异只是有兴趣，你应该使用Damerau–Levenshtein distance不是正规的Levenshtein距离。
维基百科条目包含一些示例代码，您当然可以映射到java代码。
答
我相信这是你所追求的。如果您愿意，您可以删除System.out.println声明。请注意，如果将它们留在中，则第一行和第一列在打印的内容中被省略。
对照results on the wikipedia page进行验证。
public int getLevenshteinDistance(String a, String b)
{
// d is a table with m+1 rows and n+1 columns
char[] s = (a).toCharArray();
char[] t = (b).toCharArray();
System.out.println(a + " - " + b);
int m = s.length;
int n = t.length;
int[][] d = new int[m + 1][n + 1];
int i;
int j;
for(i = 0; i < (m + 1); i++)
{
d[i][0] = i; //deletion
}
for(j = 0; j < (n + 1); j++)
{
d[0][j] = j; //insertion
}
for (j = 1; j < (n + 1); j++)
{
for (i = 1; i < (m + 1); i++)
{
if (s[i-1] == t[j-1])
{
d[i][j] = d[i-1][j-1];
}
else
{
d[i][j] = Math.min((d[i-1][j] + 1), //deletion
(Math.min((d[i][j-1] + 1), //insertion
(d[i-1][j-1] + 1)))); //substitution
}
System.out.print(" [" + d[i][j] + "]");
}
System.out.println("");
}
return d[m][n];
}
测试：
String a = "Saturday";
String b = "Sunday";
int d = getLevenshteinDistance(a, b);
System.out.println(d);
a = "kitten";
b = "sitting";
d = getLevenshteinDistance(a, b);
System.out.println(d);
需要更多信息请。你想解决什么问题？ – 2009-11-16 05:21:19
作为首次使用的用户，查看这里发布的一些关于整体样式的问题可能很有用，并阅读http://stackoverflow.com/faq上的常见问题解答。 – 2009-11-16 05:22:54