python - 使用 pyparsing Forward() 和多个规则来查找回文序列

Question

我正在尝试使用递归来查找 DNA 中的回文序列。我这样做是因为不可能知道 DNA 中回文序列的确切长度。我已经在脑海中和纸上解决了这个问题，但是下面的代码仍然没有给出我想要的答案。我是 pyparsing 和使用 CFG 的新手。因此，我设置代码的方式可能是错误的。欢迎任何帮助。

stem = Forward()
atRule = Word("A") + ZeroOrMore(stem) + Word("T")
taRule = Word("T") + ZeroOrMore(stem) + Word("A")
gcRule = Word("G") + ZeroOrMore(stem) + Word("C")
cgRule = Word("C") + ZeroOrMore(stem) + Word("G")
stem << locatedExpr(Combine(atRule + taRule + gcRule + cgRule))
print(stem.parseString("AAAGGGCCCTTTAAAGGGCCCTTT"))

Answer 1

我认为您对一些事情感到困惑。即便如此，我无法让任何解析器匹配最长的回文，我认为这是你的目标。

首先，Word("A") 匹配一个或多个 A。同样，Word("T") 匹配一个或多个 T。所以: AAAAT 将作为回文进行匹配。相反，让我们执行 Literal("A") + ... + Literal("T")

其次，ZeroOrMore(stem) 意味着您可以有多个内部回文。这将匹配:“A AT TA T”，这不是回文。相反，让我们做Optional(stem)。

第三，+ 运算符代表串联，而不是交替。 atRule + taRule + gcRule + cgRule 表示“AT 回文，后跟 TA 回文，后跟 GC 回文，后跟 CG 回文”。相反，让我们使用 |。

第四，你调用locateExpr，它必须比我的pyparsing副本更新。我已经包含了它，并且稍微改变了它的用法。

这是修改后的程序:

from pyparsing import *

def locatedExpr(expr):
    locator = Empty().setParseAction(lambda s,l,t: l)
    return Group(locator("locn_start") + expr("value") + locator.copy().leaveWhitespace()("locn_end"))

stem = Forward()
atRule = Literal("A") + Optional(stem) + Literal("T")
taRule = Literal("T") + Optional(stem) + Literal("A")
gcRule = Literal("G") + Optional(stem) + Literal("C")
cgRule = Literal("C") + Optional(stem) + Literal("G")
stem << Combine(atRule | taRule | gcRule | cgRule)
lstem = locatedExpr(stem)
print(lstem.parseString('AT'))
print(lstem.parseString('ATAT'))
print(lstem.parseString("AAAGGGCCCTTTAAAGGGCCCTTT"))

结果如下:

[[0, 'AT', 2]]
[[0, 'AT', 2]]
[[0, 'AAAGGGCCCTTT', 12]]

请注意，结果是最小的初始回文，而不是整个字符串。虽然我不认为这是您的目标，但我希望我的改变能让您更接近。

编辑:

如果您的目标是确定字符串是否为回文(与“在较大字符串中搜索回文”相比)，那么此程序可能更容易使用:

def DNA_complement(s):
    d = {'A':'T', 'T':'A', 'C':'G', 'G':'C'}
    return ''.join(d.get(ch,'') for ch in s)

def DNA_reversed_complement(s):
    return DNA_complement(reversed(s))

def DNA_palindrome(s):
    return s == DNA_reversed_complement(s)

print DNA_palindrome('AT')
print DNA_palindrome('ATAT')
print DNA_palindrome('AAAGGGCCCTTTAAAGGGCCCTTT')