确定满足汉明距离矩阵的字符串

Question

确定满足汉明距离矩阵的字符串

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个字符串的汉明距离矩阵来说，手动操作是不切实际的。有没有人能建议一个可以做到这一点的算法？

谢谢，Chris

- ChrisUofR

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anne van Rossum · Accepted Answer

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

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

接下来要做的是逐对比较字符串。例如，如果您搜索[5 12 14]，您将发现表N包含5和12之间以及12和14之间的字符串。下一个挑战当然是找到电路，在该电路中可以将距离为5和12的字符串与距离为12和14的字符串结合在一起，使电路“闭合”。

％我们生成长度为len的n个字符串
n = 50;
len = 20;
％我们有一个大小为4（ABCD）的分类变量
cat = 4;
％我们想要生成与以下海明距离矩阵对应的字符串
search = [5 12 14];
％search=[10 12 14 14 14 16];
S = squareform(search);
％请注意，我们完全随机生成每个字符串。如果需要小距离，则引入跨字符串的相关性是有意义的
X = randi(cat-1, n, len);
％计算海明距离
t = pdist(X,'hamming') * len;
％我们必须在其中找到我们的小矩阵S的大矩阵
Y = squareform(t);
％如果存在submatrix（Y，S），则所有以下内容都可能被替换为这样的东西
R = zeros(size(S), size(Y));
for j = 1:size(S)
    M = zeros(size(Y), size(S));
    for i = 1:size(Y)
        M(i,:) = ismember(S(j,:), Y(i,:));
    endfor
    R(j,:) = all(M');
endfor

[x,y] = find(R);
％A将是包含将组成我们子矩阵的列/行的索引的单元格集合
A = accumarray(x,y,[], @(v) {sort(v).'});
％例如，如果根本不存在距离5，则我们可以直接退出
if (sum(cellfun(@isempty,A)) > 0)  
    printf("没有匹配项\n");
    return
endif
％我们现在要获取所有具有“search”中的值的可能子矩阵
C = cell(1, numel(A));
[C{:}] = ndgrid( A{:} );
N = cell2mat( cellfun(@(v)v(:), C, 'UniformOutput',false) );
N = unique(sort(N,2), 'rows');

printf("找到%i个潜在匹配项（但包含重复项）\n", size(N,1));
％我们现在进一步过滤（删除重复项）
[f,g] = mode(N,2);
h = g == 1;
N = N(h,:);

printf("找到%i个潜在匹配项\n", size(N,1));
M = zeros(size(N), size(search,2));
for i = 1:size(N) 
    f = N(i,:);
    M(i,:) = squareform(Y(f,f))';
endfor

F = squareform(S)';
％目前我们忘记了错误的排列，因此对于search>3，您需要过滤掉这些！
M = sort(M,2);
F = sort(F,2);
％从（大）表M中取出已排序的搜索字符串
％我们搜索“关闭”电路的那些
D = ismember(M,F,'rows');
mf = find(D);
if (mf) 
    matches = size(mf,1);
    printf("找到%i个匹配项\n", matches);  
    for i = 1:matches
        r = mf(i);
        printf("我们返回匹配项%i（仅检查排列现在）\n", r);
        t = N(r,:)';
        str = X(t,:);
        check = squareform(pdist(str,'hamming')*len);
        strings = char(str+64)
        check
    endfor
else
    printf("没有匹配项\n");
endif

它将生成类似以下的字符串：

ABAACCBCACABBABBAABA
ABACCCBCACBABAABACBA
CABBCBBBABCBBACAAACC