Linguistic complexity of protein sequences as compared to texts of human languages

The determinants of the rarity of nucleic and peptide short sequences in nature

The prevalence of nucleic and peptide short sequences across organismal genomes and proteomes has not been thoroughly investigated. We examined 45 785 reference genomes and 21 871 reference proteomes, spanning archaea, bacteria, eukaryotes and viruses to calculate the rarity of short sequences in them. To capture this, we developed a metric of the rarity of each sequence in nature, the rarity index. We find that the frequency of certain dipeptides in rare oligopeptide sequences is hundreds of times lower than expected, which is not the case for any dinucleotides. We also generate predictive regression models that infer the rarity of nucleic and proteomic sequences across nature or within each domain of life and viruses separately. When examining each of the three domains of life and viruses separately, the R² performance of the model predicting rarity for 5-mer peptides from mono- and dipeptides ranged between 0.814 and 0.932. A separate model predicting rarity for 10-mer oligonucleotides from mono- and dinucleotides achieved R² performance between 0.408 and 0.606. Our results indicate that the mono- and dinucleotide composition of nucleic sequences and the mono- and dipeptide composition of peptide sequences can explain a significant proportion of the variance in their frequencies in nature.

Small Insertions and Deletions Drive Genomic Plasticity during Adaptive Evolution of Yersinia pestis

The life cycle of Yersinia pestis has changed a lot to adapt to flea-borne transmission since it evolved from an enteric pathogen, Yersinia pseudotuberculosis. Small insertions and deletions (indels), especially frameshift mutations, can have major effects on phenotypes and contribute to virulence and host adaptation through gene disruption and inactivation. Here, we analyzed 365 Y. pestis genomes and identified 2,092 genome-wide indels on the core genome. As recently reported in Mycobacterium tuberculosis, we also detected "indel pockets" in Y. pestis, with average complexity scores declining around indel positions, which we speculate might also exist in other prokaryotes. Phylogenic analysis showed that indel-based phylogenic tree could basically reflect the phylogenetic relationships of major phylogroups in Y. pestis, except some inconsistency around the Big Bang polytomy. We observed 83 indels arising in the trunk of the phylogeny, which played a role in accumulation of pseudogenes related to key metabolism and putatively pathogenicity. We also discovered 32 homoplasies at the level of phylogroups and 7 frameshift scars (i.e., disrupted reading frame being rescued by a second frameshift). Additionally, our analysis showed evidence of parallel evolution at the level of genes, with sspA, rpoS, rnd, and YPO0624, having enriched mutations in Brazilian isolates, which might be advantageous for Y. pestis to cope with fluctuating environments. The diversified selection signals observed here demonstrates that indels are important contributors to the adaptive evolution of Y. pestis. Meanwhile, we provide potential targets for further exploration, as some genes/pseudogenes with indels we focus on remain uncharacterized. IMPORTANCE Yersinia pestis, the causative agent of plague, is a highly pathogenic clone of Yersinia pseudotuberculosis. Previous genome-wide SNP analysis provided few adaptive signatures during its evolution. Here by investigating 365 public genomes of Y. pestis, we give a comprehensive overview of general features of genome-wide indels on the core genome and their roles in Y. pestis evolution. Detection of "indel pockets," with average complexity scores declining around indel positions, in both Mycobacterium tuberculosis and Y. pestis, gives us a clue that this phenomenon might appear in other bacterial genomes. Importantly, the identification of four different forms of selection signals in indels would improve our understanding on adaptive evolution of Y. pestis, and provide targets for further physiological mechanism researches of this pathogen. As evolutionary research based on genome-wide indels is still rare in bacteria, our study would be a helpful reference in deciphering the role of indels in other species.

Reversible gene silencing through frameshift indels and frameshift scars provide adaptive plasticity for Mycobacterium tuberculosis

