Multiple spaced seeds for homology search
(2007) In Bioinformatics 23(22). p.2969-2977- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/968953
- author
- Ilie, Lucian and Ilie, Silvana LU
- organization
- publishing date
- 2007
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Bioinformatics
- volume
- 23
- issue
- 22
- pages
- 2969 - 2977
- publisher
- Oxford University Press
- external identifiers
-
- wos:000251197800002
- scopus:36448966762
- ISSN
- 1367-4803
- DOI
- 10.1093/bioinformatics/btm422
- 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
- 708b0af2-81df-40ea-a987-fea469efc566 (old id 968953)
- date added to LUP
- 2016-04-01 11:57:49
- date last changed
- 2022-01-26 20:49:29
@article{708b0af2-81df-40ea-a987-fea469efc566,
abstract = {{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.}},
author = {{Ilie, Lucian and Ilie, Silvana}},
issn = {{1367-4803}},
language = {{eng}},
number = {{22}},
pages = {{2969--2977}},
publisher = {{Oxford University Press}},
series = {{Bioinformatics}},
title = {{Multiple spaced seeds for homology search}},
url = {{http://dx.doi.org/10.1093/bioinformatics/btm422}},
doi = {{10.1093/bioinformatics/btm422}},
volume = {{23}},
year = {{2007}},
}