我在用hadoop工作，我必须在java中对齐n个字符串，我想要一个在java中计算一般字符串（没有生物信息学、基因组等）的算法。锿。
ASFHASFHASDSAAPJEIHRA <-- seq1 AAPSOFHASFDSOISISN--A <-- seq2 AWP-JWRAIADSDIA--N--A <-- seq3 AOPSJD-A-JDSSDSOQOSSJ <-- seq4 100000000011000000000 <-- score
有人能帮我取个名字，图书馆什么的吗？
polkgigr1#
您可以编写自己的动态规划算法，但复杂度是：o（n^k），如果n是序列长度，k是序列数。假设你有k=2个序列：你有一个二维网格，网格中的每个点对应一对字符。所以位置（1，1）对应于word1[1]和word2[1]。此网格中的水平边和垂直边对应于插入和删除，而对角线边对应于匹配或不匹配。每一次你都要罚一次。在您的示例中，匹配=+1，而其他可能性为+0。当您到达网格的右下角时，您将获得最佳对齐分数。
1条答案
按热度按时间polkgigr1#
您可以编写自己的动态规划算法，但复杂度是：o（n^k），如果n是序列长度，k是序列数。假设你有k=2个序列：你有一个二维网格，网格中的每个点对应一对字符。所以位置（1，1）对应于word1[1]和word2[1]。此网格中的水平边和垂直边对应于插入和删除，而对角线边对应于匹配或不匹配。每一次你都要罚一次。在您的示例中，匹配=+1，而其他可能性为+0。当您到达网格的右下角时，您将获得最佳对齐分数。