Mycobacterium tuberculosis can adapt to changing environments by non-heritable mechanisms. Frame-shifting insertions and deletions (indels) may also participate in adaptation through gene disruption, which could be reversed by secondary introduction of a frame-restoring indel. We present ScarTrek, a program that scans genomic data for indels, including those that together disrupt and restore a gene's reading frame, producing "frame-shift scars" suggestive of reversible gene inactivation. We use ScarTrek to analyze 5977 clinical M. tuberculosis isolates. We show that indel frequency inversely correlates with genomic linguistic complexity and varies with gene-position and gene-essentiality. Using ScarTrek, we detect 74 unique frame-shift scars in 48 genes, with a 3.74% population-level incidence of unique scar events. We find multiple scars in the ESX-1 gene cluster. Six scars show evidence of convergent evolution while the rest shared a common ancestor. Our results suggest that sequential indels are a mechanism for reversible gene silencing and adaptation in M. tuberculosis.

Otaki J. Search for Human-Specific Proteins Based on Availability Scores of Short Constituent Sequences: Identification of a WRWSH Protein in Human Testis

Little is known about protein sequences unique in humans. Here, we performed alignment-free sequence comparisons based on the availability (frequency bias) of short constituent amino acid (aa) sequences (SCSs) in proteins to search for human-specific proteins. Focusing on 5-aa SCSs (pentats), exhaustive comparisons of availability scores among the human proteome and other nine mammalian proteomes in the nonredundant (nr) database identified a candidate protein containing WRWSH, here called FAM75, as human-specific. Examination of various human genome sequences revealed that FAM75 had genomic DNA sequences for either WRWSH or WRWSR due to a single nucleotide polymorphism (SNP). FAM75 and its related protein FAM205A were found to be produced through alternative splicing. The FAM75 transcript was found only in humans, but the FAM205A transcript was also present in other mammals. In humans, both FAM75 and FAM205A were expressed specifically in testis at the mRNA level, and they were immunohistochemically located in cells in seminiferous ducts and in acrosomes in spermatids at the protein level, suggesting their possible function in sperm development and fertilization. This study highlights a practical application of SCS-based methods for protein searches and suggests possible contributions of SNP variants and alternative splicing of FAM75 to human evolution.

Deamination gradients within codons after 1<->2 position swap predict amino acid hydrophobicity and parallel β-sheet conformational preference

Deaminations C->T and A->G are frequent mutations producing nucleotide content gradients across genomes proportional to singlestrandedness during replication/transcription. Hence, within single codons, deamination risks increase from first to third codon positions, while second codon positions are functionally most crucial. Here genetic codes are analyzed assuming that after anticodons protected codons from deaminations, first and second codon positions swapped (N2N1N3->N1N2N3), with lowest deamination risks for N2 in presumed primitive N2N1N3 codons. N2N1N3, not standard N1N2N3, codon structure minimizes deaminations inversely proportionally to cognate amino acid hydrophobicity and parallel betasheet conformational preference. For N1N2N3, deamination minimization increases with genetic code integration order of cognate amino acids: during the presumed N2N1N3->N1N2N3 codon structure transition, protein synthesis combined direct codon-amino acid interactions for late amino acids and tRNA-based translation for early amino acids. Hence N2N1N3 codons would correspond to tRNA-free translation by spontaneous codon-amino acid affinities, and tRNA-mediated translation presumably caused N2N1N3->N1N2N3 swaps. Results show that rational, not arbitrary rules link codon and amino acid structures. Some analyses detect mitochondrial RNAs and peptides in public data corresponding to systematic position swaps, suggesting occasional swapping polymerase activity.

Localized Context-Dependent Effects of the "Ambush" Hypothesis: More Off-Frame Stop Codons Downstream of Shifty Codons

The ambush hypothesis speculates that off-frame stop codons increase translational efficiency after ribosomal frameshifts by stopping early frameshifted translation. Some evidences fit this hypothesis: (1) synonymous codon usages increase with their potential contribution to off-frame stops; (2) the genetic code assigns frequent amino acids to codon families contributing to off-frame stops; (3) positive biases for off-frame stops (AT rich) occur despite adverse nucleotide (GC) biases; and (4) mitochondrial off-frame stop codon densities increase with ribosomal structural instability, potential proxy of frameshift frequencies. In this study, analyses of vertebrate mitogenes and tRNA synthetase genes from all superkingdoms and viruses test a new prediction of the ambush hypothesis: sequences immediately downstream of frameshift-inducing homopolymer codons (AAA, CCC, GGG, and TTT) are off-frame stop rich. Codons immediately downstream of homopolymer codons form more than average off-frame stops, biases are stronger than for corresponding upstream distances and for any other group of synonymous codons. Sequences downstream of that high-density region are off-frame stop depleted. This decrease suggests that off-frame stops, combined with suppressor tRNAs regulate translation of overlapping coding sequences. Results show the predictive power of the ambush hypothesis, from macroevolutionary (genetic code structure) to detailed gene sequence anatomy.

