Search

We present the variable length local decoding, a method which augments the alphabet of a sequence or a set of sequences. Roughly speaking, the approach distinguishes several types of symbols/nucleotides according to their contexts in the sequences. These contexts have variable lengths and are defined from a prefix code.We first give an original algorithm computing the decoding with a complexity linear both in time and memory space. Next, the approach is applied to alignment-free sequence comparison. We give a heuristic way to select context lengths relevant to this question. The comparison of sequences itself is based on the composition in “augmented” symbols of their variable length local decodings. The results of this comparison are illustrated on a biological alignment.

A computer-assisted analysis was made of 24 complete nucleotide sequences selected from the vertebrate retroviruses to represent the ten viral groups. The conclusions of this analysis extend and strengthen the previously made hypothesis on the Moloney murine leukemia virus: The evolution of the nucleotide sequence appears to have occurred mainly through at least three overlapping levels of duplication: (1) The distributions of overrepresented (3-6)-mers are consistent with the universal rule of a trend toward TG/CT excess and with the persistence of a certain degree of symmetry between the two strands of DNA. This suggests one or several original tandemly repeated sequences and some inverted duplications. (2) The existence of two general core consensuses at the level of these (3-6)-mers supports the hypothesis of a common evolutionary origin of vertebrate retroviruses. Consensuses more specific to certain sequences are compatible with phylogenetic trees established independently. The consensuses could correspond to intermediary evolutionary stages. (3) Most of the (3-6)-mers with a significantly higher than average frequency appear to be internally repeated (with monomeric or oligomeric internal iterations) and seem to be at least partly the cause of the bias observed by other researchers at the level of retroviral nucleotide composition. They suggest a third evolutionary stage by slippage-like stepwise local duplications.

Background While multiple alignment is the first step of usual classification schemes for biological sequences, alignment-free methods are being increasingly used as alternatives when multiple alignments fail. Subword-based combinatorial methods are popular for their low algorithmic complexity (suffix trees ...) or exhaustivity (motif search), in general with fixed length word and/or number of mismatches. We developed previously a method to detect local similarities (the N-local decoding) based on the occurrences of repeated subwords of fixed length, which does not impose a fixed number of mismatches. The resulting similarities are, for some "good" values of N, sufficiently relevant to form the basis of a reliable alignment-free classification. The aim of this paper is to develop a method that uses the similarities detected by N-local decoding while not imposing a fixed value of N. We present a procedure that selects for every position in the sequences an adaptive value of N, and we implement it as the MS4 classification tool. Results Among the equivalence classes produced by the N-local decodings for all N, we select a (relatively) small number of "relevant" classes corresponding to variable length subwords that carry enough information to perform the classification. The parameter N, for which correct values are data-dependent and thus hard to guess, is here replaced by the average repetitivity κ of the sequences. We show that our approach yields classifications of several sets of HIV/SIV sequences that agree with the accepted taxonomy, even on usually discarded repetitive regions (like the non-coding part of LTR). Conclusions The method MS4 satisfactorily classifies a set of sequences that are notoriously hard to align. This suggests that our approach forms the basis of a reliable alignment-free classification tool. The only parameter κ of MS4 seems to give reasonable results even for its default value, which can be a great advantage for sequence sets for which little information is available.

Background In general, the construction of trees is based on sequence alignments. This procedure, however, leads to loss of informationwhen parts of sequence alignments (for instance ambiguous regions) are deleted before tree building. To overcome this difficulty, one of us previously introduced a new and rapid algorithm that calculates dissimilarity matrices between sequences without preliminary alignment. Results In this paper, HIV (Human Immunodeficiency Virus) and SIV (Simian Immunodeficiency Virus) sequence data are used to evaluate this method. The program produces tree topologies that are identical to those obtained by a combination of standard methods detailed in the HIV Sequence Compendium. Manual alignment editing is not necessary at any stage. Furthermore, only one user-specified parameter is needed for constructing trees. Conclusion The extensive tests on HIV/SIV subtyping showed that the virus classifications produced by our method are in good agreement with our best taxonomic knowledge, even in non-coding LTR (Long Terminal Repeat) regions that are not tractable by regular alignment methods due to frequent duplications/insertions/deletions. Our method, however, is not limited to the HIV/SIV subtyping. It provides an alternative tree construction without a time-consuming aligning procedure.

Background A new variant of Creutzfeldt-Jakob disease was described in the United Kingdom. It is often claimed that it is caused by consumption of food infected with the agent of bovine spongiform encephalopathy. However, this remains open to question because the number of cases of the variant is, at the present time, less than would be expected from a major food-borne source. Discussion The EUROCJD cooperative study presents currently available epidemiological data of Creutzfeldt-Jakob disease and its new variant, for nine European countries plus Australia and Canada. Unexpectedly, for the United Kingdom where all but a few cases of the new variant have been reported, these cases have to be included in the incidence curve of the sporadic forms of the disease in order to obtain the best fit with the median curve from all the countries. This variant could be merely a rare clinical phenotype within the sporadic disease. The published clinical and experimental data which suggest that it is linked with bovine spongiform encephalopathy, lead us to propose that this link could be a common etiological origin other than consumption of bovine infected food. In any case, public health recommendations hold and further investigation is required. Summary The lack of a relative increase of the Creutzfeldt-Jakob-disease mortality rate in the United Kingdom, does not fit well with the new variant being the consequence of consumption of food infected with the agent of bovine spongiform encephalopthy.

