確定滿足海明距離矩陣的字符串

Question

我正在嘗試從漢明距離矩陣創建一個字符串列表。每個字符串必須是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個絃線的漢明距離矩陣來說是不切實際的，以手動進行。任何人都可以提出一個算法可以做到這一點？

謝謝，克里斯

Answer 1

這是一個有趣的練習。 :-)

以下octave腳本隨機產生n字符串的長度爲len。隨後它計算所有這些字符串之間的海明距離。

接下來要做的是字符串是兩兩比較的。例如，如果您搜索[5 12 14]，則會發現表N包含5和12之間的字符串，以及12和14分開的字符串。接下來的挑戰當然是找到其中相隔5和12的電路可以與12和14分開的電路放在一起，以使電路「閉合」。

 
% We generate n strings of length len 
n=50; 
len=20; 

% We have a categorical variable of size 4 (ABCD) 
cat=4; 

% We want to generate strings that correspond with the following hamming distance matrix 
search=[5 12 14]; 
%search=[10 12 14 14 14 16]; 
S=squareform(search); 

% Note that we generate each string totally random. If you need small distances it makes sense to introduce 
% correlations across the strings 
X=randi(cat-1,n,len); 

% Calculate the hamming distances 
t=pdist(X,'hamming')*len; 

% The big matrix we have to find our little matrix S within 
Y=squareform(t); 

% All the following might be replaced by something like submatrix(Y,S) if that would exist 
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 will be a set of cells that contains the indices of the columns/rows that will make up our submatrices 
A = accumarray(x,y,[], @(v) {sort(v).'}); 

% If for example the distance 5 doesn't occur at all, we can already drop out 
if (sum(cellfun(@isempty,A)) > 0) 
    printf("There are no matches\n"); 
    return 
endif 

% We are now gonna get all possible submatrices with the values in "search" 
C = cell(1, numel(A)); 
[C{:}] = ndgrid(A{:}); 

N = cell2mat(cellfun(@(v)v(:), C, 'UniformOutput',false)); 
N = unique(sort(N,2), 'rows'); 

printf("Found %i potential matches (but contains duplicates)\n", size(N,1)); 

% We are now further filtering (remove duplicates) 
[f,g]=mode(N,2); 
h=g==1; 
N=N(h,:); 

printf("Found %i potential matches\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)'; 

% For now we forget about wrong permutations, so for search > 3 you need to filter these out! 
M = sort(M,2); 
F = sort(F,2); 

% Get the sorted search string out of the (large) table M 
% We search for the ones that "close" the circuit 
D=ismember(M,F,'rows'); 
mf=find(D); 

if (mf) 
    matches=size(mf,1); 
    printf("Found %i matches\n", matches); 
    for i = 1:matches 
     r=mf(i); 
     printf("We return match %i (only check permutations now)\n", r); 
     t=N(r,:)'; 
     str=X(t,:); 
     check=squareform(pdist(str,'hamming')*len); 
     strings=char(str+64) 
     check 
    endfor 
else 
    printf("There are no matches\n"); 
endif 

它會生成字符串如：

 
ABAACCBCACABBABBAABA 
ABACCCBCACBABAABACBA 
CABBCBBBABCBBACAAACC