论文部分内容阅读
比较数兆碱基的DNA序列是发现和标记保守的基因组特征普遍使用的技术，进行这样的比较可以发现长达几十兆的序列之间很多短的局部对齐。为有效地处理这样的长序列，已有的算法通过扩展短的、不含替换及其他不同之处的匹配碱基串来发现对齐。但是，精确匹配的碱基串太短，在重要的相似性中出现的这种匹配串也会偶然出现在背景序列中，因此对于不含长的精确匹配串的序列，算法必须平衡发现序列特征的效率和敏感性。 本文首先分析了两种降低相似搜索算法复杂度的方法：过滤试探法和确定的排除法。对于高于用户指定阈值的相似性，确定的排除算法确保具有100％敏感性。但是，对于相似度低，但实际上有趣的相同度水平65—70％的大规模全体成对问题，其敏感性不好。字匹配过滤试探法在实践中更有效一些，但其敏感性无控制地依赖于有趣的相似性中突变的分布，并且当相同度在67％左右时，其效率和敏感性显著衰退。 在分析以上两种方法的基础上，本文提出了一种新的算法：RP-ALL-PAIRS算法。该算法通过随机投影发现基因组序列中含有特定部分的替换的无间隔局部对齐。这些对齐的长度和替换率可以选择，使其在重要的相似性中出现频繁，而在背景序列中出现很少。RP-ALL-PAIRS使用位置敏感散列函数来获取DNA序列的随机投影。在位置敏感散列函数下，两个串投影值相同的概率直接随它们的相似度不同而变化。将随机方法应用于相似搜索打破了维的制约，在相似度低至67％的无间隔相同度时，得到比确定性的排除算法(如双过滤算法)本质上更好的性能。在实践中标记基因组特征时，RP-ALL-PAIRS和字匹配技术互为补充，使用它可发现用相对短的字长难以发现的生物学上有趣的相似性。 本文还分析了算法的性能，并在此基础上讨论了如何给RP-ALL-PAIRS选择最优化的参数及算法实现的细节问题，通过实验证实了RP-ALL-PAIRS发现DNA序列特征时取得了较好的效率和敏感性的平衡。