Kinetic Selection of Template Polymer with Complex Sequences

The emergence and maintenance of polymers with complex sequences pose a major question in the study of the origin of life. To answer this, we study a model polymerization reaction, where polymers are synthesized by stepwise ligation from two types of monomers, catalyzed by a long polymer as a template. Direct stochastic simulation and dynamical systems analysis reveal that the most dominant polymer sequence in a population successively changes, depending on the flow rate of monomers to the system, with more complex sequences selected at a lower flow rate. We discuss the relevance of this kinetic sequence selection through nonequilibrium flow to the origin of complex polymers.

Bijective codon transformations show genetic code symmetries centered on cytosine's coding properties

Homology of some RNAs with template DNA requires systematic exchanges between nucleotides. Such exchanges produce 'swinger' RNA along 23 bijective transformations (nine symmetric, X ↔ Y; and 14 asymmetric, X → Y → Z → X, for example A ↔ C and A → C → G → A, respectively). Here, analyses compare amino acids coded by swinger-transformed codons to those coded by untransformed codons, defining coding invariance after transformations. Swinger transformations cluster according to coding invariance in four groups characterized by transformations into cytosine (C = C, T → C, A → C, and G → C). C's central mutational coding role shows that swinger transformations constrained genetic code genesis. Coding invariance post-transformations correlate positively/negatively with mitochondrial swinger transcription/lepidosaurian body temperature. Presumably, low/high temperatures stabilize/revert rare swinger polymerization modes, producing long swinger sequences/point mutations, respectively. Coding invariance after swinger transformations might compensate effects of swinger polymerizations in species with low body temperatures. Hypothetically, swinger transcription increased coding potential of RNA self-replicating protolife systems under heating/cooling cycles.

Protein lipograms

Linguistic analysis of protein sequences is an underexploited technique. Here, we capitalize on the concept of the lipogram to characterize sequences at the proteome levels. A lipogram is a literary composition which omits one or more letters. A protein lipogram likewise omits one or more types of amino acid. In this article, we establish a usable terminology for the decomposition of a sequence collection in terms of the lipogram. Next, we characterize Uniref50 using a lipogram decomposition. At the global level, protein lipograms exhibit power-law properties. A clear correlation with metabolic cost is seen. Finally, we use the lipogram construction to assign proteomes to the four branches of the tree-of-life: archaea, bacteria, eukaryotes and viruses. We conclude from this pilot study that the lipogram demonstrates considerable potential as an additional tool for sequence analysis and proteome classification.

Reviewing evidence for systematic transcriptional deletions, nucleotide exchanges, and expanded codons, and peptide clusters in human mitochondria

Polymerization sometimes transforms sequences by (a) systematic deletions of mono-, dinucleotides after trinucleotides, or (b) 23 systematic nucleotide exchanges (9 symmetric, X<>Y, e.g. G<>T, 14 asymmetric, X > Y > Z > X, e.g. A > G > T > A), producing del- and swinger RNAs. Some peptides correspond to del- and swinger RNA translations, also according to tetracodons, codons expanded by a silent nucleotide. Here new analyzes assume different proteolytic patterns, partially alleviating false negative peptide detection biases, expanding noncanonical mitoproteome profiles. Mito-genomic, -transcriptomic and -proteomic evidence for noncanonical transcriptions and translations are reviewed and clusters of del- and swinger peptides (also along tetracodons) are described. Noncanonical peptide clusters indicate regulated expression of cryptically encoded mitochondrial protein coding genes. These candidate noncanonical proteins don't resemble known proteins.

Evolution of Nucleotide Punctuation Marks: From Structural to Linear Signals

