我需要比较 X 和 Y 染色体的 DNA 序列，并找到 Y 染色体独有的模式（由大约 50-75 个碱基对组成）。请注意，这些序列部分可以在染色体中重复。这需要快速完成（BLAST 需要 47 天，需要几个小时或更短时间）。有没有特别适合这种比较的算法或程序？同样，速度是这里的关键。
我把它放在 SO 上的原因之一是从特定应用程序领域之外的人那里获得观点，他们可以提出他们在日常使用中用于字符串比较的算法，这可能适用于我们的使用。所以不要害羞！
问问题
627 次
4 回答
3
- 在序列 X 上构建后缀树S。
- 对于序列 Y 中的每个起始位置 i，在 S 中查找字符串 Y[i..i+75]。如果从位置 i 开始找不到匹配项（即如果在 j < 75 个核苷酸匹配后查找失败），那么您有找到一个 Y 唯一的长度为 j 的字符串。
- 所有起始位置 i 上最小的此类字符串是最短的唯一字符串（如果您对最小化长度不感兴趣，则在找到任何此类字符串后停止）。
总时间：O(|X| + m|Y|) 其中 m 是最大字符串长度（例如 m = 75）。
可能还有基于广义后缀树的更有效的算法。
于 2010-08-27T03:51:21.303 回答
2
我假设你有一个 X 和一个 Y 来比较。将它们连接起来，用两个都不出现的标记字符分隔，形成例如 XoY。现在以线性时间形成http://en.wikipedia.org/wiki/Suffix_array。
你得到的是一个指向连接字符串中位置的指针数组，其中指针的排列方式使它们指向的子字符串按字母顺序出现在数组中。您还将获得一个 LCP 数组，给出一个后缀和数组中直接位于它之前的后缀之间共享的最长公共前缀的长度，该后缀的排序刚好小于它。这实际上是该位置和小于它的任何子字符串之间共享的最长公共前缀，因为任何具有更长公共前缀且小于 string[i] 的东西都会在它和当前 string[i - 1] 之间排序。
您可以判断指针从其位置指向哪个原始字符串，因为 X 在 Y 之前。您可以将数组切割成 X 和 Y 指针的交替子部分。pos[i] 和 pos[i - 1] 之间共享的公共前缀的长度是 lcp[i]。pos[i] 和 pos[i-2] 共享的前缀长度为 min(lcp[i], lcp[i-1])。因此，如果您从一系列 X 之前的 Y 值开始，您可以通过逐步降低该部分，在每一步执行最小操作，依次计算出该 Y 和所有 X 之间的前缀字符数。类似地，您可以计算出所有这些 X 和出现在后缀数组中的下一个 Y 之间共享的前缀字符数，每个 X 花费一分钟。当然，对于 Y 范围也是如此。
我认为您希望 X 或 Y 中的子字符串与其他性别的任何其他子字符串共享小前缀，因为从同一位置开始的比此长一个字符的字符串根本不会出现在其他性别中。我认为一旦你完成了上面的 min() 计算，你就可以使用堆提取 N 个最小的前缀子字符串来跟踪 N 个最小的条目。我认为这里的一切都需要时间线性 |X| + |是| （除非 N 与 |X| 或 |Y| 相当）。
于 2010-08-27T05:19:25.723 回答
1
本文可能有一些替代方案来调整 BLAST 以提高其性能（通过细分问题空间 AFAIKS）。
于 2010-08-27T02:53:53.330 回答
0
我有一个有趣的答案，它将是技术答案。主要思想是子序列的比较应该在GPU上进行，因为现代显卡的GPU是高度并行的处理环境（如小型超级计算机）。所以我们可以将碱基对编码为一个像素，假设 X 染色体有 1.54 亿对——我们得到一张包含 1.54 亿像素的 X 染色体图像——这个图像大小约为 500 MB。对于 Y 染色体，我们得到一个 160 MB 大小的图像。所以这两个（500+160）MB图像可以通过下降显卡非常有效地处理。（只需获得 >= 1 GB 视频内存的视频卡）。
下一步是编写 GPU 程序，可能借助Pixel Shader或Cuda或OpenCL
GPU 程序很简单——基本上它将 Y 染色体图像中的 50-75 个相邻像素与 X 染色体图像的所有像素进行比较。所以这个 GPU 程序最多应该有 75*1.54 亿次操作，这将在一个小时左右的时间内在现代 GPU 上计算出来。因为 Y 的所有子序列都将被并行测试。
希望有帮助
于 2010-08-27T09:40:49.673 回答