2

我有一个巨大的字符串列表（N = ~100 万），长度为 100 个字符，我试图找到它们之间的重叠。例如，一个字符串可能是

XXXXXXXXXXXXXXXXXXAACTGCXAACTGGAAXA (and so on)

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

将所有字符串读入数组

创建空 NxN 矩阵

将每个字符串与具有更高数组索引的每个字符串进行比较（以避免重做比较）

将最长重叠写入矩阵

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

如果您没有猜到，这些是 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
4

2 回答 2

1

你真的需要知道所有字符串对之间的匹配吗？如果是，那么您将必须将每个字符串与每个其他字符串进行比较，这意味着您将需要 n^2/2 次比较，并且即使每个字符串对只存储一个字节，您也将需要 1.5 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) 开始重复，直到计算时间用完，或者剩余的字符串变得太短而无趣。

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

于 2014-03-02T22:00:16.913 回答
0

我没有看到很多方法可以改善您需要将每个字符串相互比较（包括移动它们）这一事实，这本身就是超长的，计算集群似乎是最好的方法。

我看到的唯一改进方法是字符串比较本身：用二进制模式替换 A、C、T、G 和 X：

  • A = 0x01
  • C = 0x02
  • T = 0x04
  • G = 0x08
  • X = 0x0F
这样，您可以将一个项目存储在 4 位上，即每个字节两个（虽然这可能不是一个好主意，但仍然是一个可能的调查选项），然后使用 AND 操作快速比较它们，这样您就“只是”必须计算你有多少连续的非零值。这只是一种处理通配符的方法，抱歉，我没有更好的主意来降低整体比较的复杂性。

于 2014-03-02T21:57:30.983 回答