Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73814-5_5 | FAW |
Keywords | Field | DocType |
high probability,known algorithm,monte carlo algorithm,time o,random region,new algorithm,spaced seed,seed-compatible-suffix set,near optimal seed,monte carlo | Exponential function,Monte Carlo algorithm,Computer science,Algorithm | Conference |
Volume | ISSN | ISBN |
4613 | 0302-9743 | 3-540-73813-4 |
Citations | PageRank | References |
1 | 0.35 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xin Gao | 1 | 598 | 64.98 |
| Shuai Cheng Li | 2 | 184 | 30.25 |
| Yinan Lu | 3 | 19 | 6.62 |