Title | Discovering simple DNA sequences by the algorithmic significance method. |
Publication Type | Journal Article |
Year of Publication | 1993 |
Authors | Milosavljević A, Jurka J |
Journal | Comput Appl Biosci |
Volume | 9 |
Issue | 4 |
Pagination | 407-11 |
Date Published | 1993 Aug |
ISSN | 0266-7061 |
Keywords | Algorithms, Base Sequence, DNA, Satellite, Humans, Molecular Sequence Data, Pattern Recognition, Automated, Repetitive Sequences, Nucleic Acid, Sequence Analysis, DNA, Tissue Plasminogen Activator |
Abstract | A new method, 'algorithmic significance', is proposed as a tool for discovery of patterns in DNA sequences. The main idea is that patterns can be discovered by finding ways to encode the observed data concisely. In this sense, the method can be viewed as a formal version of the Occam's Razor principle. In this paper the method is applied to discover significantly simple DNA sequences. We define DNA sequences to be simple if they contain repeated occurrences of certain 'words' and thus can be encoded in a small number of bits. Such definition includes minisatellites and microsatellites. A standard dynamic programming algorithm for data compression is applied to compute the minimal encoding lengths of sequences in linear time. An electronic mail server for identification of simple sequences based on the proposed method has been installed at the Internet address pythia/anl.gov. |
DOI | 10.1093/bioinformatics/9.4.407 |
Alternate Journal | Comput. Appl. Biosci. |
PubMed ID | 8402207 |