蛋白质组学与生物信息学杂志
开放获取

抽象的

从基因组中挖掘 Unique-m 子串

叶凯、贾振宇、王一鹏、Paul Flicek 和 Rolf Apweiler

基因组中独特的子串可能表明高水平的特异性，这对于许多遗传学研究（例如 PCR、微阵列）至关重要和基础杂交、Southern 和 Northern 印迹、RNA 干扰 (RNAi) 和基因组（重）测序。然而，仅基因组中的独特序列不足以保证高特异性。例如，即使感兴趣的子串在基因组中仅出现一次，在一定容差范围内的核苷酸错配也可能会损害特异性。在这项研究中，我们提出了基因组唯一 m 子串的概念，用于控制全基因组测定中的特异性。如果整个基因组的一条链上只有一个完美匹配，而所有其他近似匹配必须有超过 m 个不匹配，则定义了 unique-m 子串。我们开发了一种模式增长方法，可以从给定的基因组中系统地挖掘这种独特的 m 子串。我们的算法不需要预处理步骤来提取大多数其他竞争对手方法所需的序列信息。从基因组中搜索唯一的 m 个子串是作为常规的单个任务执行的数据挖掘，利用查询之间的相似性来实现巨大的加速。我们算法的运行时间与输入基因组的大小和唯一的 m 个子串的长度呈线性关系。此外，unique-m 挖掘算法已被并行化，以便于在具有共享内存的集群或具有多个 CPU 的单台机器上进行全基因组计算。