Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Fast computation of good multiple spaced seeds

Ilie, Lucian and Ilie, Silvana LU (2007) 7th International Workshop on Algorithms in Bioinformatics (WABI 2007) 4645. p.346-358
Abstract
Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. A significant fraction of computing power in the world is dedicated to performing such tasks. The introduction of optimal spaced seeds by Ma et al. 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 PatternHunterII, the sensitivity of dynamic programming is approached at BLASTn speed. Whereas computing optimal multiple spaced seeds was proved to be NP-hard, we show that, from practical point of view, computing good ones can be very efficient. We give a simple heuristic algorithm which... (More)
Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. A significant fraction of computing power in the world is dedicated to performing such tasks. The introduction of optimal spaced seeds by Ma et al. 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 PatternHunterII, the sensitivity of dynamic programming is approached at BLASTn speed. Whereas computing optimal multiple spaced seeds was proved to be NP-hard, we show that, from practical point of view, computing good ones can be very efficient. We give a simple heuristic algorithm which computes good multiple seeds in polynomial time. Computing sensitivity is not required. When allowing the computation of the sensitivity for few seeds, we obtain better multiple seeds than previous ones in much shorter time. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
BLAST, PatternHunterII, string overlaps, sensitivity, homology search, multiple spaced seeds
host publication
Algorithms in Bioinformatics, Proceedings (Lecture Notes in Computer Science)
volume
4645
pages
346 - 358
publisher
Springer
conference name
7th International Workshop on Algorithms in Bioinformatics (WABI 2007)
conference location
Philadelphia, Pennsylvania, United States
conference dates
2007-09-08 - 2007-09-09
external identifiers
  • wos:000249739200031
  • scopus:37249063588
ISSN
0302-9743
1611-3349
ISBN
978-3-540-74125-1
DOI
10.1007/978-3-540-74126-8_32
language
English
LU publication?
yes
additional info
The information about affiliations in this record was updated in December 2015. The record was previously connected to the following departments: Numerical Analysis (011015004)
id
f15fdb87-833f-456e-a757-ce71a87c82a5 (old id 1409920)
date added to LUP
2016-04-01 11:51:03
date last changed
2024-01-07 22:52:55
@inproceedings{f15fdb87-833f-456e-a757-ce71a87c82a5,
  abstract     = {{Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. A significant fraction of computing power in the world is dedicated to performing such tasks. The introduction of optimal spaced seeds by Ma et al. 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 PatternHunterII, the sensitivity of dynamic programming is approached at BLASTn speed. Whereas computing optimal multiple spaced seeds was proved to be NP-hard, we show that, from practical point of view, computing good ones can be very efficient. We give a simple heuristic algorithm which computes good multiple seeds in polynomial time. Computing sensitivity is not required. When allowing the computation of the sensitivity for few seeds, we obtain better multiple seeds than previous ones in much shorter time.}},
  author       = {{Ilie, Lucian and Ilie, Silvana}},
  booktitle    = {{Algorithms in Bioinformatics, Proceedings (Lecture Notes in Computer Science)}},
  isbn         = {{978-3-540-74125-1}},
  issn         = {{0302-9743}},
  keywords     = {{BLAST; PatternHunterII; string overlaps; sensitivity; homology search; multiple spaced seeds}},
  language     = {{eng}},
  pages        = {{346--358}},
  publisher    = {{Springer}},
  title        = {{Fast computation of good multiple spaced seeds}},
  url          = {{http://dx.doi.org/10.1007/978-3-540-74126-8_32}},
  doi          = {{10.1007/978-3-540-74126-8_32}},
  volume       = {{4645}},
  year         = {{2007}},
}