We present an evolutionary hypothesis assuming that signals marking nucleotide synthesis (DNA replication and RNA transcription) evolved from multi- to unidimensional structures, and were carried over from transcription to translation. This evolutionary scenario presumes that signals combining secondary and primary nucleotide structures are evolutionary transitions. Mitochondrial replication initiation fits this scenario. Some observations reported in the literature corroborate that several signals for nucleotide synthesis function in translation, and vice versa. (a) Polymerase-induced frameshift mutations occur preferentially at translational termination signals (nucleotide deletion is interpreted as termination of nucleotide polymerization, paralleling the role of stop codons in translation). (b) Stem-loop hairpin presence/absence modulates codon-amino acid assignments, showing that translational signals sometimes combine primary and secondary nucleotide structures (here codon and stem-loop). (c) Homopolymer nucleotide triplets (AAA, CCC, GGG, TTT) cause transcriptional and ribosomal frameshifts. Here we find in recently described human mitochondrial RNAs that systematically lack mono-, dinucleotides after each trinucleotide (delRNAs) that delRNA triplets include 2x more homopolymers than mitogenome regions not covered by delRNA. Further analyses of delRNAs show that the natural circular code X (a little-known group of 20 translational signals enabling ribosomal frame retrieval consisting of 20 codons {AAC, AAT, ACC, ATC, ATT, CAG, CTC, CTG, GAA, GAC, GAG, GAT, GCC, GGC, GGT, GTA, GTC, GTT, TAC, TTC} universally overrepresented in coding versus other frames of gene sequences), regulates frameshift in transcription and translation. This dual transcription and translation role confirms for X the hypothesis that translational signals were carried over from transcriptional signals.

Parasitism as the main factor shaping peptide vocabularies in current organisms

Self/non-self-discrimination by vertebrate immune systems is based on the recognition of the presence of peptides in proteins of a parasite that are not contained in the proteins of a host. Therefore, a reduction of the number of 'words' in its own peptide vocabulary could be an efficient evolutionary strategy of parasites for escaping recognition. Here, we compared peptide vocabularies of 30 endoparasitic and 17 free-living unicellular organisms and also eight multicellular parasitic and 16 multicellular free-living organisms. We found that both unicellular and multicellular parasites used a significantly lower number of different pentapeptides than free-living controls. Impoverished pentapeptide vocabularies in parasites were observed across all five clades that contain both the parasitic and free-living species. The effect of parasitism on a number of peptides used in an organism's proteins is larger than effects of all other studied factors, including the size of a proteome, the number of encoded proteins, etc. This decrease of pentapeptide diversity was partly compensated for by an increased number of hexapeptides. Our results support the hypothesis of parasitism-associated reduction of peptide vocabulary and suggest that T-cell receptors mostly recognize the five amino acids-long part of peptides that are presented in the groove of major histocompatibility complex molecules.

Natural mitochondrial proteolysis confirms transcription systematically exchanging/deleting nucleotides, peptides coded by expanded codons

Protein sequences have higher linguistic complexities than human languages. This indicates undeciphered multilayered, overprinted information/genetic codes. Some superimposed genetic information is revealed by detections of transcripts systematically (a) exchanging nucleotides (nine symmetric, e.g. A<->C, fourteen asymmetric, e.g. A->C->G->A, swinger RNAs) translated according to tri-, tetra- and pentacodons, and (b) deleting mono-, dinucleotides after each trinucleotide (delRNAs). Here analyses of two independent proteomic datasets considering natural proteolysis confirm independently translation of these non-canonical RNAs, also along tetra- and pentacodons, increasing coverage of putative, cryptically encoded proteins. Analyses assuming endoproteinase GluC and elastase digestions (cleavages after residues D, E, and A, L, I, V, respectively) detect additional peptides colocalizing with detected non-canonical RNAs. Analyses detect fewer peptides matching GluC-, elastase- than trypsin-digestions: artificial trypsin-digestion outweighs natural proteolysis. Results suggest occurrences of complete proteins entirely matching non-canonical, superimposed encoding(s). Protein-coding after bijective transformations could explain genetic code symmetries, such as along Rumer's transformation.

