Winnowing sequences from a database search
Winnowing sequences from a database search
复制标题
DOI：
10.1145/299432.299451
复制
发表时间：
1999-04
期刊：
影响因子：
--
通讯作者：
P. Berman;Zheng Zhang;Y. Wolf;E. Koonin;W. Miller
中科院分区：
文献类型：
--
作者：
P. Berman;Zheng Zhang;Y. Wolf;E. Koonin;W. Miller
在序列相似性的数据库搜索中，与不同序列区域（例如，蛋白质结构域）经常被与相同序列的另一个区域的大量匹配所掩盖。为了科普这一问题，人们提出了丢弃冗余匹配的算法。这个问题的一个模型是从一个区间列表开始的，每个区间都有一个相关的分数;每个区间给出了查询序列中与数据库序列比对的位置范围，分数就是比对的分数。如果区间I包含在区间J中，并且I的得分小于J的得分，则I被称为被J支配。然后，问题是识别被至少K个其他区间支配的每个区间，其中K是给定的“可容忍冗余”水平。“开发了一种算法来解决O（N log N）时间和O（N*）空间的问题，其中N是间隔的数量，N* 是一个精确定义的值，永远不会超过N，并且通常要小得多。这个丢弃数据库命中的标准已经在Blast程序中实现，如本文中用示例所示。还描述了这种方法的几种变型和扩展。
In database searches for sequence similarity, matches to a distinct sequence region (e.g., protein domain) are frequently obscured by numerous matches to another region of the same sequence. In order to cope with this problem, algorithms are developed to discard redundant matches. One model for this problem begins with a list of intervals, each with an associated score; each interval gives the range of positions in the query sequence that align to a database sequence, and the score is that of the alignment. If interval I is contained in interval J, and I's score is less than J's, then I is said to be dominated by J. The problem is then to identify each interval that is dominated by at least K other intervals, where K is a given level of "tolerable redundancy." An algorithm is developed to solve the problem in O(N log N) time and O(N*) space, where N is the number of intervals and N* is a precisely defined value that never exceeds N and is frequently much smaller. This criterion for discarding database hits has been implemented in the Blast program, as illustrated herein with examples. Several variations and extensions of this approach are also described.