New algorithms for the spaced seeds

Xin Gao; Shuai Cheng Li; Yinan Lu

doi:10.1007/978-3-540-73814-5_5

New algorithms for the spaced seeds

Xin Gao, Shuai Cheng Li, Yinan Lu^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

The best known algorithm computes the sensitivity of a given spaced seed on a random region with running time O((M+L)|B|), where M is the length of the seed, L is the length of the random region, and |B| is the size of seed-compatible-suffix set, which is exponential to the number of 0's in the seed. We developed two algorithms to improve this running time: the first one improves the running time to O(|B′|²ML), where B′ is a subset of B; the second one improves the running time to O((M|B|) ^2.236log(L/M)), which will be much smaller than the original running time when L is large. We also developed a Monte Carlo algorithm which can guarantee to quickly find a near optimal seed with high probability. © Springer-Verlag Berlin Heidelberg 2007.

Original language	English
Title of host publication	Frontiers in Algorithmics
Subtitle of host publication	First Annual International Workshop, FAW 2007, Lanzhou, China, August 1-3, 2007, Proceedings
Editors	Franco P. Preparata, Qizhi Fang
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	50-61
ISBN (Electronic)	978-3-540-73814-5
ISBN (Print)	9783540738138
DOIs	https://doi.org/10.1007/978-3-540-73814-5_5
Publication status	Published - 2007
Externally published	Yes
Event	1st International Workshop on Frontiers in Algorithmics (FAW 2007) - Lanzhou, China Duration: 1 Aug 2007 → 3 Aug 2007

Publication series

Name	Lecture Notes in Computer Science
Volume	4613
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Workshop on Frontiers in Algorithmics (FAW 2007)
Country/Territory	China
City	Lanzhou
Period	1/08/07 → 3/08/07

Research Keywords

Bioinformatics
Homology search
Spaced seed

Access Output

10.1007/978-3-540-73814-5_5

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{d6dd88a062104e3aaa555883311096d2,

title = "New algorithms for the spaced seeds",

abstract = "The best known algorithm computes the sensitivity of a given spaced seed on a random region with running time O((M+L)|B|), where M is the length of the seed, L is the length of the random region, and |B| is the size of seed-compatible-suffix set, which is exponential to the number of 0's in the seed. We developed two algorithms to improve this running time: the first one improves the running time to O(|B′|2ML), where B′ is a subset of B; the second one improves the running time to O((M|B|) 2.236log(L/M)), which will be much smaller than the original running time when L is large. We also developed a Monte Carlo algorithm which can guarantee to quickly find a near optimal seed with high probability. {\textcopyright} Springer-Verlag Berlin Heidelberg 2007.",

keywords = "Bioinformatics, Homology search, Spaced seed",

author = "Xin Gao and Li, {Shuai Cheng} and Yinan Lu",

year = "2007",

doi = "10.1007/978-3-540-73814-5_5",

language = "English",

isbn = "9783540738138",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "50--61",

editor = "Preparata, {Franco P. } and Fang, {Qizhi }",

booktitle = "Frontiers in Algorithmics",

note = "1st International Workshop on Frontiers in Algorithmics (FAW 2007) ; Conference date: 01-08-2007 Through 03-08-2007",

}

Gao, X, Li, SC & Lu, Y 2007, New algorithms for the spaced seeds. in FP Preparata & Q Fang (eds), Frontiers in Algorithmics: First Annual International Workshop, FAW 2007, Lanzhou, China, August 1-3, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4613 , Springer , Berlin, Heidelberg, pp. 50-61, 1st International Workshop on Frontiers in Algorithmics (FAW 2007), Lanzhou, China, 1/08/07. https://doi.org/10.1007/978-3-540-73814-5_5

New algorithms for the spaced seeds. / Gao, Xin; Li, Shuai Cheng; Lu, Yinan.
Frontiers in Algorithmics: First Annual International Workshop, FAW 2007, Lanzhou, China, August 1-3, 2007, Proceedings. ed. / Franco P. Preparata; Qizhi Fang. Berlin, Heidelberg: Springer , 2007. p. 50-61 (Lecture Notes in Computer Science; Vol. 4613 ).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - New algorithms for the spaced seeds

AU - Gao, Xin

AU - Li, Shuai Cheng

AU - Lu, Yinan

PY - 2007

Y1 - 2007

N2 - The best known algorithm computes the sensitivity of a given spaced seed on a random region with running time O((M+L)|B|), where M is the length of the seed, L is the length of the random region, and |B| is the size of seed-compatible-suffix set, which is exponential to the number of 0's in the seed. We developed two algorithms to improve this running time: the first one improves the running time to O(|B′|2ML), where B′ is a subset of B; the second one improves the running time to O((M|B|) 2.236log(L/M)), which will be much smaller than the original running time when L is large. We also developed a Monte Carlo algorithm which can guarantee to quickly find a near optimal seed with high probability. © Springer-Verlag Berlin Heidelberg 2007.

AB - The best known algorithm computes the sensitivity of a given spaced seed on a random region with running time O((M+L)|B|), where M is the length of the seed, L is the length of the random region, and |B| is the size of seed-compatible-suffix set, which is exponential to the number of 0's in the seed. We developed two algorithms to improve this running time: the first one improves the running time to O(|B′|2ML), where B′ is a subset of B; the second one improves the running time to O((M|B|) 2.236log(L/M)), which will be much smaller than the original running time when L is large. We also developed a Monte Carlo algorithm which can guarantee to quickly find a near optimal seed with high probability. © Springer-Verlag Berlin Heidelberg 2007.

KW - Bioinformatics

KW - Homology search

KW - Spaced seed

UR - http://www.scopus.com/inward/record.url?scp=38049185212&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-38049185212&origin=recordpage

U2 - 10.1007/978-3-540-73814-5_5

DO - 10.1007/978-3-540-73814-5_5

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783540738138

T3 - Lecture Notes in Computer Science

SP - 50

EP - 61

BT - Frontiers in Algorithmics

A2 - Preparata, Franco P.

A2 - Fang, Qizhi

PB - Springer

CY - Berlin, Heidelberg

T2 - 1st International Workshop on Frontiers in Algorithmics (FAW 2007)

Y2 - 1 August 2007 through 3 August 2007

ER -

New algorithms for the spaced seeds

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this