核心问题是:
我正在寻找一种算法来计算一组字符串之间的最大简约距离.对于距离,我的意思是类似于Damerau-Levenshtein距离,即字符或相邻字符块的删除,插入,替换和转置的最小数量.但是我不想使用常规字符串来调查带有方向字符的字符串.
因此,字符串可能如下所示:
(A,1) (B,1) (C,1) (D,1)可能的衍生物可能是:
(A,1) (C,0) (B,0) (D,1)(A,1) (C,1) (B,1) (D,1)(A,1) (B,0) (C,0) (D,1)A,B,C,D字符身份在哪里1 = forward和0 = reverse.
这里,导数1.将具有距离2,因为你可以切出块BC并重新粘贴它(1切,1贴).衍生物2.也会有2个,因为你可以剪掉C并重新粘贴在B前面(1个剪切,1个粘贴),而数字3则需要4个操作(2个剪切,2个粘贴)进行转换.类似,删除或插入块将产生距离1.
如果要为所有可能的X 定义(X,0)和(X,1)作为两个不同的非面向字符(X0, X1),示例3.将导致距离为2,因为您可以切出块B1C1并B0C0分两步插入块.
一个现实世界的例子:
细菌基因组中的基因可以被认为是定向特征(A,0),(B,0)......通过确定序列距离,两个相关细菌中同源基因的基因组方向可以用作进化标记迹线.细菌基因组是圆形字符串的事实引入了额外的边界条件ABC等于BCA.
真正的基因组确实具有独特的基因,在伴侣中没有相应的基因,从而产生了一个占位符字符@.这些占位符将比较的信息内容减少到下限,因为例如(A,1)(B,1)@(C,1)可以转换为(A,1)@@@(B,1) @(C,1)通过插入块@@@.然而,方向部分恢复信息内容,因为您可能会发现(A,1)@@@(B,0)@(C,1)表示最小距离为3.更好的是比较多个相关序列的算法(同时,因为你可以在进化历史中找到中间体,从而提高分辨率.
我意识到,在文本字符串比较中已经发布了几个问题.但它们无法轻易扩展以包括方向.此外,存在大量处理生物序列的方法,特别是用于多序列分析.然而,它们仅限于在交替方向上不存在的大分子序列,并且通常为任何特定的字符匹配调用特定的权重.
如果已经有一个python库可以进行必要的自定义来解决这个问题,那就太棒了.但任何合适的方向感知算法都会非常有用.