Overlap digraph: An effective model for finding good spaced seeds for biological sequence local alignment |
| |
Authors: | Ke Chen Kun She QingXin Zhu |
| |
Institution: | (1) Department of Computer Engineering, Kyungpook National University, Daegu, 702-701, South Korea |
| |
Abstract: | Spaced seeds technology, which was proposed by PatternHunter, has been proven to be more sensitive and faster than continuous
seeds, and it is now widely used for bio-sequence local alignments. However, finding optimal spaced seeds is an NP-hard problem.
A seed digraph model is proposed to find good spaced seeds, which are very close to optimal, in a very different but effective
way. Using this different approach, some good long spaced seeds which cannot be calculated by normal optimal sensitivity formulas
due to their exponential complexity can be found. |
| |
Keywords: | homology search spaced seed overlap digraph |
本文献已被 维普 SpringerLink 等数据库收录! |
|