5

我正在使用 difflib 来识别较长序列中短字符串的所有匹配项。然而，当有多个匹配时，difflib 似乎只返回一个：

> sm = difflib.SequenceMatcher(None, a='ACT', b='ACTGACT')
> sm.get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=3, b=7, size=0)]

我期望的输出是：

[Match(a=0, b=0, size=3), Match(a=0, b=4, size=3), Match(a=3, b=7, size=0)]

事实上，字符串 ACTGACT 包含两个匹配的 ACT，分别位于位置 0 和 4，大小均为 3（加上字符串末尾的另一个大小为 0 的匹配）。

如何获得多个匹配项？我期待 difflib 返回两个位置。

4

2 回答 2

2

你为什么要使用difflib它？您应该能够只使用标准的正则表达式。

import re
pattern = "ACT"
text = "ACTGACT"
matches = [m.span() for m in re.finditer(pattern, text)]

这会给你：

[(0, 3), (4, 7)]

或者这是否出于某种原因不包括您感兴趣的信息？它当然不会返回 difflib 返回的最后一个空匹配，但您可以轻松地创建它。

于 2015-02-27T13:02:04.560 回答
2

正如 Jerry 指出的那样，并且 k-nut 正确回答，您正在为您的问题使用错误的算法。老实说，k-nut 的答案并没有那么糟糕，但这并不是解决此类问题的最有效方法。我是一名生物信息学家，鉴于您的问题和示例案例，您似乎非常想解决“我们的”经典 DNA 序列比对/搜索问题（请参阅Altschul 或“Gene”Myers 等科学巨星的科学文献如果您对细节感兴趣并想阅读有史以来被引用次数最多的论文之一，请在这个问题上讨论）。

有效地在长段数据库中查找短段正是 Altschul 现在著名的BLAST算法启发式解决的方法和/或可以使用Smith-Waterman进行精确查找。在 Python 中执行此操作的最有效方法可能是使用BioPython，特别是，您可能希望查看描述如何设置本地 NCBI BLAST+ 实例的部分。如果您没有“嫁给” Python，那么今天有更快的 BLAST 实现，例如FSA-BLAST。

另一方面，如果您需要完全匹配（与 BLAST 的启发式方法相反），如果您不介意较长的查询时间并且有一个小的参考序列（B在您的示例中），则可能是这种情况，您可以去与官方的 Smith-Waterman (SW) 对齐。如果没有，并且您仍然需要精确匹配，请首先使用 BLAST 过滤匹配，然后使用候选的 SW 对齐减少您的集合。

您可以在纯 Python 中实现 SW，甚至只使用任何现有的纯 Python 实现，但我只推荐该路径用于纯粹的教育目的（例如，查看GitHub 上的swalign）。如果您仍然想要一个相当强大的基于 Python 的实现，请查看scikit-bio的 SW 对齐，尽管 scikit-bio 仍处于 alpha 状态。但首先阅读上面已经链接的SW WikiPedia 页面，根据您拥有的硬件，您可能会改用CUDA或C++中的 GPU 或至少 SIMD 优化的实现。如果您想要一个带有 Python 包装器的好版本，请查看SSWlib。

于 2015-03-06T10:08:39.283 回答