Unbiased Mitoproteome Analyses Confirm Non-canonical RNA, Expanded Codon Translations

Proteomic MS/MS mass spectrometry detections are usually biased towards peptides cleaved by experimentally added digestion enzyme(s). Hence peptides resulting from spontaneous degradation and natural proteolysis usually remain undetected. Previous analyses of tryptic human proteome data (cleavage after K, R) detected non-canonical tryptic peptides translated according to tetra- and pentacodons (codons expanded by silent mono- and dinucleotides), and from transcripts systematically (a) deleting mono-, dinucleotides after trinucleotides (delRNAs), (b) exchanging nucleotides according to 23 bijective transformations. Nine symmetric and fourteen asymmetric nucleotide exchanges (X ↔ Y, e.g. A ↔ C; and X → Y → Z → X, e.g. A → C → G → A) produce swinger RNAs. Here unbiased reanalyses of these proteomic data detect preferentially non-canonical tryptic peptides despite assuming random cleavage. Unbiased analyses couldn't reconstruct experimental tryptic digestion if most detected non-canonical peptides were false positives. Detected non-tryptic non-canonical peptides map preferentially on corresponding, previously described non-canonical transcripts, as for tryptic non-canonical peptides. Hence unbiased analyses independently confirm previous trypsin-biased analyses that showed translations of del- and swinger RNA and expanded codons. Accounting for natural proteolysis completes trypsin-biased mitopeptidome analyses, independently confirms non-canonical transcriptions and translations.

Google matrix analysis of DNA sequences

For DNA sequences of various species we construct the Google matrix [Formula: see text] of Markov transitions between nearby words composed of several letters. The statistical distribution of matrix elements of this matrix is shown to be described by a power law with the exponent being close to those of outgoing links in such scale-free networks as the World Wide Web (WWW). At the same time the sum of ingoing matrix elements is characterized by the exponent being significantly larger than those typical for WWW networks. This results in a slow algebraic decay of the PageRank probability determined by the distribution of ingoing elements. The spectrum of [Formula: see text] is characterized by a large gap leading to a rapid relaxation process on the DNA sequence networks. We introduce the PageRank proximity correlator between different species which determines their statistical similarity from the view point of Markov chains. The properties of other eigenstates of the Google matrix are also discussed. Our results establish scale-free features of DNA sequence networks showing their similarities and distinctions with the WWW and linguistic networks.

A frequency-based linguistic approach to protein decoding and design: Simple concepts, diverse applications, and the SCS Package

Protein structure and function information is coded in amino acid sequences. However, the relationship between primary sequences and three-dimensional structures and functions remains enigmatic. Our approach to this fundamental biochemistry problem is based on the frequencies of short constituent sequences (SCSs) or words. A protein amino acid sequence is considered analogous to an English sentence, where SCSs are equivalent to words. Availability scores, which are defined as real SCS frequencies in the non-redundant amino acid database relative to their probabilistically expected frequencies, demonstrate the biological usage bias of SCSs. As a result, this frequency-based linguistic approach is expected to have diverse applications, such as secondary structure specifications by structure-specific SCSs and immunological adjuvants with rare or non-existent SCSs. Linguistic similarities (e.g., wide ranges of scale-free distributions) and dissimilarities (e.g., behaviors of low-rank samples) between proteins and the natural English language have been revealed in the rank-frequency relationships of SCSs or words. We have developed a web server, the SCS Package, which contains five applications for analyzing protein sequences based on the linguistic concept. These tools have the potential to assist researchers in deciphering structurally and functionally important protein sites, species-specific sequences, and functional relationships between SCSs. The SCS Package also provides researchers with a tool to construct amino acid sequences de novo based on the idiomatic usage of SCSs.

Word decoding of protein amino Acid sequences with availability analysis: a linguistic approach

