CN106778078A - DNA sequence dna similitude comparison method based on kendall coefficient correlations - Google Patents

Abstract

The invention discloses a DNA sequence similarity comparison method based on kendall correlation coefficient, which comprises the following steps: 1) obtaining N DNA sequences to be compared; 2) selecting a length k, and obtaining each pair of combined DNA sequences in a sliding window manner The corresponding k words, and be combined into corresponding vectors 3) With the k words obtained in step 2), calculate the number of times that each k word occurs in the DNA sequence, that is, calculate the frequency vector of the occurrence of the k words in the DNA sequence, and use It is denoted as _xi , and the frequency of all k words in the DNA sequence is denoted as X={ _xi }; 4) Combining the k word vectors of N DNA sequences in pairs, we can get Combination, each combination k word frequency vector is recorded as x, y; 5) The k word frequency vector of each combination is x, y, and its corresponding kendall correlation coefficient is calculated; 6) N*N order of N DNA sequences is established Similarity coefficient matrix to obtain DNA sequence similarity and evolutionary relationship graph. The invention improves the effect of DNA sequence similarity comparison, simplifies calculation complexity and shortens calculation time.

Description

DNA Sequence Similarity Alignment Method Based on Kendall Correlation Coefficient

technical field

The invention relates to the field of computer and bioinformatics processing, in particular to a DNA sequence similarity comparison method based on kendall correlation coefficient.

Background technique

The central task of bioinformatics is to extract rational knowledge from the vast sea of DNA sequence data. The task faced by bioinformaticians is not only to solve efficient data storage methods, but also to develop effective data analysis tools. Because only by using new and effective data analysis tools, can DNA sequence information be converted into biological knowledge, and the structural and functional information contained in them can be clarified, so as to fully understand the biological significance they represent.

The theoretical basis of DNA sequence comparison is the theory of evolution. If there is enough similarity between two DNA sequences, it is speculated that the two may have a common evolutionary ancestor, through the replacement of residues in the DNA sequence, residues or DNA sequence fragments Deletion and DNA sequence recombination and other genetic variation processes evolved respectively. DNA sequence similarity and DNA sequence homology are different concepts. The degree of similarity between DNA sequences is a quantifiable parameter, while whether DNA sequences are homologous needs to be verified by evolutionary facts. DNA sequence comparison is actually using a specific mathematical model or algorithm to find the maximum number of matching bases between two or more DNA sequences.

Huang Yujuan, Wang Tianming and others constructed a probability distribution using the frequency and location information of k words in the DNA sequence. This distribution represents the distance between two vectors, and the smaller the value, the closer the species. Vinga and Almeida proposed a DNA sequence comparison method based on word frequency: the number of occurrences of all words with a length of k is obtained by sliding the window to obtain the number of times or frequency vectors of k words, so that a DNA sequence is mapped to a high-dimensional Euclidean space. A vector, thus converting the similarity comparison between DNA sequences into a comparison between vectors.

Double DNA sequence comparison is to use a specific algorithm to compare two DNA sequences, so as to find the maximum similarity between the two DNA sequences. The Kendall correlation coefficient is widely used in the correlation prediction of time DNA sequence, hydrology, water quality DNA sequence, etc., but it has not been used in DNA sequence similarity matching.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies in the prior art, provide a DNA sequence similarity comparison method based on the Kendall correlation coefficient, and construct a list of N DNA sequences The first-order similarity coefficient matrix is used to obtain the evolutionary relationship of N DNA sequences, and at the same time, the efficiency of DNA sequence similarity comparison is improved and the calculation efficiency is improved.

The technical scheme adopted in the present invention is:

A DNA sequence similarity comparison method based on kendall correlation coefficient, which comprises the steps of:

1) Obtain N DNA sequences to be compared;

2) Select the length k, obtain the corresponding k words of each pair of combined DNA sequences in a sliding window manner, and combine them into corresponding vectors

3) With the k words obtained in step 2), calculate the number of times that each k word occurs in the DNA sequence, that is, calculate the frequency vector that the k word occurs in the DNA sequence, and record it as _xi ;

4) Combining the k word vectors of N DNA sequences in pairs to obtain Combination, each combination vector is recorded as X={ _xi }, Y={y _i }.

5) The k word frequency vectors of each combination are x _i , y _i , and their corresponding kendall correlation coefficients are calculated;

6) Establish an N×N order correlation coefficient matrix of N DNA sequences to obtain similarity information and evolutionary relationship diagrams of DNA sequences.

Further, in the step 2), the word frequency vector whose length is k is taken for the DNA sequence.

Further, in the step 5), the kendall correlation coefficient of the k words of the DNA sequence can be obtained through the following steps;

a) Obtain the k words of the DNA sequence A to be compared by the following formula, wherein the length of the DNA sequence A is set to n:

