On spaced seeds for similarity search
On spaced seeds for similarity search
复制标题
DOI：
10.1016/s0166-218x(03)00382-2
复制
发表时间：
2004-04-15
影响因子：
1.1
通讯作者：
Tromp, J
中科院分区：
文献类型：
--
作者：
Keich, U;Li, M;Tromp, J
基因组学研究通常依赖于基于寻找短种子匹配（连续 k 碱基）然后进行扩展的策略的相似性搜索。种子长度 k 的具体选择是由搜索速度（较大的 k 减少命中机会）和灵敏度（较小的 k 发现较弱的相似性）之间的权衡决定的。 Ma 等人提出了使用单个确定性优化间隔种子的新颖想法。 （Bioinformatics (2002) 18）对上述相似性搜索过程进行了验证，并根据经验证明，最佳间隔种子使搜索速度提高四倍，而不会牺牲灵敏度。 Califano 和 Rigoutsos（技术报告，IBM T.J. Watson 研究中心 (1995)、Burkhardt、Karkkainen、CPM (2001) 和 Buhler, Bioinformatics 17 (2001) 419）和其他应用中也研究了多个随机间隔模式、间隔 q-gram 和间隔探针 [(RECOMB (1999) 295, RECOMB （2000）245）]。他们都被发现比邻近的同行更好。在本文中，我们研究了最佳种子的一些理论和实践方面。特别是，我们证明了常用的连续种子在某种意义上是最差的，并且我们为寻找最佳种子的问题提供了一种算法解决方案。 (C) 2003 Elsevier B.V. 保留所有权利。
Genomics studies routinely depend on similarity searches based on the strategy of finding short seed matches (contiguous k bases) which are then extended. The particular choice of the seed length, k, is determined by the tradeoff between search speed (larger k reduces chance hits) and sensitivity (smaller k finds weaker similarities). A novel idea of using a single deterministic optimized spaced seed was introduced in Ma et al. (Bioinformatics (2002) 18) to the above similarity search process and it was empirically demonstrated that the optimal spaced seed quadruples the search speed, without sacrificing sensitivity. Multiple, randomly spaced patterns, spaced q-grams, and spaced probes were also studied in Califano and Rigoutsos (Technical Report, IBM T.J. Watson Research Center (1995), Burkhardt, Karkkainen, CPM (2001), and Buhler, Bioinformatics 17 (2001) 419) and in other applications [(RECOMB (1999) 295, RECOMB (2000) 245)]. They were all found to be better than their contiguous counterparts. In this paper we study some of the theoretical and practical aspects of optimal seeds. In particular we demonstrate that the commonly used contiguous seed is in some sense the worst one, and we offer an algorithmic solution to the problem of finding the optimal seed. (C) 2003 Elsevier B.V. All rights reserved.