title: The combinatorics of overlapping genes.
abstract: Overlapping genes exist in all domains of life and are much more abundant than expected upon their first discovery in the late 1970s. Assuming that the reference gene is read in frame +0, an overlapping gene can be encoded in two reading frames in the sense strand, denoted by +1 and +2, and in three reading frames in the opposite strand, denoted by -0, -1, and -2. This motivated numerous researchers to study the constraints induced by the genetic code on the various overlapping frames, mostly based on information theory. Our focus in this paper is on the constraints induced on two overlapping genes in terms of amino acids, as well as polypeptides. We show that simple linear constraints bind the amino-acid composition of two proteins encoded by overlapping genes. Novel constraints are revealed when polypeptides are considered, and not just single amino acids. For example, in double-coding sequences with an overlapping reading frame -2, each Tyrosine (denoted as Tyr or Y) in the overlapping frame overlaps a Tyrosine in the reference frame +0 (and reciprocally), whereas specific words (e.g. YY) never occur. We thus distinguish between null constraints (YY = 0 in frame -2) and non-null constraints (Y in frame +0 ⇔ Y in frame -2). Our equivalence-based constraints are symmetrical and thus enable the characterization of the joint composition of overlapping proteins. We describe several formal frameworks and a graph algorithm to characterize and compute these constraints. As expected, the degrees of freedom left by these constraints vary drastically among the different overlapping frames. Interestingly, the biological meaning of constraints induced on two overlapping proteins (hydropathy, forbidden di-peptides, expected overlap length …) is also specific to the reading frame. We study the combinatorics of these constraints for overlapping polypeptides of length n, pointing out that, (i) except for frame -2, non-null constraints are deduced from the amino-acid (length = 1) constraints and (ii) null constraints are deduced from the di-peptide (length = 2) constraints. These results yield support for understanding the mechanisms and evolution of overlapping genes, and for developing novel overlapping gene detection methods.
authors.affiliation: IMAG, UMR 5149 - CNRS & Université de Montpellier, France; CPBS, UMR 5236 - CNRS & Université de Montpellier, France; Université Paul Valéry Montpellier 3, France; Institut de Biologie Computationnelle, LIRMM, UMR 5506 - CNRS & Université de Montpellier, France. Electronic address: sophie.lebre@umontpellier.fr.
authors.forename: Sophie
authors.initials: S
authors.lastname: Lèbre
authors.affiliation: Institut de Biologie Computationnelle, LIRMM, UMR 5506 - CNRS & Université de Montpellier, France; Unité Bioinformatique Evolutive, C3BI, USR 3756 - Institut Pasteur & CNRS, Paris, France.
authors.forename: Olivier
authors.initials: O
authors.lastname: Gascuel
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence / Q000235:genetics*; D000818:Animals; D005075:Biological Evolution; D005807:Genes, Overlapping; D006801:Humans; D016366:Open Reading Frames; D011506:Proteins / Q000235:genetics*
chemical_list: D011506:Proteins
keywords: Amino-acid composition; Codon usage; Double-coding sequences; Genetic code; Linear and logical constraints; Overlapping gene detection; Stop codons