b) Calculate the frequency of occurrence of k words by the following formula: x _i = {i-th k words The number of repetitions in the DNA sequence A};

c) For the combined X and Y vectors, calculate the kendall correlation coefficient through the following formula It is characterized in that: t _x is { _xi }, {y _i } has consistent logarithms, t _y is { _xi , y _i } has inconsistent logarithms, T is { _xi , y _i } has inconsistent The total number of identical k words.

d) t _x and t _y in step c) can be obtained by the following formula, t _x = ( _xi -y _i )*( _xi -y _i ) is the same sign, then it is called { _xi , y _i }, t _y can be obtained by the following formula, if t _y = ( _xi -y _i )*( _xi -y _i ) is a different sign, it is called inconsistency in { _xi , y _i } Sexual logarithm

The obtained kendall correlation coefficient τ is a number with a value of [-1,1]. When the value of τ is closer to 1, it means that the correlation between the two DNA sequences is stronger. When the value of τ is closer to -1, the It means that there is a negative correlation between the two DNA sequences, and when the value of τ is close to 0, it means that there is no correlation between the two DNA sequences.

Construct a kendall correlation coefficient matrix of N*N order, which is a symmetrical matrix, and the value on the diagonal is 1, and the pairwise similarity information of N DNA sequences can be obtained, thereby constructing the evolutionary model of N DNA sequences relation.

The present invention is based on the DNA sequence similarity comparison method of the kendall correlation coefficient, adopts the sliding window method to obtain the k-word frequency vector of the DNA sequence to be analyzed, and combines the k-word vectors of the N DNA sequences in pairs, and uses the kendall correlation coefficient to compare The correlation coefficient of the k-word frequency vector of the corresponding DNA sequence is calculated, so that the similarity detection of multiple DNA sequences can be carried out, and the detection results can effectively reflect the evolutionary relationship between the DNA sequences. This method is relatively simple. It only needs to construct a symmetrical matrix. The value on the diagonal line from the upper left to the lower right of the matrix is 1, which simplifies the computational complexity and improves the operational efficiency. The kendall coefficient can be used as a feature to describe the prediction of DNA sequence similarity value, good accuracy can be obtained.

Description of drawings

The present invention will be described in further detail below in conjunction with accompanying drawing and specific embodiment;

Fig. 1 is the schematic flow chart of the DNA sequence similarity comparison method based on kendall correlation coefficient of the present invention;

Fig. 2 is a diagram of the evolution relationship of DNA sequences in the method of comparing DNA sequence similarity based on Kendall correlation coefficient in the present invention.

detailed description

As shown in Figure 1 or Figure 2, the method of the present invention adopts the DNA coding DNA sequences of 20 species as an example to be further described in detail, including the following steps: As shown in Figure 1, the present embodiment based on the kendall correlation coefficient The DNA sequence similarity comparison method comprises the following steps:

1) Select the DNA coding DNA sequences of 20 species as the initial DNA sequences, and the names and lengths of the DNA sequences of the 20 species are shown in Table 1;

species name DNA sequence length baboon 16522 blue hale 16403 cat 17010 common_chimpanzee 16564 cow 16339 fin_whale 16399 gibbon 16473 gorilla 16365 grayseal 16798 harbor seal 16827 horse 16661 the human 16570 the mouse 16296 opossum 17085 orangutan 16390 pigmy_chimpanzee 16555 platypus 17020 rat 16301 wallaroo 16897 whiter hinoceros 16833

Table 1: Species DNA sequence information

2) Obtain k words from the initial DNA sequence in step 1, and combine these k words to obtain the k word frequency vector of the initial DNA sequence (see Vinga, S.Almeida, JSAligment-free sequence comparison area review[J].Bioinformatics. 513-523.2003). The feature of this method is to calculate the frequency of short DNA sequences of length k appearing in the DNA sequence to be tested according to the sliding window method. For the 4 bases {A, T, G, C} of DNA, take the length of k as 2, then There are 4 ² =16 kinds of corresponding k words, and if k=3 then correspond to k words 4 ³ =64 kinds; as the DNA sequence A=ATAACTA of the DNA sequence fragment to be tested, its k words W ₂ ={AT, TA, AA, TT,AG,GA,AC,CA,CT….}, its frequency vector The value is {1,2,1,0,0,0,1,0,1,0...}; the DNA sequence fragment to be tested B=ACAACTTA, and its k word frequency vector is {0,1,1,1,0 ,0,2,1,1,0...};

3) Corresponding to N DNA sequences, N k-word frequency vectors can be obtained, and combined in pairs to obtain Combination, each combination frequency vector is recorded as X, Y

4) Calculated by the following formula Obtain the kendall correlation coefficient, where t _x is the logarithm of consistency between { _xi , y _i } and other k word frequencies, and t _y is the inconsistency pair between { _xi , y _i } and other k word frequencies Number, T is that { _xi , y _i } has different total number of k words, step 2) in DNA sequence A, the total number of k words of segment B is T=7;

