Annotated statistical indices for sequence analysis
Alberto Apostolico, Mary Ellen Bock, Xuyan Xu · 2002
A statistical index for string x is a digital-search tree or trie that returns, for any query string /spl omega/ and in a number of comparisons bounded by the length of /spl omega/, the number of occurrences of /spl omega/ in x. Clever algorithms are available that support the construction and weighting of such indices in time and space linear in the length of x. This paper addresses the problem of annotating a statistical index with such parameters as the expected value and variance of the number of occurrences of each substring.