engleski

A Note on Indexing DNA and Protein Sequences

Many applications in computational biology rely on indexing biological sequences. Indexing the sequences greatly reduces the time complexity of a search. However, good index structures, such as suffix trees, require inordinate amounts of space. We describe a work in progress on a new approach to indexing using truncated suffix tree implemented with a LZ compressed trie. The index would require about 4 bytes per symbol for the largest collection of protein sequences (over 450 M amino acids) and about 5 bytes for the largest collection of DNA sequences (over 20 G bases).

DNA indexing; protein sequence indexing; suffix trees; LZ trie; sequence matching; truncated suffix tree; suffix sequoia

nije evidentirano