SST: an algorithm for finding near-exact sequence matches in time proportional to the logarithm of the database size
SST: an algorithm for finding near-exact sequence matches in time proportional to the logarithm of the database size
复制标题
DOI：
10.1093/bioinformatics/18.6.873
复制
发表时间：
2002-06-01
期刊：
影响因子：
5.8
通讯作者：
Volkmuth, W
中科院分区：
文献类型：
--
作者：
Giladi, E;Walker, MG;Volkmuth, W
动机：在大规模测序项目和比较基因组学中经常进行近精确序列匹配的检测。执行这些大规模的序列相似性搜索的时间和成本是禁止使用即使是最快的现存算法。结果：我们已经开发了一种算法，称为SST（序列搜索树），搜索数据库的DNA序列的近精确匹配，在时间上成比例的数据库大小n的对数。在SST中，我们使用多个偏移量将每个序列划分为称为“窗口”的固定长度的片段。每个窗口被映射到维度为4（k）的向量，该向量包含其分量k元组的出现频率，其中k是通常在4-6范围内的参数。然后，我们创建一个树结构的索引的窗口在矢量空间中，树结构的矢量量化（TSVQ）。我们通过将查询划分为窗口并在数据库中搜索最近邻窗口的树结构索引来识别查询序列的最近邻。当树是平衡的时，这产生搜索的0（log n）复杂度。在我们的计算中观察到了这种复杂性。SST对于靶序列与查询序列显示出高度相似性的应用是最有效的，例如组装鸟枪序列或将EST与基因组序列匹配。该算法也是一种有效的滤波方法。具体地说，它可以用作其他搜索方法的预处理步骤，以降低在一个大型数据库中搜索另一个数据库的复杂性。对于从1.5兆碱基的基因组序列中识别120000个片段的组装中的重叠片段的问题，当我们考虑构建和搜索树时，SST比BLAST快15倍。对于单独的搜索（即建立树索引后），SST比BLAST快27倍。
Motivation: Searches for near exact sequence matches are performed frequently in large-scale sequencing projects and in comparative genomics. The time and cost of performing these large-scale sequence-similarity searches is prohibitive using even the fastest of the extant algorithms. Faster algorithms are desired.Results: We have developed an algorithm, called SST (Sequence Search Tree), that searches a database of DNA sequences for near-exact matches, in time proportional to the logarithm of the database size n. In SST, we partition each sequence into fragments of fixed length called 'windows' using multiple offsets. Each window is mapped into a vector of dimension 4(k) which contains the frequency of occurrence of its component k-tuples, with k a parameter typically in the range 4-6. Then we create a tree-structured index of the windows in vector space, with tree-structured vector quantization (TSVQ). We identify the nearest neighbors of a query sequence by partitioning the query into windows and searching the tree-structured index for nearest-neighbor windows in the database. When the tree is balanced this yields an 0 (log n) complexity for the search. This complexity was observed in our computations. SST is most effective for applications in which the target sequences show a high degree of similarity to the query sequence, such as assembling shotgun sequences or matching ESTs to genomic sequence. The algorithm is also an effective filtration method. Specifically, it can be used as a preprocessing step for other search methods to reduce the complexity of searching one large database against another. For the problem of identifying overlapping fragments in the assembly of 120000 fragments from a 1.5 megabase genomic sequence, SST is 15 times faster than BLAST when we consider both building and searching the tree. For searching alone (i.e. after building the tree index), SST 27 times faster than BLAST.