Hit integration for identifying optimal spaced seeds

BMC Bioinformatics

Research

Won-Hyoung Chung¹  Seong-Bae Park¹ 

[1] Department of Computer Engineering, Kyungpook National University, 702-701, Daegu, South Korea;

关键词: Dynamic Programming;    Suffix;    Homologous Region;    Dynamic Programming Algorithm;    Gaussian Quadrature;   

DOI  :  10.1186/1471-2105-11-S1-S37

来源: Springer

【 摘 要 】

BackgroundIntroduction of spaced speeds opened a way of sensitivity improvement in homology search without loss of search speed. Since then, the efforts of finding optimal seed which maximizes the sensitivity have been continued today. The sensitivity of a seed is generally computed by its hit probability. However, the limitation of hit probability is that it computes the sensitivity only at a specific similarity level while homologous regions usually distributed in various similarity levels. As a result, the optimal seed found by hit probability is not actually optimal for various similarity levels. Therefore, a new measure of seed sensitivity is required to recommend seeds that are robust to various similarity levels.ResultsWe propose a new probability model of sensitivity hit integration which covers a range of similarity levels of homologous regions. A novel algorithm of computing hit integration is proposed which is based on integration of hit probabilities at a range of similarity levels. We also prove that hit integration is computable by expressing the integral part of hit integration as a recursive formula which can be easily solved by dynamic programming. The experimental results for biological data show that hit integration reveals the seeds more optimal than those by PatternHunter.ConclusionThe presented model is a more general model to estimate sensitivity than hit probability by relaxing similarity level. We propose a novel algorithm which directly computes the sensitivity at a range of similarity levels.

【 授权许可】

CC BY   
© Chung and Park; licensee BioMed Central Ltd. 2010