Algorithm for constructing hypothetical evolutionary trees using common mutations similarity matrices

Abstract

The present invention permits constructing hypothetical evolutionary trees for a set of genetically related DNA strings or a set of proteins within a protein family. The main novelty of the invention compared to other hypothetical evolutionary tree construction methods is the use of a common mutations similarity matrix.

Claims

1. A computer implemented method comprising: receiving as input either a set of nucleic acid sequences or a set of protein sequences; generating an initial common mutations similarity matrix; in each successive steps merging the pair of sequences that are most similar according to the current common mutations similarity matrix and then updating the common mutations similarity matrix; repeating the merging steps until there is only sequence left; finally, from the sequence of merging steps reconstruct a hypothetical evolutionary tree.

2. The method in claim 1, wherein in case of nucleotide sequences the common mutations similarity matrix is computed by first identifying a hypothetical common ancestor sequence. In the case of nucleotide sequences the computation of the hypothetical common ancestor sequence comprises of the following two steps: first an alignment of the input nucleotide sequences and second in each column of the alignment finding the most frequent nucleotide. If there is more than one with the same maximum frequency than any one of those is selected by some random method.

3. The method in claim 1, wherein in case of amino acid sequences the common mutations similarity matrix is computed by first identifying a hypothetical common ancestor sequence. In the case of amino acid sequences the computation of the hypothetical common ancestor sequence comprises of the following two steps: first an alignment of the input nucleotide sequences and second in each column of the alignment finding the amino acid that is overall closest to all the amino acids in that column. Further, the overall closest amino acid is the amino acid that has the maximum sum of similarities between it and the amino acids in the column. If there is more than one with the same maximum value than any one of those is selected by some random method.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0008] Our hypothetical evolutionary tree construction algorithm based on common mutations similarity matrices (CMSMs) is summarized by the following pseudocode:

TABLE-US-00001 ALGORITHM CMSM(S.sub.1 . . . S.sub.n, n) Input Data: S.sub.1 ... S.sub.n are n aligned nucleotide sequences, each with the same length l. The alignment may contain gaps. (If the original sequences are not aligned, then preprocess the data by any well-known sequence alignment algorithm [10].) 1 Form n clusters of sequences, each with a single sequence. 2 Find the putative common ancestor of the sequences. 3 Construct a graph T with a node for each n cluster and for . 4 Find the common mutations similarity matrix 5 While (there is more than one cluster) 6 If (exist distinct S.sub.i and S.sub.j with non-0 common mutations) 7 Merge a closest distinct S.sub.i and S.sub.j pair into a new cluster S.sub.ij and create a node for S.sub.ij.and update the common mutations similarity matrix. 8 Connect the nodes for S.sub.i and S.sub.j with parent node S.sub.ij. 9 Else 10 Connect the remaining clusters' nodes to parent . 11 Return T. 12 Return T.

[0009] Next we illustrate the above algorithm using as the input data the following seven nucleotide sequences S.sub.1 . . . S.sub.7, each with a length fifteen nucleotides displayed by groups of five nucleotides per column in table below:

TABLE-US-00002 S.sub.1 AGCTA CTAGT AATCA S.sub.2 AGCTA CGAGT AATCA S.sub.3 ATCCA CTAGT ACACT S.sub.4 ATCCA CTAGT ATACT S.sub.5 CGGTA TTTGT AAGCT S.sub.6 CGGTT CATCA AATGC S.sub.7 AGGTA CTTGA AATCC

[0010] Let S.sub.i[k] denote the k.sup.th nucleotide of the i.sup.th nucleotide sequence, S.sub.i.

[0011] Line 2: Find a Putative Common Ancestor of the Sequences:

[0012] In the case of nucleotide sequences, as in the current example, we find the hypothetical common ancestor sequence, denoted , as the mode of each column. If there is no most frequent nucleotide in a column, then we arbitrarily chose one of the most frequent nucleotides in it.

