Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2006 Apr;4(2):553-69.
doi: 10.1142/s0219720006001977.

A unifying framework for seed sensitivity and its application to subset seeds

Gregory Kucherov  1 , Laurent Noé, Mikhail Roytberg
Affiliations

A unifying framework for seed sensitivity and its application to subset seeds

Gregory Kucherov et al. J Bioinform Comput Biol. 2006 Apr.

Abstract

We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem--a set of target alignments, an associated probability distribution, and a seed model--that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Illustration to Example 2
Algorithm 1
Algorithm 1
Sπ computation
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

See all "Cited by" articles

References

    1. Aho AV, Corasick MJ. Efficient string matching: An aid to bibliographic search. Communications of the ACM. 1975;18(6):333–340.
    1. Altschul S, Madden T, Schäffer A, Zhang J, Zhang Z, Miller W, Lipman D. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research. 1997;25(17):3389–3402. - PMC - PubMed
    1. Brejova B, Brown D, Vinar T. Optimal spaced seeds for Hidden Markov Models, with application to homologous coding regions. In: Baeza-Yates MCR, Chavez E, editors. Lecture Notes in Computer Science; Proceedings of the 14th Symposium on Combinatorial Pattern Matching; Morelia (Mexico). June 2003; Springer; pp. 42–54.
    1. Brejova B, Brown D, Vinar T. Vector seeds: an extension to spaced seeds allows substantial improvements in sensitivity and specificity. In: Benson G, Page R, editors. Lecture Notes in Computer Science; Proceedings of the 3rd International Workshop in Algorithms in Bioinformatics (WABI); Budapest (Hungary). September 2003; Springer;
    1. Brejova B, Brown D, Vinar T. Optimal spaced seeds for homologous coding regions. Journal of Bioinformatics and Computational Biology. 2004 Jan;1(4):595–610. - PubMed

Publication types

LinkOut - more resources