key: cord-0897203-jvfjf7aw authors: Feng, Jie; Hu, Yong; Wan, Ping; Zhang, Aibing; Zhao, Weizhong title: New method for comparing DNA primary sequences based on a discrimination measure date: 2010-10-21 journal: J Theor Biol DOI: 10.1016/j.jtbi.2010.07.040 sha: beb7a26a834f61fb7bffe43bdaa8ddfe4fd9201e doc_id: 897203 cord_uid: jvfjf7aw We introduce a new approach to compare DNA primary sequences. The core of our method is a new measure of pairwise distances among sequences. Using the primitive discrimination substrings of sequence S and Q, a discrimination measure DM(S, Q) is defined for the similarity analysis of them. The proposed method does not require multiple alignments and is fully automatic. To illustrate its utility, we construct phylogenetic trees on two independent data sets. The results indicate that the method is efficient and powerful. With the completion of the sequencing of the genomes of human and other species, the field of analysis of genomic sequences is becoming very important tasks in bioinformatics. Comparison of primary sequences of different DNA strands remains the upmost important aspect of the sequence analysis. So far, most comparison methods are based on string alignment (Pearson and Lipman, 1988; Lake, 1994) : a distance function is used to represent insertion, deletion, and substitution of letters in the compared strings. Using the distance function, one can compare DNA primary sequences and resolve the questions of the homology of macromolecules. However, it is not easy to use for long sequences since it is realized with the aid of dynamic programming, which will be slow due to the large number of computational steps. In the past two decades, alignment-free sequence comparison (Vinga and Almeida, 2003) has been actively pursued. Some new methods have been derived with a variety of theoretical foundations. One category out of these methods is based on the statistics of word frequency within a DNA sequence (Sitnikova and Zharkikh, 1993; Karlin and Burge, 1995; Wu et al., 1997 Wu et al., , 2001 Stuart et al., 2002; Qi et al., 2004) . The core idea is that the more similar the two sequences are, the greater the number of the factors shared by two sequences is. The earliest publication using frequencies statistics of k-words for sequence comparison dates from 1986 (Blaisdell, 1986) . Three years after, Blaisdell (1989) proved that the dissimilarity values observed by using distance measures based on word frequencies are directly related to the ones requiring sequence alignment. In recent years, many researchers employ the k-words and the Markov model to obtain the information about the biological sequences (Pham and Zuegg, 2004; Pham, 2007; Kantorovitz et al., 2007; Helden, 2004; Dai et al., 2008) . Another category does not require resolving the sequence with fixed word length segments. It can be further divided into three groups. In the first group, researchers represent DNA sequence by curves (Hamori and Ruskin, 1983; Nandy, 1994; Randic et al., 2003a; Zhang et al., 2003; Liao, 2005; Li et al., 2006; Qi et al., 2007; Yu et al., 2009) , numerical sequences (He and Wang, 2002) , or matrices (Randic, 2000; Randic et al., 2001) . According to the representation, some numerical characterizations are selected as invariants of sequence for comparisons of DNA primary sequences. The advantage of these methods is that they provide a simple way of viewing, sorting and comparing various gene structures. But how to obtain suitable invariants to characterize DNA sequences and compare them is still a question need our attention. The second group corresponds to iterated maps. Jeffrey (1990) proposed the chaos game representation (CGR) as a scaleindependent representation for genomic sequences. The algorithm exploited iterative function systems to map nucleotide sequences into a continuous space. Since then, alignment-free methods based on CGR have aroused much interest in the field of computational biology. Further studies by Almeida et al. (2001) showed that CGR is a generalized Markov chain probability table which can accommodate non-integer orders, and that CGR is a powerful sequence modelling tool because of its computational efficiency and scale-independence (Almeida and Vinga, 2002 . Such alignment-free methods have been successfully applied for sequence comparison, phylogeny, detection of horizontal transfers, detection of oligonucleotides of interest, meta-genomic studies (Deschavanne et al., 1999; Pride et al., 2003; Sandberg et al., 2003; Teeling et al., 2004; Chapus et al., 2005; Wang et al., 2005; Dufraigne et al., 2005; Joseph and Sasikumar, 2006) . The third group is based on text compression technique Chen et al., 2004; Cilibrasi et al., 2004) . If one sequence which is given the information contained in the other sequence is significantly compressible, the two sequences are considered to be close. There are also some important methods which are based on compression algorithm but do not actually apply the compression, such as Lemple-Ziv complexity and Burrows-Wheeler transform (Otu and Sayood, 2003; Mantaci et al., 2007 Mantaci et al., , 2008 Yang et al., 2010) . In this paper, we propose a new sequence distance for the similarity analysis of DNA sequences. Based on the properties of primitive discrimination substrings, we construct a discrimination measure (DM) between every two sequences. Furthermore, as application, two data sets (bÀglobin genes and coronavirus genomes) are prepared and tested to identify the validity of the method. The results demonstrate that the new method is powerful and efficient. DNA sequences consist of four nucleotides: A (adenine), G (guanine), C (cytosine), and T (thymine). A DNA sequence, of length n, can be viewed as a linear sequence of n symbols from a finite alphabet A ¼ fA,C,G,Tg. Let S and Q be sequences defined over A, l(S) be the length of S, S(i) denotes the ith element of S and S(i, j) is the substring of S composed of the elements of S between positions i and j (inclusive). Definition 1. S(i, j) is called a discrimination substring (DS) that distinguishes S from Q if Sði,jÞ A Q , particularly, if S(i, j) does not include any other DSs distinguishing S from Q, we call S(i, j) a primitive discrimination substring (PDS) that distinguishes S from Q. The set of PDSs that distinguish S from Q is denoted by DðS,QÞ. Similarly, DðQ,SÞ expresses the set of PDSs that distinguish Q from S. Note that every sequence has its own identity, hence DðS,QÞ is usually different from DðQ,SÞ. For example for S¼acctac and Q¼gtgact, we can obtain that DðS,QÞ ¼ fcc,tag and DðQ,SÞ ¼ fgt,tg, ga,actg. Suppose u A DðS,QÞ and l(u)¼k, then we can get uð1,kÀ1Þ A Q (otherwise uð1,kÀ1Þ A DðS,QÞ, which conflicts with the minimum of u). Therefore the larger the k is, the more the same elements both S and Q have and correspondingly the smaller the degree of discrimination that S distinguishes from Q is. On the other hand, if the number of appearances of u in sequence S is t, we obviously note that the smaller the t is, the smaller the degree of discrimination that S distinguishes from Q is. From the above description, we construct the following discrimination measure that one sequence distinguishes from another sequence. Definition 2. DMðS 1 -S 2 Þ denotes the discrimination measure that S 1 distinguishes from S 2 in which v A DðQ,SÞ, lðvÞ ¼ ku and the number of appearances of v in sequence Q is tu. Definition 3. The discrimination measure of sequences S and Q is For the function DM to be a distance, it must satisfy (a) DMðx,yÞ 40 for x ay; (b) DM(x,x) ¼0; (c) DM(x,y) ¼DM(y,x) (symmetric); and (d) DMðx,yÞ r DMðx,zÞþDMðz,yÞ (triangle inequality). Apparently, DM satisfies distance conditions (a)-(c). It is not obvious that it also satisfies (d). The following proposition answers this. Proposition 1. DM(x,y) satisfies the triangle inequality, that is DMðx,zÞ rDMðx,yÞþDMðy,zÞ. Proof. Suppose s is an arbitrary element of Dðx,zÞ. If s is also contained in Dðx,yÞ, clearly we can obtain that DMðx-zÞ r DMðx-yÞþDMðy-zÞ. If there exists an element t A Dðx,zÞ, and t is not contained in Dðx,yÞ, then we can derive t A Dðy,zÞ, therefore the triangle inequality DMðx-zÞ rDMðx-yÞ þ DMðy-zÞ still comes into existence. Similarly, we can prove that DMðz-xÞ rDMðy-xÞþDMðz-yÞ. it is sufficient to prove the following inequality: This is equivalent to, by squaring both sides of the above inequality, ce þdf r ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ffi ðc 2 þd 2 Þðe 2 þf 2 Þ q : To prove this inequality, we just need to prove ðce þ df Þ 2 rðc 2 þ d 2 Þðe 2 þ f 2 Þ, i.e. 2cedf re 2 d 2 þ c 2 f 2 : Obviously, this inequality comes into existence. Therefore, ffiffiffiffiffiffiffiffiffiffiffiffiffiffi ffi Hence DM(x,y) satisfies the triangle inequality. & In this section, we apply the discrimination measure to analyze two sets of DNA primary sequences. The similarities among these species are computed by calculating the discrimination measure between every two sequences. The smaller the discrimination measure is, the more similar the species are. That is to say, the discrimination measures of evolutionary closely related species are smaller, while those of evolutionary disparate species are larger. Fig. 1 illustrates the basic processes of the DM algorithm. The first set we select includes 10 bÀglobin genes, whose similarity has been studied by many researchers using their first exon sequences (Randic et al., 2003b; Liu and Wang, 2005) . Here we will analyze these species using their complete bÀglobin genes. Table 1 presents their names, EMBL accession numbers, locations and lengths. In Table 2 , we present the similarity/dissimilarity matrix for the full DNA sequences of bÀglobin gene from 10 species listed in Table 1 by our new method. Observing Table 2 , we note that the most similar species pairs are human-gorilla, humanchimpanzee and gorilla-chimpanzee, which is expected as their evolutionary relationship. At the same time, we find that gallus and opossum are the most remote from the other species, which coincides with the fact that gallus is the only nonmammalian species among these 10 species and opossum is the most remote species from the remaining mammals. By further study of the values in the table, we can gain more information about their similarity. Another usage of the similarity/dissimilarity matrix is that it can be used to construct phylogenetic tree. The quality of the constructed tree may show whether the matrix is good and therefore whether the method of abstracting information from DNA sequences is efficient. Once a distance matrix has been calculated, it is straightforward to generate a phylogenetic tree using the NJ method or the UPGMA method in the PHYLIP package (http://evolution.genetics.washington.edu/phylip.html). In Fig. 2, we show the phylogenetic tree of 10 bÀglobin gene sequences based on the distance matrix DM, using NJ method. The tree is drawn using the DRAWGRAM program in the PHYLIP package. From this figure, we observe that (1) gallus is clearly separated from the rest, this coincides with real biological phenomenon; (2) human, gorilla, chimpanzee and lemur are placed closer to bovine and goat than to mouse and rat, this is in complete agreement with Cao et al. (1998) confirming the outgroup status of rodents relative to ferungulates and primates. Next, we consider inferring the phylogenetic relationships of coronaviruses with the complete coronavirus genomes. The 24 complete coronavirus genomes used in this paper were downloaded from GenBank, of which 12 are SARS-CoVs and 12 are from other groups of coronaviruses. The name, accession number, abbreviation, and genome length for the 24 genomes are listed in Table 3 . According to the existing taxonomic groups, sequences 1-3 form group I, and sequences 4-11 belong to group II, while sequence 12 is the only member of group III. Previous work showed that SARS-CoVs (sequences 13-24) are not closely related to any of the previously characterized coronaviruses and form a distinct group IV. In Fig. 3 , we present the phylogenetic tree belonging to 24 species based on the distance matrix DM, using UPGMA method. The tree is viewed using the DRAWGRAM program. As shown in Fig. 3 , four groups of coronaviruses can be seen from it: (1) The group I coronaviruses, including TGEV, PEDV and HCoV-229E tend to cluster together; (2) BCoV, BCoVL, BCoVM, BCoVQ, MHV, MHV2, MHVM, and MHVP, which belong to group II, are grouped in a monophyletic clade; (3) IBV, belonging to group III, is situated at an independent branch; (4) the SARS-CoVs from group IV are grouped in a separate branch, which can be distinguished easily from other three groups of coronaviruses. The tree constructed based on DM algorithm is quite consistent with the results obtained by other researchers (Zheng et al., 2005; Song et al., 2005; Liu et al., 2007; Li et al., 2008) . The emphasis of the present work is to provide a new method to analyze DNA sequences. From the above applications, we can see that our method is feasible for comparing DNA sequences and deducing their similarity relationship. In this paper, we propose a new method for the similarity analysis of DNA sequences. It is a simple method that yields results reasonably and rapidly. Our algorithm is not necessarily an improvement as compared to some existing methods, but an alternative for the similarity analysis of DNA sequences. The new approach does not require sequence alignment and graphical representation, and besides, it is fully automatic. The whole operation process utilizes the entire information contained in the DNA sequences and do not require any human intervention. The application of the DM algorithm to the sets of bÀglobin genes and coronavirus genomes demonstrates its utility. This method will also be useful to researchers who are interested in evolutionary analysis. Analysis of genomic sequences by chaos game representation Universal sequence map (USM) of arbitrary discrete sequences Computing distribution of scale independent motifs in biological sequences Biological sequences as pictures: a generic two dimensional solution for iterated maps A measure of similarity of sets of sequences not requiring sequence alignment Effectiveness of measures requiring and not requiring prior sequence alignment for estimating the dissimilarities of natural sequences Conflict among individual mitochondrial proteins in resolving the phylogeny of eutherian orders Exploration of phylogenetic data using a global sequence analysis method Shared information and program plagiarism detection Algorithmic clustering of music based on string compression Markov model plus k-word distributions: a synergy that produces novel statistical measures for sequence comparison Genomic signature: characterization and classification of species assessed by chaos game representation of sequences Detection and characterization of horizontal transfers in prokaryotes using genomic signature H curves, a novel method of representation of nucleotides series especially suited for long DNA sequences Characteristic sequences for DNA primary sequence Metrics for comparing regulatory sequences on the basis of pattern counts Chaos game representation of gene structure Chaos game representation for comparison of whole genomes A statistical method for alignment free comparison of regulatory sequences Dinucleotide relative abundance extremes: a genomic signature Reconstructing evolutionary trees from DNA and protein sequences: paralinear distances Directed graphs of DNA sequences and their numerical characterization 2-D graphical representation of protein sequences and its application to coronavirus phylogeny An information based sequence distance and its application to whole mitochondrial genome phylogeny A 2D graphical representation of DNA sequence A relative similarity measure for the similarity analysis of DNA sequences Characteristic distribution of L-tuple for DNA primary sequence An extension of the Burrows-Wheeler transform Distance measures for biological sequences: some recent approaches A new graphical representation and analysis of DNA sequence structure A new sequence distance measure for phylogenetic tree construction Improved tools for biological sequence comparison Spectral distortion measures for biological sequence comparisons and database searching A probabilistic measure for alignment-free sequence comparison Evolutionary implications of microbial genome tetranucleotide frequency biases Whole proteome prokaryote phylogeny without sequence alignment: a K-string composition approach New 3D graphical representation of DNA sequence based on dual nucleotides On the similarty of DNA primary sequences On the characterization of DNA primary sequences by triplet of nucleic acid bases Novel 2-D graphical representation of DNA sequences and their numerical characterization Analysis of similarity/ dissimilarity of DNA sequences based on novel 2-D graphical representation Quantifying the speciesspecificity in genomic signatures, synonymous codon choice, amino acid usage and G +C content Statistical analysis of L-tuple frequencies in eubacteria and organells Cross-host evolution of severe acute respiratory syndrome coronavirus in palm civet and human Integrated gene and species phylogenies from unaligned whole genome protein sequences Application of tetranucleotide frequencies for the assignment of genomic fragments Alignment-free sequence comparison-a review The spectrum of genomic signatures: from dinucleotides to chaos game representation A measure of DNA sequence dissimilarity based on Mahalanobis distance between frequencies of words Statistical measures of DNA dissimilarity under Markov chain models of base composition The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform TN curve: a novel 3D graphical representation of DNA sequence based on trinucleotides and its applications The Z curve database: a graphic representation of genome sequences Coronavirus phylogeny based on a geometric approach We thank all the anonymous referees for their valuable suggestions and support.