Figure 1. Simplified classification of sequence analysis tasks. One can clearly distinguish three major activities of sequence analysts. (1) Pattern searches: sequence alignment and searches for known patterns expressed in known alphabets of sequence (or structure-related) motifs. (2) Database design: creation of new data structures or inclusion of new knowledge into existing data structures. The ‘new knowledge’ can be inferred from sequence analyses but it can also be acquired from research outside sequence analysis. (3) Pattern acquisition: determining new alphabets and function-associated patterns. The shaded content of blocks indicates activities that pertain to pattern acquisition. Dashed borders and connector lines indicate pattern acquisition proper while dotted lines and connectors indicate partial relation to pattern acquisition simultaneously with partial relation to sequence alignment-based database searches.

Figure 2. Pragmatic inference and sequence pattern acquisition. Broadly specified biological knowledge about biomolecular sequences and structures, as well as from outside sequences and structures, is involved in every step of alphabet determination. Once sequence motifs (meaningful pattern-generating descriptors of sequences) are determined, the alphabets of patterns can be used for sequence analysis and comparison. The most important classes of sequence patterns are mentioned in shaded boxes with broken borders. The dotted borders of shaded boxes indicate classes of patterns that are often used in sequence analysis but are usually less significant as functional ‘signatures’ (correlates) of sequences.

Figure 3. Examples of periodic and quasiperiodic (nucleotide) sequence patterns. Motifs taken into account are printed in bold.

Figure 4. Example of pattern acquisition via analysis of short oligonucleotide distance charts. All four distance charts were made for large collections of sufficiently long intron and exon sequences from several eukaryotic genomes (primarily human, mouse and fruit fly). (a) Distance charts between two instances of the same nonhomopolymeric dinucleotide AC (charts are almost identical for 11 other nonhomopolymeric dinucleotides). (b) Nearest (shortest) distance charts between two instances of nonhomopolymeric dinucleotide AC. (c) Distance charts between two instances of the same mirror-symmetric trinucleotide that begins with nonhomopolymeric dinucleotides whose distance and shortest distance charts are A and B respectively. In our examples the trinucleotide is ACA but all other mirror-symmetric trinucleotides display very similar charts. (d) Shortest distance charts between two instances of the same mirror-symmetric trinucleotide. A host of significant defining patterns (descriptors) can be inferred from studying charts (a)–(d). For instance the fact that dinucleotides in introns occur at preferred distance of 0, 2, 4, and generally 2n (n=1, 2, 3,) while the preferred shortest distance is 0 indicates that tandem repeats of nonhomopolymeric dinucleotides are a predominant, defining, pattern in introns. The fact that mirror-symmetric, nonhomopolymeric, trinucleotides display 3-base quasiperiodicity in exons but not in introns is a clear confirmation of triplet nature of the genetic code (avoidance of stop codons in the protein-encoding reading frame). Even if the genetic code was not known we could easily conclude that trinucleotides and their 3-base quasiperiodicity constitute defining, function-associated, patterns in exons but not in introns.

Figure 5. Lengths of sequences that are required for statistical analyses of k-grams (k=1, 2,, 10) over three elementary alphabets of sizes 2, 4 and 20 letters. The alphabets of size 2 and 4 correspond to typical representations of nucleotide sequences while the alphabet of size 20 is used for primary structure of proteins. The lengths of the sequences have been evaluated from the so-called statistics of blanks (Kullback, 1976) for Bernoulli texts. According to this statistics the expected number of ‘blanks’ (absent symbols) in a text of length L over an alphabet of size n is


where p(i) stands for the probability of the ith letter. In Bernoulli texts, probabilities p(i) are all equal to 1/n and therefore the number of letters absent by chance alone is B¢(L) = n[1 – (1/n)]L. One can set B¢(L) close to 0 (we used the value 0.1 for this figure) and then calculate minimum value of L₀ that will be large enough not to affect the number of missing letters. Only those sequences with lengths greater than or equal to L₀ are sufficiently long to be suitable for statistical analysis based on k-gram frequency counts.