c++ - 提高字符串重叠矩阵构建效率

Question

我有一个巨大的列表(N = ~100 万)，其中包含 100 个字符长的字符串，我试图找出它们之间的重叠部分。例如，一个字符串可能是

XXXXXXXXXXXXXXXXXXAACTGCXAACTGGAAXA (and so on)

我需要构建一个 N × N 矩阵，其中包含每个字符串与其他每个字符串的最长重叠值。我现在的方法是(伪代码)

read in all strings to array

create empty NxN matrix

compare each string to every string with a higher array index (to avoid redoing comparisons)

Write longest overlap to matrix

还有很多其他事情要做，但我确实需要一种更有效的方法来构建矩阵。即使使用最强大的计算集群，我也需要几天时间才能掌握这种方法。

如果您没有猜到，这些是 DNA 片段。 X 表示“通配符”(探针给出的质量分数低于阈值)，所有其他选项都是碱基(A、C、T 或 G)。我尝试编写一个四叉树算法，但这种方法太占用内存了。

如果您能提供任何更有效的方法建议，我会很高兴；我正在使用 C++，但伪代码/想法或其他语言代码也会非常有帮助。

编辑一些代码摘录，说明我当前的方法。与概念无关的任何内容均已删除

//part that compares them all to each other
for (int j=0; j<counter; j++) //counter holds # of DNA
    for (int k=j+1; k<counter; k++)
        int test = determineBestOverlap(DNArray[j],DNArray[k]);

//boring stuff

//part that compares strings. Definitely very inefficient,
//although I think the sheer number of comparisons is the main problem
int determineBestOverlap(string str1, string str2)
{
    int maxCounter = 0, bestOffset = 0;
    //basically just tries overlapping the strings every possible way
    for (int j=0; j<str2.length(); j++)
    {
        int counter = 0, offset = 0;
        while (str1[offset] == str2[j+offset] && str1[offset] != 'X') 
        {
              counter++;
              offset++;
        }
        
        if (counter > maxCounter)
        {
                    maxCounter = counter;
                    bestOffset = j;
        }
    }
    return maxCounter; 
} //this simplified version doesn't account for flipped strings

Answer 1

你真的需要知道所有字符串对之间的匹配吗？如果是，那么您将不得不将每个字符串与其他每个字符串进行比较，这意味着您将需要进行 n^2/2 次比较，并且即使您只为每个字符串对存储一个字节，您也将需要半 TB 的内存。

但是，我假设您真正感兴趣的是长字符串，那些有超过 20 个或 30 个甚至超过 80 个共同字符的字符串，您可能真的不想知道两个字符串是否对有 3 个字符相同，另外 50 个是 X，其余 47 个不匹配。

如果我是你，我会尝试什么——仍然不知道这是否适合你的应用——是:

1) 从每个字符串中，提取有意义的最大子字符串。我想您想完全忽略开头和结尾处的“X”，如果某些“可读”部分被大量“X”破坏，则单独处理可读部分而不是使用更长的字符串。很多这样的“哪些子串是相关的？”取决于你的数据和应用程序，我真的不知道。

2) 列出这些最长的子串，以及每个子串出现的次数。按字符串长度排序此列表。您可以但实际上不必将每个原始字符串的索引与子字符串一起存储。你会得到类似(示例)的东西

AGCGCTXATCG 1
GAGXTGACCTG 2
.....
CGCXTATC    1
......

3) 现在，从列表的顶部到底部:

a) 将“当前字符串”设置为列表顶部的字符串。

b) 如果当前字符串旁边的出现次数 > 1，则您找到了匹配项。如果您不记得索引，请在原始字符串中搜索子字符串，并标记匹配项。

c) 将当前字符串与所有相同长度的字符串进行比较，以找到某些字符为 X 的匹配项。

d) 从当前字符串中删除第一个字符。如果结果字符串已经在您的表中，则将其出现次数计数器加一，否则将其输入表中。

e) 从当前字符串中删除最后一个而不是第一个字符，重复 3b。

f) 从列表中删除当前字符串。

g) 从 3a) 开始重复，直到计算时间用完，或者剩余的字符串变得太短而不有趣。

这是否是一个更好的算法在很大程度上取决于您的数据以及您真正感兴趣的比较。如果您的数据非常随机/您的匹配项很少，它可能需要比您最初的想法更长的时间。但它可能会让您首先找到有趣的部分，并跳过不那么有趣的部分。