The amino acid sequences of proteins determine their three-dimensional structures and functions. However, how sequence information is related to structures and functions is still enigmatic. In this study, we show that at least a part of the sequence information can be extracted by treating amino acid sequences of proteins as a collection of English words, based on a working hypothesis that amino acid sequences of proteins are composed of short constituent amino acid sequences (SCSs) or "words". We first confirmed that the English language highly likely follows Zipf's law, a special case of power law. We found that the rank-frequency plot of SCSs in proteins exhibits a similar distribution when low-rank tails are excluded. In comparison with natural English and "compressed" English without spaces between words, amino acid sequences of proteins show larger linear ranges and smaller exponents with heavier low-rank tails, demonstrating that the SCS distribution in proteins is largely scale-free. A distribution pattern of SCSs in proteins is similar among species, but species-specific features are also present. Based on the availability scores of SCSs, we found that sequence motifs are enriched in high-availability sites (i.e., "key words") and vice versa. In fact, the highest availability peak within a given protein sequence often directly corresponds to a sequence motif. The amino acid composition of high-availability sites within motifs is different from that of entire motifs and all protein sequences, suggesting the possible functional importance of specific SCSs and their compositional amino acids within motifs. We anticipate that our availability-based word decoding approach is complementary to sequence alignment approaches in predicting functionally important sites of unknown proteins from their amino acid sequences.

RNAexinv: An extended inverse RNA folding from shape and physical attributes to sequences

Background

RNAexinv is an interactive java application that performs RNA sequence design, constrained to yield a specific RNA shape and physical attributes. It is an extended inverse RNA folding program with the rationale behind that the generated sequences should not only fold into a desired structure, but they should also exhibit favorable attributes such as thermodynamic stability and mutational robustness. RNAexinv considers not only the secondary structure in order to design sequences, but also the mutational robustness and the minimum free energy. The sequences that are generated may not fully conform with the given RNA secondary structure, but they will strictly conform with the RNA shape of the given secondary structure and thereby take into consideration the recommended values of thermodynamic stability and mutational robustness that are provided.

Results

The output consists of designed sequences that are generated by the proposed method. Selecting a sequence displays the secondary structure drawings of the target and the predicted fold of the sequence, including some basic information about the desired and achieved thermodynamic stability and mutational robustness. RNAexinv can be used successfully without prior experience, simply specifying an initial RNA secondary structure in dot-bracket notation and numerical values for the desired neutrality and minimum free energy. The package runs under LINUX operating system. Secondary structure predictions are performed using the Vienna RNA package.

Conclusions

RNAexinv is a user friendly tool that can be used for RNA sequence design. It is especially useful in cases where a functional stem-loop structure of a natural sequence should be strictly kept in the designed sequences but a distant motif in the rest of the structure may contain one more or less nucleotide at the expense of another, as long as the global shape is preserved. This allows the insertion of physical observables as constraints. RNAexinv is available at http://www.cs.bgu.ac.il/~RNAexinv.

Viruses are essential agents within the roots and stem of the tree of life

In contrast with former definitions of life limited to membrane-bound cellular life forms which feed, grow, metabolise and replicate (i) a role of viruses as genetic symbionts, (ii) along with peripheral phenomena such as cryptobiosis and (iii) the horizontal nature of genetic information acquisition and processing broaden our view of the tree of life. Some researchers insist on the traditional textbook conviction of what is part of the community of life. In a recent review [Moreira, D., Lopez-Garcia, P., 2009. Ten reasons to exclude viruses from the tree of life. Nat. Rev. Microbiol. 7, 306-311.] they assemble four main arguments which should exclude viruses from the tree of life because of their inability to self-sustain and self-replicate, their polyphyly, the cellular origin of their cell-like genes and the volatility of their genomes. In this article we will show that these features are not coherent with current knowledge about viruses but that viral agents play key roles within the roots and stem of the tree of life.

Folding at the rhythm of the rare codon beat

The persistent difficulties in the production of protein at high levels in heterologous systems, as well as the inability to understand pathologies associated with protein aggregation, highlight our limited knowledge on the mechanisms of protein folding in vivo. Attempts to improve yield and quality of recombinant proteins are diverse, frequently involving optimization of the cell growth temperature, the use of synonymous codons and/or the co-expression of tRNAs, chaperones and folding catalysts among others. Although protein secondary structure can be determined largely by the amino acid sequence, protein folding within the cell is affected by a range of factors beyond amino acid sequence. The folding pathway of a nascent polypeptide can be affected by transient interactions with other proteins and ligands, the ribosome, translocation through a pore membrane, redox conditions, among others. The translation rate as well as the translation machinery itself can dramatically affect protein folding, and thus the structure and function of the protein product. This review addresses current efforts to better understand how the use of synonymous codons in the mRNA and the availability of tRNAs can modulate translation kinetics, affecting the folding, the structure and the biological activity of proteins.