5) t _x and t _y in step 4) can be obtained by the following formula, t _x = ( _xi -y _i ) × ( _xi -y _i ) is the same sign, then it is called { _xi , y _i } Consistency logarithm, t _y can be obtained by the following formula, t _y = ( _xi -y _i )×( _xi -y _i ) is a different sign, it is called the inconsistency pair in { _xi ,y _i } number;

6) The construction matrix is a kendall correlation coefficient matrix of order N*N, which is a symmetrical matrix with a diagonal value of 1, and can usually be listed as an upper triangular matrix. Since similarity is negatively correlated with distance, before constructing the evolutionary relationship diagram, we invert the similarity value and convert it into distance, and then construct the evolutionary relationship diagram, please refer to Figure 2.

Result analysis: by calculating the Pearson correlation coefficient between the edit distance, we find that the correlation coefficient between the DNA sequence similarity calculated by kendall and the edit distance is -0.94, indicating that the DNA sequence similarity calculated by the method of the present invention has It is characterized by high precision and can be obtained by fast calculation, which is a very effective method to replace the edit distance.

The above is only an embodiment of the present invention, and does not limit the patent scope of the present invention. Any equivalent structure or equivalent process transformation made by using the description of the present invention and the contents of the accompanying drawings, or directly or indirectly used in other related technologies fields, all of which are equally included in the scope of patent protection of the present invention.

Claims (5)

1. the DNA sequence dna similitude comparison method of kendall coefficient correlations is based on, it is characterised in that：It comprises the following steps：

1) N bars DNA sequence dna to be compared is obtained；

2) length k is chosen, each pair is obtained in the way of sliding window and is combined the corresponding k words of DNA sequence dna, and be combined into corresponding Vector；

3) with step 2) acquired in k words, calculate the number of times that each k word occurs in DNA sequence dna, that is, calculate k words in DNA sequence dna The frequency vector of middle appearance, is designated as x_i；

4) combination of two is carried out to N bar DNA sequence dna k term vectors, that is, is obtainedCombination, each mix vector is designated as X={ x_i},Y ={ y_i}；

5) the k word frequency vectors of every kind of combination are x_i, y_i, calculate its corresponding kendall coefficient correlation；

6) N × N rank correlation matrixs of N bar DNA sequence dnas are set up, to obtain the analog information and evolutionary relationship of DNA sequence dna Figure.

2. the DNA sequence dna similitude comparison method of kendall coefficient correlations is based on according to claim 1, it is characterised in that： The step 2) in, the word frequency vector that its length is k is taken to DNA sequence dna.

3. the DNA sequence dna similitude comparison method of kendall coefficient correlations is based on according to claim 1, it is characterised in that： The step 5) in, the kendall coefficient correlations of the k words of DNA sequence dna are obtained as follows：

A) by following formula, the k words of DNA sequence dna A to be compared are obtained, wherein DNA sequence dna A length is set to n：

$F_K^A=\left(f\right(W_{k,1}^A),f(W_{k,2}^A),...f(W_{k,n}^A\left)\right)$

B) by following formula, the frequency that k words occur is calculated：x_i={ i-th k wordThat repeats in DNA sequence dna A is secondary Number }；

C) to the X for combining, Y-direction amount, by following formula, calculates kendall coefficient correlationsIt is characterized in that：t_xIt is {x_i},{y_iIn possess uniformity logarithm, t_yIt is { x_i,y_iPossessing inconsistency logarithm, T is { x_i,y_iPossess that to differ k words total Number；

D) t in step c)_x, t_yCan be obtained by following formula, t_x=(x_i-y_i)*(x_i-y_i) be jack per line, then it is known as { x_i,y_iIn Uniformity logarithm, t_yCan be obtained by following formula, t_y=(x_i-y_i)*(x_i-y_i) be contrary sign, then it is known as { x_i,y_iIn inconsistency Logarithm.

4. the DNA sequence dna similitude comparison method of kendall coefficient correlations is based on according to claim 1, it is characterised in that： The kendall coefficient correlations τ for being obtained is the number that a value is [- 1,1], when the value of τ is closer to 1 expression, two DNA sequences Degree of correlation is stronger between row, when the value of τ is related negative sense between two DNA sequence dnas of -1 expression, when the value of τ is approached Represent that two DNA sequence dnas do not exist correlation in 0.

5. the DNA sequence dna similitude comparison method of kendall coefficient correlations is based on according to claim 1, it is characterised in that： The kendall correlation matrixs of N*N ranks are built in step 6, this matrix is symmetrical matrix, and the value on diagonal is 1, can be obtained To the affinity information two-by-two of N bar DNA sequence dnas, the relation of the evolution of N bar DNA sequence dnas is thus constructed.