Please use this identifier to cite or link to this item: https://doi.org/10.1089/cmb.2005.12.1137
Title: Quick, practical selection of effective seeds for homology search
Authors: Preparata, F.P.
Zhang, L. 
Choi, K.P. 
Keywords: Filtration technique
Homology search
Leakage model
q-gram
Sequence alignment
Spaced seeds
Issue Date: Nov-2005
Citation: Preparata, F.P., Zhang, L., Choi, K.P. (2005-11). Quick, practical selection of effective seeds for homology search. Journal of Computational Biology 12 (9) : 1137-1152. ScholarBank@NUS Repository. https://doi.org/10.1089/cmb.2005.12.1137
Abstract: It has been observed that in homology search gapped seeds have better sensitivity than ungapped ones for the same cost (weight). In this paper, we propose a probability leakage model (a dissipative Markov system) to elucidate the mechanism that confers power to spaced seeds. Based on this model, we identify desirable features of gapped search seeds and formulate an extremely efficient procedure for seed design: it samples from the set of spaced seed exhibiting those features, evaluates their sensitivity, and then selects the best. The sensitivity of the constructed seeds is negligibly less than that of the corresponding known optimal seeds. While the challenging mathematical question of characterizing optimal search seeds remains open, we believe that our eminently efficient and effective approach represents a satisfactory solution from a practitioner's viewpoint. © Mary Ann Liebert, Inc.
Source Title: Journal of Computational Biology
URI: http://scholarbank.nus.edu.sg/handle/10635/104699
ISSN: 10665277
DOI: 10.1089/cmb.2005.12.1137
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

12
checked on Mar 27, 2020

WEB OF SCIENCETM
Citations

12
checked on Mar 19, 2020

Page view(s)

71
checked on Mar 28, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.