Multiple spaced seeds for homology search
Multiple spaced seeds for homology search
复制标题
DOI：
10.1093/bioinformatics/btm422
复制
发表时间：
2007-11-15
期刊：
影响因子：
5.8
通讯作者：
Ilie, Silvana
中科院分区：
文献类型：
--
作者：
Ilie, Lucian;Ilie, Silvana
动机：同源性搜索在两个生物序列之间找到相似的片段，如DNA或蛋白质序列。PatternHunter中引入了最佳间距种子，提高了同源搜索的灵敏度和速度，并已被许多比对程序采用，如BLAST。随着PatternHunterll中多个间隔种子的进一步改进，史密斯-沃特曼灵敏度以BLASTn速度逼近。结果：给出了一种在多项式时间内计算最佳多重种子的简单算法。由于采用了完全不同的方法，因此与以前的方法有很大的不同。在12天内计算了PatternHunterII的多个间距的种子，重16粒，重11粒。S花了我们17岁才找到一个更好的。我们的方法改变了观察多个间隔种子的方式。联系：ilie@csd.uwo.ca。
Motivation: Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. The introduction of optimal spaced seeds in PatternHunter has increased both the sensitivity and the speed of homology search, and it has been adopted by many alignment programs such as BLAST. With the further improvement provided by multiple spaced seeds in PatternHunterll, Smith-Waterman sensitivity is approached at BLASTn speed. However, computing optimal multiple spaced seeds was proved to be NP-hard and current heuristic algorithms are all very slow (exponential).Results: We give a simple algorithm which computes good multiple seeds in polynomial time. Due to a completely different approach, the difference with respect to the previous methods is dramatic. The multiple spaced seed of PatternHunterII, with 16 weight 11 seeds, was computed in 12 days. It takes us 17 s to find a better one. Our approach changes the way of looking at multiple spaced seeds.Contact: ilie@csd.uwo.ca.