Reconstruction of natural RNA sequences from RNA shape, thermodynamic stability, mutational robustness, and linguistic complexity by evolutionary computation

The process of designing novel RNA sequences by inverse RNA folding, available in tools such as RNAinverse and InfoRNA, can be thought of as a reconstruction of RNAs from secondary structure. In this reconstruction problem, no physical measures are considered as additional constraints that are independent of structure, aside of the goal to reach the same secondary structure as the input using energy minimization methods. An extension of the reconstruction problem can be formulated since in many cases of natural RNAs, it is desired to analyze the sequence and structure of RNA molecules using various physical quantifiable measures. In prior works that used secondary structure predictions, it has been shown that natural RNAs differ significantly from random RNAs in some of these measures. Thus, we relax the problem of reconstructing RNAs from secondary structure into reconstructing RNAs from shapes, and in turn incorporate physical quantities as constraints. This allows for the design of novel RNA sequences by inverse folding while considering various physical quantities of interest such as thermodynamic stability, mutational robustness, and linguistic complexity. At the expense of altering the number of nucleotides in stems and loops, for example, physical measures can be taken into account. We use evolutionary computation for the new reconstruction problem and illustrate the procedure on various natural RNAs.

The performances of the chi-square test and complexity measures for signal recognition in biological sequences

