1

我在 hadoop 中工作，我必须在 java 中对齐 n 个字符串，我想要一个在 Java 中计算一般字符串（没有生物信息学、基因组等）的算法。埃斯。

ASFHASFHASDSAAPJEIHRA <-- seq1
AAPSOFHASFDSOISISN--A <-- seq2
AWP-JWRAIADSDIA--N--A <-- seq3
AOPSJD-A-JDSSDSOQOSSJ <-- seq4
100000000011000000000 <-- score

有人可以帮我取个名字，图书馆什么的吗？

4

1 回答 1

0

您可以编写自己的动态编程算法，但复杂度为： O(N^k) 如果 N 是序列长度，k 是序列数。假设您有 k=2 序列：您有一个 2D 网格，其中网格中的每个点对应于一对字符。所以位置 (1,1) 对应 word1[1] 和 word2[1]。该网格中的水平和垂直边缘对应于插入和删除，而对角线对应于匹配或不匹配。对于每一个，你必须装置一个惩罚。在您的示例中，匹配 = +1，而其他可能性为 +0。当您到达网格的右下角时，您将获得最佳对齐分数。

于 2013-07-18T12:29:55.063 回答