Previous analyses of retroviral nucleotide sequences, suggest a so-called "scrambled duplicative stepwise molecular evolution" (many sectors with successive duplications/deletions of short and longer motifs) that could have stemmed from one or several starter tandemly repeated short sequence(s). In the present report, we tested this hypothesis by focusing on the long terminal repeats (LTRs) (and flanking sequences) of 24 human and 3 simian immunodeficiency viruses. By using a calculation strategy applicable to short sequences, we found consensus overrepresented motifs (often containing CTG or CAG) that were congruent with the previously defined "retroviral signature." We also show many local repetition patterns that are significant when compared with simply shuffled sequences. First- and second-order Markov chain analyses demonstrate that a major portion of the overrepresented oligonucleotides can be predicted from the dinucleotide compositions of the sequences, but by no means can biological mechanisms be deduced from these results: some of the listed local repetitions remain significant against dinucleotide-conserving shuffled sequences; together with previous results, this suggests that interspersed and/or local mononucleotide and oligonucleotide repetitions could have biased the dinucleotide compositions of the sequences. We searched for suggestive evolutionary patterns by scrutinizing a reliable multiple alignment of the 27 sequences. A manually constructed alignment based on homology blocks was in good agreement with the polypeptide alignment in the coding sectors and has been exhaustively assessed by using a multiplied alphabet obtained by the promising mathematical strategy called the N-block presentation (taking into account the environment of each nucleotide in a sequence). Sector by sector, we hypothesize many successive duplication/deletion scenarios that fit our previous evolutionary hypotheses. This suggests an important duplication/deletion role for the reverse transcriptase, particularly in inducing stuttering cryptic simplicity patterns.

We investigate the nucleotide sequences of 23 retroelements (4 mammalian retroviruses, 1 human, 3 yeast, 2 plant, and 13 invertebrate retrotransposons) in terms of their oligonucleotide composition in order to address the problem of relationship between retrotransposons and retroviruses, and the coadaptation of these retroelements to their host genomes. We have identified by computer analysis over-represented 3- through 6-mers in each sequence. Our results indicate retrotransposons are heterogeneous in contrast to retroviruses, suggesting different modes of evolution by slippage-like mechanisms. Moreover, we have calculated the Observed/Expected number ratio for each of the 256 tetramers and analysed the data using a multivariate approach. the tetramer composition of retroelement sequences appears to be influenced by host genomic factors like methylase activity.

An exhaustive computer-assisted analysis of the Moloney murine leukemia virus nucleotide sequence shows numerous deviations in the oligomeric distribution, suggesting three overlapping levels of a stepwise duplicative evolution. (1) The sequence fits the universal rule of TG/CT excess which has been proposed as the construction principle of all sequences, and maintains some degree of symmetry between the two complementary strands. (2) Oligomeric repeating units share a core consensus regularly scattered throughout the sequence. This consensus is not merely predictable from the doublet frequencies and codon usage, but could correspond to an intermediary stage in a so-called periodic-to-chaotic transition. (3) Probable stepwise local duplications could be accounted for by slippagelike mechanisms. Comparison with the human spumaretrovirus (HSRV) shows similar segments in the overrepresented oligomers of the two sequences. The intermediary stage of transition oligomeric repeating units is not so clearly suggested in HSRV, perhaps because of numerous stepwise local duplications. In any case, a common evolutionary origin for the two viruses is not ruled out.

The nucleotide sequences encoding the transforming polyproteins of the Snyder-Theilen and Gardner-Arnstein strains of feline sarcoma virus (FeSV) have been determined. These sequences include a viral transforming gene ( v-fes ), derived from cellular proto-oncogene sequences ( c-fes ) of domestic cats by recombination with feline leukemia virus (FeLV). The v-fes sequences are predicted to encode a polypeptide domain strikingly similar to that specified by the transforming gene ( v-fps ) of the avian Fujinami sarcoma virus. In addition, the 3′ 0.8 kilobase pairs of v-fes encode amino acid sequences homologous to the carboxy-terminal portion of pp60 src , the transforming protein encoded by the avian Rous sarcoma virus src gene. Thus different feline and avian retroviral transforming genes, all of which encode functionally related proteins with associated tyrosine-specific kinase activities, must be derived from divergent members of the same protooncogene family.

Isoelectric focusing (IEF) analysis of class I endogenous type-C virus induced by iododeoxyuridine treatment of BALB/K-3T3 cells revealed, in addition to the major variant of the p30 polypeptide, which has an isoelectric point of 6.1 (pI 6.1 isop30), a minor isop30 with a pI of 5.6. This value was also found for a prototype BALB/c B-tropic endogenous virus isolate. The pI 5.6 isop30 of the N-tropic isolate was amplified by long-term virus replication in B-type mouse cells, and comparative IEF and XC-assay data suggest that it may correspond to a B-tropic subpopulation which has not yet been detected in vitro in mouse cells of embryonic origin.

The present study is a detailed computer-assisted analysis of the feline leukemia virus gag gene nucleotide sequence together with its flanking sequences (ST-FeLV GAG) that is compared with the aligned sectors of the Moloney strain of murine leukemia virus (Mo-MuLV GAG) and of three strains of feline sarcoma virus. It shows that perfectly matched repeated oligomers up to 13 nucleotides long are overrepresented and scattered throughout both ST-FeLV GAG and Mo-MuLV GAG, in noncoding and coding sectors, with no stringent correlation to codon usage in ST-FeLV gPr80gag. Many repeated oligomers share a core consensus that is intriguingly part of the inverted repeat at the termini of the long terminal repeat. Local scrambled repetitions of nucleotide subsequences have been found; they suggest a model of molecular evolution by slippage-like mechanisms. Thus, viral genomes could be subject to the same evolutionary mechanisms that are now known to be operating extensively in eukaryotic genomes. The data are discussed in light of putative patterns of molecular evolution.