TABLE-US-00003 S.sub.1 AGCTA CTAGT AATCA S.sub.2 AGCTA CGAGT AATCA S.sub.3 ATCCA CTAGT ACACT S.sub.4 ATCCA CTAGT ATACT S.sub.5 CGGTA TTTGT AAGCT S.sub.6 CGGTT CATCA AATGC S.sub.7 AGGTA CTTGA AATCC AGCTA CTAGT AATCT

Line 4:

[0013] It can be assumed that in each sequence S.sub.i those nucleotides that do not match the corresponding nucleotide in were mutated at some point during evolution. In the above table those nucleotides are underscored. The common mutations similarity matrix is constructed by finding for each pair of sequences the number of underscored items, i.e., mutations with respect that they share. In our example, the result is the following:

TABLE-US-00004 S.sub.1 S.sub.2 S.sub.3 S.sub.4 S.sub.5 S.sub.6 S.sub.7 S.sub.1 1 1 0 0 0 0 0 S.sub.2 1 2 0 0 0 0 0 S.sub.3 0 0 4 3 0 0 0 S.sub.4 0 0 3 4 0 0 0 S.sub.5 0 0 0 0 5 3 2 S.sub.6 0 0 0 0 3 9 4 S.sub.7 0 0 0 0 2 4 4

[0014] Line 7: Merging Nodes and Updating the Common Mutations Similarity Matrix:

[0015] When we merge two sequences S.sub.i and S.sub.j, in the merged sequence the k.sup.th element will be equal to the nucleotide in the two sequences if S.sub.i[k]=S.sub.j[k] and will be equal to [k] otherwise. For example, according to the common mutations similarity matrix shown above, the closest pair of sequences is S.sub.6 and S.sub.7. When we merge these sequences, the matrix of sequences will be updated as follows:

TABLE-US-00005 S.sub.1 AGCTA CTAGT AATCA S.sub.2 AGCTA CGAGT AATCA S.sub.3 ATCCA CTAGT ACACT S.sub.4 ATCCA CTAGT ATACT S.sub.5 CGGTA TTTGT AAGCT S.sub.67 AGGTA CTTGA AATCC AGCTA CTAGT AATCT

[0016] The WHILE loop is repeated until there are no more unmerged sequences or there are no similar sequences (that is, their common mutations value is simply zero). Therefore, after merging S6 and S7 into a cluster, in the next iteration of the while loop, the algorithm updates the common mutations matrix as follows:

TABLE-US-00006 S.sub.1 S.sub.2 S.sub.3 S.sub.4 S.sub.5 S.sub.67 S.sub.1 1 1 0 0 0 0 S.sub.2 1 2 0 0 0 0 S.sub.3 0 0 4 3 0 0 S.sub.4 0 0 3 4 0 0 S.sub.5 0 0 0 0 5 2 S.sub.67 0 0 0 0 2 4

[0017] Next merging the closest pair, S.sub.3 and S.sub.4, yields:

TABLE-US-00007 S.sub.1 AGCTA CTAGT AATCA S.sub.2 AGCTA CGAGT AATCA S.sub.34 ATCCA CTAGT AAACT S.sub.5 CGGTA TTTGT AAGCT S.sub.67 AGGTA CTTGA AATCC AGCTA CTAGT AATCT

[0018] The updated common mutations matrix will be:

TABLE-US-00008 S.sub.1 S.sub.2 S.sub.34 S.sub.5 S.sub.67 S.sub.1 1 1 0 0 0 S.sub.2 1 2 0 0 0 S.sub.34 0 0 3 0 0 S.sub.5 0 0 0 5 2 S.sub.67 0 0 0 2 4

[0019] Next merging the closest pair, S.sub.5 and S.sub.67, yields:

TABLE-US-00009 S.sub.1 AGCTA CTAGT AATCA S.sub.2 AGCTA CGAGT AATCA S.sub.34 ATCCA CTAGT AAACT S.sub.567 AGGTA CTTGT AATCT AGCTA CTAGT AATCT

