-2

我有一个简单的字符串和一个集合列表，其中每个集合是一个包含 2 个可能字符的位置，如下所示：

“AGTCG”

[('A', 'T'), ('C', 'B'), ('G', 'T'), ('T', 'X'), ... ]

我想在哪里找到最长的匹配。在本例中，它将是“TCG”。每组永远不会有超过 2 个字符。我想出的最佳解决方案是使用字符组合（ACGT...、ACGX...、ACTT...等）生成每个可能的字符串，然后使用 difflab SequenceMatcher.find_longest_match 并找到最大的结果. 我怀疑有更好的方法，但很难找到其他选择。有没有更好的办法？

4

1 回答 1

0

有点解决了。不是一个精确的解决方案，而是我更大目标的解决方案，它允许绕过这一步。目标是产生对齐，因此如果集合中每个位置只有一个字符，例如 ACGTACGT，则字符串“AGTCG”将尽可能对齐以产生 A-GT-CG-。经过反思，而不是在递归算法中寻找最大匹配，最好的方法是利用史密斯-沃特曼算法的修改版本。

https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm

于 2021-07-06T18:06:04.977 回答