文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > proportional to the logarithm
侵权投诉

proportional to the logarithm

An algorithm for searching sequence databases in time

SST: An algorithm for searching sequence databases in time proportional to the logarithm of the database size. egiladi@incyte.com 1 2

Eldar Giladi 1

Michael G. Walker 1 mwalker@incyte.com

wangz@Cs.Stanford.Edu

James Ze Wang 2

Wayne Volkmuth 1 volkmuth@incyte.com

Research Informatics, Incyte, 3174 Porter Drive, Palo Alto CA 94303 Department of Computer Science, Stanford University, Stanford CA 94089

Keywords: sequence similarity search, clustering, k-tuple encoding.

1 Introduction In the current e orts to generate and interpret the complete genome sequences of humans and model organisms, large scale searches for near exact sequence matches are frequently performed. Examples include programs that assemble DNA from shotgun sequencing projects which initially search for overlapping fragments, large scale searches of EST databases against genomic databases to determine the location of genes, and cross species genomic comparisons between very closely related genomes. We have developed an algorithm, called SSTSequence Search Tree, that searches a database of DNA sequences for near exact matches, in time proportional to the logarithm of the database size n.

2 The SST algorithm In SST, we partition each sequence into fragments of xed length W called windows" using multiple o sets. Windows begin at position j, and end at position j+ W, with j= 0; 1; 2::: . Typical values of the parameters are 0 W 1000 and 5 W=2. Then each window is mapped into a vector of dimension 4 that represents the frequency of occurrence of its component k-tuples. Speci cally, the I 'th entry in the vector is the number of occurrences of tuple I in that window. Here we associate the integer  k

Ia1 a2 ak=  k i 2 f

X 4 Ma; k l l l=1

with the k-tuple of nucleotides a1 a2 a, a A,C,G,T where Ma= 0; 1; 2; 3 for a= A, a= C, a= G, a= T, respectively. Typically 4 k 6. The mapping has transformed the problem of nding near exact matches to query windows in the database to that of nding nearest neighbors in vector space. This search can be done very e ciently by constructing a tree-structured index of vectors. We construct the index using tree structured vector quantizationTSVQ, by recursively searching the data for clusters that provide binaryor higher-order partitions using k-means clustering 2 . We identify the nearest-neighbors of a query sequence by partitioning the query into non-overlapping windows and searching the tree-structured index for nearest neighbor windows in the database. Only windows which are at L1 distance less than a threshold T are returned. However, SST is not guaranteed to return all nearest neighbors at distance T, as we shall see in our computations. Our work is most closely related to 1, 3, 4 . g l l l l l







第1页

你可能喜欢

热门文档

相关文档

  • proportional to the logarithm

    SST: An algorithm for searching sequence databases in time proportional to the logarithm of the database size. Eldar Giladi Michael G. Walker y James ...

  • HCI复习提纲答案(附带中文翻译)

    公式是什么 Hick’s law states that the time it takes to choose one item from n alternatives is proportional to the logarithm (base 2) of the number...

  • 电位分析法-英文版-potentiometry

    measured potential, and the contribution is proportional to the logarithm of the selectivity coefficient: A smaller selectivity coefficient indicates less ...

  • HCI复习题

    What is the formula? (ppt 7-32) Hick’s law states that the time it takes to choose one item from n alternatives is proportional to the logarithm ...

  • BZ化学振荡反应在分析检测中的应用(1)

    The results show that the changes both in oscillating period and amplitude were linearly proportional to the logarithm of the concentration of 1-naphthylamine...

  • 北京大学实验心理学课件PPT版 第三章 心理物理学方法

    Is useful for comparing the sensitivity of different sense modalities. Fechner’s Law R = k㏒S; sensation is proportional to the logarithm of stimulus ...

  • HCI复习题

    s law states that the time it takes to choose one item from n alternatives is proportional to the logarithm (base 2) of the number of choices, plus...

  • 生物化学专业名词单词表

    proportional to the logarithm of their mass 与它们的质量的对数成线性比例 linear relationship 线性关系 sensitive 灵敏的 subunit 亚基 1 B8 蛋白质测序 (p ...

  • 电位分析法

    The potential difference developed across the membrane is in fact directly proportional to the Logarithm of the ionic concentration in the external solution. ...

  • 系在氨基酸及金属离子测定中的应用

    5.27×10-8 to 5.27×10-12 mol/L, the changes of oscillating period are linearly proportional to the negative logarithm of the concentrations of cobal...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email