3

我正在尝试从汉明距离矩阵创建字符串列表。每个字符串的长度必须为 20 个字符，包含 4 个字母（A、B、C、D）。例如，假设我有以下汉明距离矩阵：

   S1 S2 S3
S1  0  5 12
S2  5  0 14
S3 12 14  0

从这个矩阵我需要创建 3 个字符串，例如：

S1 = "ABBBBAAAAAAAAAABBBBB"
S2 = "BAAAAAAAAAAAAAABBBBB"
S3 = "CBBBABBBBBBBBBBBBBBB"

我手动创建了这些字符串，但我需要为代表 100 个字符串的汉明距离矩阵执行此操作，手动执行此操作不切实际。谁能建议一种可以做到这一点的算法？

谢谢，克里斯

4

1 回答 1

1

这是一个有趣的练习。:-)

以下octave脚本随机生成n长度字符串len。随后，它计算所有这些字符串之间的汉明距离。

接下来要做的是成对比较字符串。例如，如果您搜索[5 12 14]，您会发现该表N包含相距5和相距的字符串以及相距和12相距的字符串。下一个挑战当然是找到一个电路，在该电路中，可以将那些存在和分开的部分与那些存在和分开的部分放在一起，从而使电路“闭合”。12145121214

% 我们生成 n 个长度为 len 的字符串
n=50；
长度=20；

% 我们有一个大小为 4 (ABCD) 的分类变量
猫=4；

% 我们要生成与以下汉明距离矩阵对应的字符串
搜索=[5 12 14]；
%搜索=[10 12 14 14 14 16];
S=方形（搜索）；

% 请注意，我们生成的每个字符串都是完全随机的。如果您需要小距离，那么引入
% 字符串之间的相关性
X=兰迪(cat-1,n,len);

% 计算汉明距离
t=pdist(X,'汉明')*len;

% 我们必须在其中找到我们的小矩阵 S 的大矩阵
Y=正方形（t）；

% 如果存在的话，以下所有内容都可能被 submatrix(Y,S) 之类的东西替换
R=零（大小（S），大小（Y））；
对于 j = 1：大小（S）
    M=零（大小（Y），大小（S））；
    对于 i = 1：大小（Y）
        M(i,:)=ismember(S(j,:),Y(i,:));
    结束
    R(j,:)=全部(M')；
结束

[x,y]=查找（R）；

% A 将是一组单元格，其中包含构成我们的子矩阵的列/行的索引
A = accumarray(x,y,[], @(v) {sort(v).'});

% 例如，如果距离 5 根本没有出现，我们已经可以退出
if (sum(cellfun(@isempty,A)) > 0)  
    printf("没有匹配项\n");
    返回
万一

% 我们现在将获得所有可能的子矩阵，其中包含“搜索”中的值
C = 单元格（1，数字（A））；
[C{:}] = ndgrid(A{:});

N = cell2mat( cellfun(@(v)v(:), C, 'UniformOutput',false) );
N = 唯一（排序（N，2），“行”）；

printf("找到 %i 个潜在匹配项（但包含重复项）\n", size(N,1));

% 我们现在正在进一步过滤（删除重复项）
[f,g]=模式(N,2);
h=g==1；
N=N(h,:);

printf("找到 %i 个潜在匹配\n", size(N,1));

M=零（大小（N），大小（搜索，2））；
对于 i = 1：大小（N）
    f=N(i,:);
    M(i,:)=正方形(Y(f,f))';
结束

F=正方形（S）'；

% 现在我们忘记了错误的排列，所以对于搜索 > 3 你需要过滤掉这些！
M = 排序(M,2);
F = 排序(F,2);

% 从（大）表 M 中取出排序后的搜索字符串
% 我们搜索那些“关闭”电路的
D=ismember(M,F,'rows');
mf=查找（D）；

如果 (mf)
    匹配=大小（mf，1）；
    printf("找到 %i 个匹配项\n", 匹配项);  
    对于 i = 1：匹配
        r=mf(i);
        printf("我们返回匹配 %i (现在只检查排列)\n", r);
        t=N(r,:)';
        str=X(t,:);
        check=squareform(pdist(str,'hamming')*len);
        字符串=字符（str+64）
        查看
    结束
别的
    printf("没有匹配项\n");
万一

它将生成字符串，例如：

ABAACCBCACABBABBAABA
ABACCCBCACBABAABACBA
CABBCBBBABCBBACAAACC
于 2014-12-13T16:54:00.310 回答