Sensitivity analysis and efficient method for identifying optimal spaced seeds

被引：44

作者：

Choi, KP

Zhang, LX

机构：

[1] Natl Univ Singapore, Dept Math, Singapore 117543, Singapore

[2] Natl Univ Singapore, Dept Stat & Appl Probabil, Singapore 117543, Singapore

[3] Natl Univ Singapore, Dept Math, Singapore 117543, Singapore

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2004年 / 68卷 / 01期

关键词：

sequence comparison; pattern matching; filtration technique; spaced seeds; sensitivity analysis; heuristic algorithm;

D O I：

10.1016/j.jcss.2003.04.002

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The novel introduction of spaced seed idea in the filtration stage of sequence comparison by Ma et al. (Bioinformatics 18 (2002) 440) has greatly increased the sensitivity of homology search without compromising the speed of search. Finding the optimal spaced seeds is of great importance both theoretically and in designing better search tool for sequence comparison. In this paper, we study the computational aspects of calculating the hitting probability of spaced seeds; and based on these results, we propose an efficient algorithm for identifying optimal spaced seeds. (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：22 / 40

页数：19

共 23 条

[1] Gapped BLAST and PSI-BLAST: a new generation of protein database search programs [J].