[0020] The updated common mutations matrix will be:

TABLE-US-00010 S.sub.1 S.sub.2 S.sub.34 S.sub.567 S.sub.1 1 1 0 0 S.sub.2 1 2 0 0 S.sub.34 0 0 3 0 S.sub.567 0 0 0 2

[0021] Next merging the closest pair, S.sub.1 and S.sub.2, yields:

TABLE-US-00011 S.sub.12 AGCTA CTAGT AATCA S.sub.34 ATCCA CTAGT AAACT S.sub.567 AGGTA CTTGT AATCT AGCTA CTAGT AATCT

[0022] The updated common mutations matrix will be:

TABLE-US-00012 S.sub.12 S.sub.34 S.sub.567 S.sub.12 1 0 0 S.sub.34 0 3 0 S.sub.567 0 0 2

[0023] Finally, the remaining clusters S.sub.12, S.sub.34, and S.sub.567 can be interpreted as being separate branches that are all descendent from the common ancestor sequence . Hence in the else clause, the new algorithm connects the remaining clusters' nodes to and generates the following hypothetical evolutionary tree:

##STR00001##

[0024] The above hypothetical evolutionary tree is different from the one that is generated by the UPGMA algorithm. Our publications [5] and [6] show the UPGMA result but is omitted from this patent application. U.S. Pat. No. 8,725,419 [8] is focused on a completely different similarity measure between genome sequences. U.S. Pat. No. 6,847,381 [4] is only tangentially related because it describes a method to visualize the phylogenetic tree instead of a method to generate the phylogenetic tree.

[0025] The CMSM algorithm can be easily adapted to a set of amino acid sequences. For amino acid sequences the is found by taking out of the twenty possible amino acids the one that is overall closest to the amino acids in the aligned column of amino acids. The overall closest is simply the amino acids for which the sum of similarity values to the amino acids is maximal.

REFERENCES

[0026] [1] Baum, D. and Smith, S. (2012) Tree Thinking: An Introduction to Phylogenetic Biology, Roberts and Company Publishers. [0027] [2] Hall, B. G. (2011) Phylogenetic Trees Made Easy: A How to Manual, 4.sup.th edition, Sinauer Associates. [0028] [3] Lerney, P., Salemi, M. and Vandamme, A.-M, editors, (2009) The Phylogenetic Handbook: A Practical Approach to Phylogenetic Analysis and Hypothesis Testing, 2.sup.nd edition, Cambridge University Press. [0029] [4] Muto. Isamu et al. (2005) Dendogram displaying method, U.S. Pat. No. 6,847,381. [0030] [5] Revesz, P. Z., An algorithm for constructing hypothetical evolutionary trees using common mutations similarity matrices, Proceedings of the 4.sup.th ACM International Conference on Bioinformatics and Computational Biology, ACM Press, pp. 731-734, Bethesda, Md., USA, Sep. 22-25, 2013. [0031] [6] Revesz, P. Z., An efficient algorithm for constructing evolutionary trees using common mutation matrixes, Proceedings of the 14th International Conference on Mathematics and Computers in Biology and Chemistry, WSEAS Press, pp. 107-113, Baltimore, Md., USA, Sep. 17-19, 2013. [0032] [7] Saitou, N. and Nei, M. 1987. The neighbor-joining method: A new method for reconstructing phylogenetic trees. Molecular Biological Evolution, 4, 406-425. [0033] [8] Sayood, K. et al. (2014) System and method for sequence distance measure for phylogenetic tree construction, U.S. Pat. No. 8,725,419. [0034] [9] Sokal, R. R. and Michener, C. D. (1958) A statistical method for evaluating systematic relationships. University of Kansas Science Bulletin, 38, 1409-1438. [0035] [10] Jones, N. C. and Pevzner, P. A. (2004) An Introduction to Bioinformatics Algorithms, MIT Press