4

我在我正在阅读的一篇论文中发现了一个粗略的字符串比较，如下所示：

他们使用的方程式如下（摘自论文，稍作改动以使其更通用和可读）由于作者的描述不是很清楚（使用示例），我试图用自己的话解释更多作者）

例如对于 2 个序列 ABCDE 和 BCEFA，有两个可能的图

图 1) 将 B 与 BC 与 C 和 E 与 E 连接起来

图 2) 将 A 与 A 连接起来

当我连接其他三个（图 1）时，我无法将 A 与 A 连接起来，因为那将是交叉线（想象你在 BB、CC 和 EE 之间画线）；也就是说，AA 上墨的线将穿过连接 BB、CC 和 EE 的线。所以这两个序列产生了两个可能的图；一个有 3 个连接（BB、CC 和 EE），另一个只有一个（AA），然后我计算分数 d，如下式所示。

因此，为了定义两个五弦之间的相似度，我们计算它们之间的距离 d。对齐两个五串，我们寻找它们字符之间的所有身份，无论这些身份可能位于何处。如果每个身份都由两个五字符串之间的链接表示，我们为这对定义一个图。我们将此图的任何部分称为配置。

接下来，我们保留所有没有字符交叉配对的配置（含义在我上面的示例中进行了解释，即相同字符之间没有交叉链接，只保留那些图形）。然后将这些中的每一个作为与图相关的字符数 p、相应对的移动 Δi 和每个五串的连接字符之间的间隙 δij 的函数进行评估。选择最小值作为特征，称为距离 d：d Min(50 – 10p + ΣΔi + Σδij) 虽然非常粗略，但该度量通常与定性眼睛引导估计非常吻合。例如，和之间的距离abcde是abcfg 20，而abcde和之间的距离abfcg是 23 =(50 – 30 + 1 +2)。

我对如何去做这件事感到困惑。任何可以帮助我的建议将不胜感激。

我尝试了 Levenshtein 以及蛋白质序列比较中使用的简单序列比对 论文的链接是： http: //peds.oxfordjournals.org/content/16/2/103.long

我找不到关于第一作者 Alain Figureau 的任何信息以及我给 MA Soto 的电子邮件尚未得到答复（截至今天）。

谢谢

4

2 回答 2

1

好吧，这绝对不是 Levenshtein：

>>> from nltk import metrics
>>> metrics.distance.edit_distance('abcde','abcfg')
2
>>> metrics.distance.edit_distance('abcde','abfcg')
3
>>> help(metrics.distance.edit_distance)
Help on function edit_distance in module nltk.metrics.distance:

edit_distance(s1, s2)
    Calculate the Levenshtein edit-distance between two strings.
    The edit distance is the number of characters that need to be
    substituted, inserted, or deleted, to transform s1 into s2.  For
    example, transforming "rain" to "shine" requires three steps,
    consisting of two substitutions and one insertion:
    "rain" -> "sain" -> "shin" -> "shine".  These operations could have
    been done in other orders, but at least three steps are needed.

    @param s1, s2: The strings to be analysed
    @type s1: C{string}
    @type s2: C{string}
    @rtype C{int}
于 2012-10-31T21:07:46.560 回答
1

在您引用的文本块之后，引用了同一作者以前的一篇论文：蛋白质的二级结构和三维模式识别。如果没有对距离的解释，我认为值得研究一下（我不在工作，所以我无法访问完整的文档）。

否则，您也可以尝试直接联系作者：Alain Figureau 似乎是一位老派的法国研究员，没有任何联系（没有网页，没有电子邮件，没有“社交网络”，..）所以我建议尝试联系 MA Soto，他的电子邮件在论文末尾给出。我想他们会给你你正在寻找的答案：实验的过程必须非常清楚才能重复，这是研究中科学方法的一部分。

于 2012-11-01T12:18:00.973 回答