Discovering sequence similarity by the algorithmic significance method [electronic resource].
- Published
- Washington, D.C. : United States. Dept. of Energy, 1993.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy. - Physical Description
- 11 pages : digital, PDF file
- Additional Creators
- Argonne National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online
- Restrictions on Access
- Free-to-read Unrestricted online access
- Summary
- The minimal-length encoding approach is applied to define concept of sequence similarity. A sequence is defined to be similar to another sequence or to a set of keywords if it can be encoded in a small number of bits by taking advantage of common subwords. Minimal-length encoding of a sequence is computed in linear time, using a data compression algorithm that is based on a dynamic programming strategy and the directed acyclic word graph data structure. No assumptions about common word (``k-tuple``) length are made in advance, and common words of any length are considered. The newly proposed algorithmic significance method provides an exact upper bound on the probability that sequence similarity has occurred by chance, thus eliminating the need for any arbitrary choice of similarity thresholds. Preliminary experiments indicate that a small number of keywords can positively identify a DNA sequence, which is extremely relevant in the context of partial sequencing by hybridization.
- Report Numbers
- E 1.99:anl/bim/cp--78918
E 1.99: conf-930745--2
conf-930745--2
anl/bim/cp--78918 - Subject(s)
- Other Subject(s)
- Note
- Published through SciTech Connect.
02/01/1993.
"anl/bim/cp--78918"
" conf-930745--2"
"DE93015556"
1. international conference in intelligent systems for molecular biology,Washington, DC (United States),7-9 Jul 1993.
Milosavljevic, A. - Funding Information
- W-31109-ENG-38
FG03-91ER61152
View MARC record | catkey: 13812290