With large amounts of experimental data, modern molecular biology needs appropriate methods to deal with biological sequences. In this work, we apply a statistical method (Pearson's chi-square test) to recognize the signals appear in the whole genome of the Escherichia coli. To show the effectiveness of the method, we compare the Pearson's chi-square test with linguistic complexity on the complete genome of E. coli. The results suggest that Pearson's chi-square test is an efficient method for distinguishing genes (coding regions) form pseudogenes (noncoding regions). On the other hand, the performance of the linguistic complexity is much lower than the chi-square test method. We also use the Pearson's chi-square test method to determine which parts of the Open Reading Frame (ORF) have significant effect on discriminating genes form pseudogenes. Moreover, different complexity measures and Pearson's chi-square test applied on the genes with high value of Pearson's chi-square statistic. We also compute the measures on homologous of these genes. The results illustrate that there is a region near the start codon with high value of chi-square statistic and low complexity that is conserve between homologous genes.

Protein linguistics — a grammar for modular protein assembly?

The correspondence between biology and linguistics at the level of sequence and lexical inventories, and of structure and syntax, has fuelled attempts to describe genome structure by the rules of formal linguistics. But how can we define protein linguistic rules? And how could compositional semantics improve our understanding of protein organization and functional plasticity?

Structure-related statistical singularities along protein sequences: a correlation study

A data set composed of 1141 proteins representative of all eukaryotic protein sequences in the Swiss-Prot Protein Knowledge base was coded by seven physicochemical properties of amino acid residues. The resulting numerical profiles were submitted to correlation analysis after the application of a linear (simple mean) and a nonlinear (Recurrence Quantification Analysis, RQA) filter. The main RQA variables, Recurrence and Determinism, were subsequently analyzed by Principal Component Analysis. The RQA descriptors showed that (i) within protein sequences is embedded specific information neither present in the codes nor in the amino acid composition and (ii) the most sensitive code for detecting ordered recurrent (deterministic) patterns of residues in protein sequences is the Miyazawa-Jernigan hydrophobicity scale. The most deterministic proteins in terms of autocorrelation properties of primary structures were found (i) to be involved in protein-protein and protein-DNA interactions and (ii) to display a significantly higher proportion of structural disorder with respect to the average data set. A study of the scaling behavior of the average determinism with the setting parameters of RQA (embedding dimension and radius) allows for the identification of patterns of minimal length (six residues) as possible markers of zones specifically prone to inter- and intramolecular interactions.

Multi-dimensional linguistic complexity

Linguistic complexity is a simple and elegant way of calculating complexity of strings of data. It is based on the concept that the greater the vocabulary one uses, the more complex the data. Until now, it has been used only on one-dimensional data, such as DNA and protein sequences and various human language texts. The basic definition can be extended to higher dimensions, thus allowing a practical and simple calculation of linguistic complexity of images, 3D objects and other multi-dimensional data. A simple extension of linguistic complexity is introduced, followed by 2D presentations and a discussion of parametric considerations. An example of linguistic complexity calculations, demonstrating its image processing and medical diagnostic power is presented. The subjects of this paper are patent application pending.

The language of genes

Linguistic metaphors have been woven into the fabric of molecular biology since its inception. The determination of the human genome sequence has brought these metaphors to the forefront of the popular imagination, with the natural extension of the notion of DNA as language to that of the genome as the 'book of life'. But do these analogies go deeper and, if so, can the methods developed for analysing languages be applied to molecular biology? In fact, many techniques used in bioinformatics, even if developed independently, may be seen to be grounded in linguistics. Further interweaving of these fields will be instrumental in extending our understanding of the language of life.

Special factors in biological strings

Biological macromolecules such as DNA, RNA, and proteins can be regarded as finite sequences of symbols (or words) over a finite alphabet. In this paper, we refer to DNA (RNA) sequences which are words on a four-letter alphabet. A comparison is made between some "genes", or fragments of them, with random sequences or random reshuffled sequences on the same alphabet and having the same length. Some combinatorial techniques of analysis of finite words are developed. A crucial role in the comparison is played by the so-called special factors of a given word. In all the analysed DNA (RNA) fragments the distribution on the length of the number of right (left) special factors differs, in a very typical way, from the corresponding distribution in a string on the same alphabet and having the same length generated by a random source or obtained by making a random alteration (=shuffling) of the original string. This kind of change is irrespective of the length in the range that we have considered <2650 bp and of the phylogenetic origin of the fragment.

Symmetry breaking and adaptation: evidence from a 'toy model' of a virus

We argue that an induced breaking of the genetic synonym symmetry due to the action of genetic operators such as mutation can enhance the adaptability of a species to changes in the environment. In the case of a virus, the claim is that the codon bias in the neutralization epitope improves the virus' ability to generate mutants that evade the induced immune response. We support our claim with a simple 'toy model' of a viral epitope evolving in competition with the immune system. The effective selective advantage of a higher mutability leads to a dominance of codons that favor non-synonymous mutations. As further evidence we present a simple model for a genetic regulatory network that leads to adaptive evolution in a population of giraffes by means of an induced symmetry breaking rather than through any direct selective advantage.

Sequence complexity and DNA curvature

A linguistic complexity measure was applied to the complete genomes of HIV-1, Escherichia coli, Bacillus subtilis, Haemophilus influenzae, Mycoplasma genitalium, and to long human and yeast genomic fragments. Complexity values averaged over entire genomic sequences were compared, as were predicted average values of intrinsic DNA curvature. We found that both the most curved and the least complex fragments are located preferentially in non-coding parts of the genome. Analysis of location of the most curved and the simplest regions in bacteria showed that the low-complexity segments are preferentially located in close proximity to the highly curved sequences, which are, in turn, placed from 100 to 200 bases upstream to the start of the nearest coding sequence. We conclude that the parallel analysis of sequence complexity and DNA curvature might provide important information about sequence-structure-function relationship in genomes.

The "clustered structure" of the purines/pyrimidines distribution in DNA distinguishes systematically between coding and non-coding sequences

A method allowing to measure the inhomogeneous distribution of purines/pyrimidines in nucleotide sequences is developed. We show that this measure relates to the coding or non-coding character of the considered sequence. Coding sequences present a near to the random Pu or Py distribution. This property is shared by both protein-coding DNA and functional RNA-coding DNA. Non-coding sequences present a highly clustered inhomogeneity. We propose the hypothesis, corroborated with appropriate computer simulations, that this is due to the action of various transposition events accumulated for long time periods.