Fast index based algorithms and software for matching position specific scoring matrices.
Fast index based algorithms and software for matching position specific scoring matrices.
复制标题
基于快速索引的算法和用于匹配位置特定评分矩阵的软件。
DOI：
10.1186/1471-2105-7-389
复制
发表时间：
2006-08-24
影响因子：
3
通讯作者：
Kurtz S
中科院分区：
文献类型：
--
作者：
Beckstette M;Homann R;Giegerich R;Kurtz S
在生物序列分析中，位置特异性评分矩阵（PSSMs）被广泛用于表示核苷酸和氨基酸序列中的序列基序。在全基因组或大型序列数据库中搜索pssm是一种常见的，但计算成本很高的任务。我们提出了一种新的非启发式算法，称为ESAsearch，以有效地在大型数据库中查找pssm的匹配。我们的方法预处理搜索空间，例如，一个完整的基因组或一组蛋白质序列，并建立一个增强后缀阵列存储在文件中。这允许使用PSSM在亚线性期望时间内搜索数据库。由于ESAsearch受益于较小的字母，我们提出了一种变体，操作根据简化的字母编码的序列。我们还通过开发一种方法来解决PSSM分数不可比较的问题，该方法允许在给定e值或p值的情况下有效计算PSSM的矩阵相似阈值。我们的方法是基于动态规划的，与其他方法不同的是，它采用了动态规划矩阵的惰性求值。我们用核苷酸pssm和氨基酸pssm来评估ESAsearch算法。与以前最好的方法相比，ESAsearch显示核苷酸PSSMs的加速系数在17到275之间，氨基酸PSSMs的加速系数高达1.8。与最广泛使用的程序进行比较甚至显示出至少3.8倍的加速。与使用20个符号标准字母表所获得的结果相比，字母表减少在氨基酸序列上产生了额外的2个加速因子。惰性求值方法也比以前的方法快得多，速度提高了3到330倍。我们对ESAsearch的分析表明，在预期情况下，ESAsearch的运行时间是亚线性的，而在最坏的情况下，ESAsearch的运行时间是线性的，因为序列不短于||m + m - 1，其中m是PSSM的长度和有限的字母表。在实践中，ESAsearch表现出优于大多数广泛使用的程序的性能，特别是在DNA序列方面。新的精确的实时计算阈值的算法有可能取代以前使用的近似方法。除了算法贡献之外，我们还提供了一个健壮的、文档完备的、易于使用的软件包，实现了本文中提出的思想和算法。
In biological sequence analysis, position specific scoring matrices (PSSMs) are widely used to represent sequence motifs in nucleotide as well as amino acid sequences. Searching with PSSMs in complete genomes or large sequence databases is a common, but computationally expensive task. We present a new non-heuristic algorithm, called ESAsearch, to efficiently find matches of PSSMs in large databases. Our approach preprocesses the search space, e.g., a complete genome or a set of protein sequences, and builds an enhanced suffix array that is stored on file. This allows the searching of a database with a PSSM in sublinear expected time. Since ESAsearch benefits from small alphabets, we present a variant operating on sequences recoded according to a reduced alphabet. We also address the problem of non-comparable PSSM-scores by developing a method which allows the efficient computation of a matrix similarity threshold for a PSSM, given an E-value or a p-value. Our method is based on dynamic programming and, in contrast to other methods, it employs lazy evaluation of the dynamic programming matrix. We evaluated algorithm ESAsearch with nucleotide PSSMs and with amino acid PSSMs. Compared to the best previous methods, ESAsearch shows speedups of a factor between 17 and 275 for nucleotide PSSMs, and speedups up to factor 1.8 for amino acid PSSMs. Comparisons with the most widely used programs even show speedups by a factor of at least 3.8. Alphabet reduction yields an additional speedup factor of 2 on amino acid sequences compared to results achieved with the 20 symbol standard alphabet. The lazy evaluation method is also much faster than previous methods, with speedups of a factor between 3 and 330. Our analysis of ESAsearch reveals sublinear runtime in the expected case, and linear runtime in the worst case for sequences not shorter than ||m + m - 1, where m is the length of the PSSM and a finite alphabet. In practice, ESAsearch shows superior performance over the most widely used programs, especially for DNA sequences. The new algorithm for accurate on-the-fly calculations of thresholds has the potential to replace formerly used approximation approaches. Beyond the algorithmic contributions, we provide a robust, well documented, and easy to use software package, implementing the ideas and algorithms presented in this manuscript.
登录
查看更多内容
DOI：
10.1093/protein/13.3.149
发表时间：
2000-03-01
期刊：
PROTEIN ENGINEERING
影响因子：
--
作者：
Murphy, LR;Wallqvist, A;Levy, RM
通讯作者：
Levy, RM
影响因子：
14.9
作者：
Hulo, N;Sigrist, CJA;Bairoch, A
通讯作者：
Bairoch, A
影响因子：
1.3
作者：
Giegerich, R;Kurtz, S
通讯作者：
Kurtz, S
DOI：
10.1089/cmb.1994.1.93
发表时间：
1994-01-01
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
Goldstein, L;Waterman, M S
通讯作者：
Waterman, M S
影响因子：
14.9
作者：
Sandelin, A;Alkema, W;Lenhard, B
通讯作者：
Lenhard, B