期刊
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 73, 期 7, 页码 1024-1034出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2007.03.008
关键词
optimal spaced seeds; homology search
Optimal spaced seeds were introduced by the theoretical computer science community to bioinformatics to effectively increase homology search sensitivity. These seeds are serving many homology queries daily. However the computational complexity of finding the optimal spaced seeds remains to be open. In this paper, we prove that computing hit probability of a spaced seed in a uniform homology region is NP-hard, but it admits a probabilistic PTAS. We also show that the asymptotic hit probability is computable in exponential time in seed length, independent of the homologous region length. (c) 2007 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据