Search

Motivation: Compression algorithms can be used to analyse genetic sequences. A compression algorithm tests a given property on the sequence and uses it to encode the sequence: if the property is true, it reveals some structure of the sequence which can be described briefly, this yields a description of the sequence which is shorter than the sequence of nucleotides given in extenso. The more a sequence is compressed by the algorithm, the more significant is the property for that sequence. Results: We present a compression algorithm that tests the presence of a particular type of dosDNA (defined ordered sequence-DNA): approximate tandem repeats of small motifs (i.e. of lengths

A method aimed at classifying protein sequences withoutresorting to pairwise alignment is presented. Called DOCMA(DOt-plot Comparisons by Multivariate Analysis), it is basedon a multivariate analysis of the pairwise dot-plots between allthe sequences in the set. The dot-plots are first simplified byconsidering only the projections of the 'diagonal' segments ofsimilarity onto the axes. From these projections a data matrixis built, in which each column is representative of thecomparisons of one given sequence with all the other ones. Thisdata matrix is then transformed into a distance matrix by achi-squared analysis, from which the coordinates of thesequences in an orthonormal Euclidean space are obtained. Thesequences are finally classified by a dynamic clusteringprocedure followed by a search for strong clusters. Applicationof this method to protein families such as the globins, thecytochromes c and the aminoacyl-tRNA synthetases shows thatit is quite effective in delineating subgroups that contain evendistantly related sequences.IntroductionAs more and more amino acid sequences of proteins becomeavailable, there has been a growing number of studies aimedat establishing the evolutionary relationships between membersof one given set of proteins, or, less ambitiously, at classifyingthe sequences as a function of their similarities. In the first case,the problem is to find the tree(s) in which the lengths of thebranches reflect at best the pairwise distances between thesequences—assuming that these distances are directly relatedto evolutionary times. The search for such a tree is generallyextremely time consuming, even if efficient heuristics are usedto speed up the process. For instance, the determination of themost parsimonious tree for 245 globin sequences (Goodmanet al., 1988) required the use of a Cray-2 supercomputer. In thesecond case, the problem is rather to delineate the groups, orclusters, of the most closely related sequences. The informationthus gained can be used, for instance, as a guideline forperforming a multiple alignment of the sequences, i.e. thosethat are most alike will be aligned first (e.g. Corpet, 1988; Fengand Doolittle, 1987; Taylor, 1988), or to select those sequences