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.

Description:
PRIOR PUBLICATION DATA 
       [0000]    
       
         Revesz, P. Z. (2013) An algorithm for constructing hypothetical evolutionary trees using common mutations similarity matrices, Proceedings of the 4 th  ACM International Conference on Bioinformatics and Computational Biology, ACM Press, pp. 731-734, Bethesda, Md., USA, September 22-25. 
         Revesz, P. Z. (2013) 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, September 17-19. 
       
     
       U.S. PATENT DOCUMENTS 
       [0000]    
       
         Muto. Isamu et al. (2005) Dendogram displaying method, U.S. Pat. No. 6,847,381. 
         Sayood, K. et al. (2014) System and method for sequence distance measure for phylogenetic tree construction, U.S. Pat. No. 8,725,419. 
       
     
       OTHER REFERENCES 
     Please See at the End 
     PARENT CASE TEXT 
     Cross Reference to Related Applications 
       [0005]    U.S. Provisional Patent Application 62/049,332 filed Sep. 11, 2014. No other applications. 
       DESCRIPTION 
     Background of the Invention 
       [0006]    Understanding the evolutionary relationship of a set of biological organisms is an important part of many biological applications. Therefore constructing hypothetical evolutionary trees, also called phylogenetic trees, is a well-established topic with several prior algorithms proposed by other researchers (Baum and Smith [1], Hall [2], Lerney et al. [3]). Two of these algorithms, namely the neighbor joining (Saitou and Nei [7]) and the UPGMA (Sokal and Michener [9]) methods, are based on using a distance matrix for a set of nucleotide or amino acid sequences. 
       SUMMARY OF THE INVENTION 
       [0007]    The main novelty and distinguishing feature of the proposed patent is that it uses common mutations similarity matrices instead of distance matrices. The motivation behind looking for common mutations is that in practice rare but shared features, such as rare mutations, often provide useful markers of similarity among a set of closely related items. 
     
    
     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: 
         [0000]    
       
         
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
               
               
                 ALGORITHM CMSM(S 1  . . . S n , n) 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Input Data: S 1  ... S 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 i  and S j  with non-0 common mutations) 
               
             
          
           
               
                  7 
                  Merge a closest distinct S i  and S j  pair into a new cluster 
               
             
          
           
               
                   
                 S ij  and create a node for S ij .and update the common 
               
               
                   
                 mutations similarity matrix. 
               
             
          
           
               
                  8 
                 Connect the nodes for S i  and S j  with parent node S ij . 
               
             
          
           
               
                  9 
                 Else 
               
             
          
           
               
                 10 
                 Connect the remaining clusters&#39; 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 1  . . . S 7 , each with a length fifteen nucleotides displayed by groups of five nucleotides per column in table below: 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 S 1   
                 AGCTA 
                 CTAGT 
                 AATCA 
               
               
                   
                   
               
               
                   
                 S 2   
                 AGCTA 
                 CGAGT 
                 AATCA 
               
               
                   
                   
               
               
                   
                 S 3   
                 ATCCA 
                 CTAGT 
                 ACACT 
               
               
                   
                   
               
               
                   
                 S 4   
                 ATCCA 
                 CTAGT 
                 ATACT 
               
               
                   
                   
               
               
                   
                 S 5   
                 CGGTA 
                 TTTGT 
                 AAGCT 
               
               
                   
                   
               
               
                   
                 S 6   
                 CGGTT 
                 CATCA 
                 AATGC 
               
               
                   
                   
               
               
                   
                 S 7   
                 AGGTA 
                 CTTGA 
                 AATCC 
               
             
          
         
       
     
         [0010]    Let S i [k] denote the k th  nucleotide of the i th  nucleotide sequence, S 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. 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 S 1   
                 AGCTA 
                 CTAGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 2   
                 AGCTA 
                 C G AGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 3   
                 A T C C A 
                 CTAGT 
                 A CA CT 
               
               
                   
                   
               
               
                   
                 S 4   
                 A T C C A 
                 CTAGT 
                 A TA CT 
               
               
                   
                   
               
               
                   
                 S 5   
                   C G G TA 
                   T T T GT 
                 AA G CT 
               
               
                   
                   
               
               
                   
                 S 6   
                   C G G T T   
                 C ATCA   
                 AAT GC   
               
               
                   
                   
               
               
                   
                 S 7   
                 AG G TA 
                 CT T G A   
                 AATC C   
               
               
                   
                   
               
               
                   
                 μ 
                 AGCTA 
                 CTAGT 
                 AATCT 
               
             
          
         
       
     
       Line 4: 
       [0013]    It can be assumed that in each sequence S 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: 
         [0000]    
       
         
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 S 1   
                 S 2   
                 S 3   
                 S 4   
                 S 5   
                 S 6   
                 S 7   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 S 1   
                 1 
                 1 
                 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 S 2   
                 1 
                 2 
                 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 S 3   
                 0 
                 0 
                 4 
                 3 
                 0 
                 0 
                 0 
               
               
                   
                 S 4   
                 0 
                 0 
                 3 
                 4 
                 0 
                 0 
                 0 
               
               
                   
                 S 5   
                 0 
                 0 
                 0 
                 0 
                 5 
                 3 
                 2 
               
               
                   
                 S 6   
                 0 
                 0 
                 0 
                 0 
                 3 
                 9 
                 4 
               
               
                   
                 S 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 i  and S j , in the merged sequence the k th  element will be equal to the nucleotide in the two sequences if S i [k]=S 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 6  and S 7 . When we merge these sequences, the matrix of sequences will be updated as follows: 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 S 1   
                 AGCTA 
                 CTAGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 2   
                 AGCTA 
                 C G AGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 3   
                 A T C C A 
                 CTAGT 
                 A CA CT 
               
               
                   
                   
               
               
                   
                 S 4   
                 A T C C A 
                 CTAGT 
                 A TA CT 
               
               
                   
                   
               
               
                   
                 S 5   
                   C G G TA 
                   T T T GT 
                 AA G CT 
               
               
                   
                   
               
               
                   
                 S 67   
                 AG G TA 
                 CT T G A   
                 AATC C   
               
               
                   
                   
               
               
                   
                 μ 
                 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: 
         [0000]    
       
         
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 S 1   
                 S 2   
                 S 3   
                 S 4   
                 S 5   
                 S 67   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 S 1   
                 1 
                 1 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 S 2   
                 1 
                 2 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 S 3   
                 0 
                 0 
                 4 
                 3 
                 0 
                 0 
               
               
                   
                 S 4   
                 0 
                 0 
                 3 
                 4 
                 0 
                 0 
               
               
                   
                 S 5   
                 0 
                 0 
                 0 
                 0 
                 5 
                 2 
               
               
                   
                 S 67   
                 0 
                 0 
                 0 
                 0 
                 2 
                 4 
               
               
                   
                   
               
             
          
         
       
     
         [0017]    Next merging the closest pair, S 3  and S 4 , yields: 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 S 1   
                 AGCTA 
                 CTAGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 2   
                 AGCTA 
                 C G AGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 34   
                 A T C C A 
                 CTAGT 
                 AA A CT 
               
               
                   
                   
               
               
                   
                 S 5   
                   C G G TA 
                   T T T GT 
                 AA G CT 
               
               
                   
                   
               
               
                   
                 S 67   
                 AG G TA 
                 CT T G A   
                 AATC C   
               
               
                   
                   
               
               
                   
                 μ 
                 AGCTA 
                 CTAGT 
                 AATCT 
               
             
          
         
       
     
         [0018]    The updated common mutations matrix will be: 
         [0000]    
       
         
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 S 1   
                 S 2   
                 S 34   
                 S 5   
                 S 67   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 S 1   
                 1 
                 1 
                 0 
                 0 
                 0 
               
               
                   
                 S 2   
                 1 
                 2 
                 0 
                 0 
                 0 
               
               
                   
                 S 34   
                 0 
                 0 
                 3 
                 0 
                 0 
               
               
                   
                 S 5   
                 0 
                 0 
                 0 
                 5 
                 2 
               
               
                   
                 S 67   
                 0 
                 0 
                 0 
                 2 
                 4 
               
               
                   
                   
               
             
          
         
       
     
         [0019]    Next merging the closest pair, S 5  and S 67 , yields: 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 S 1   
                 AGCTA 
                 CTAGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 2   
                 AGCTA 
                 C G AGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 34   
                 A T C C A 
                 CTAGT 
                 AA A CT 
               
               
                   
                   
               
               
                   
                 S 567   
                 AG G TA 
                 CT T GT 
                 AATCT 
               
               
                   
                   
               
               
                   
                 μ 
                 AGCTA 
                 CTAGT 
                 AATCT 
               
             
          
         
       
     
         [0020]    The updated common mutations matrix will be: 
         [0000]    
       
         
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 S 1   
                 S 2   
                 S 34   
                 S 567   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 S 1   
                 1 
                 1 
                 0 
                 0 
               
               
                   
                 S 2   
                 1 
                 2 
                 0 
                 0 
               
               
                   
                 S 34   
                 0 
                 0 
                 3 
                 0 
               
               
                   
                 S 567   
                 0 
                 0 
                 0 
                 2 
               
               
                   
                   
               
             
          
         
       
     
         [0021]    Next merging the closest pair, S 1  and S 2 , yields: 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 S 12   
                 AGCTA 
                 CTAGT 
                 AATC A   
               
               
                   
                   
               
               
                   
                 S 34   
                 A T C C A 
                 CTAGT 
                 AA A CT 
               
               
                   
                   
               
               
                   
                 S 567   
                 AG G TA 
                 CT T GT 
                 AATCT 
               
               
                   
                   
               
               
                   
                 μ 
                 AGCTA 
                 CTAGT 
                 AATCT 
               
             
          
         
       
     
         [0022]    The updated common mutations matrix will be: 
         [0000]    
       
         
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 S 12   
                 S 34   
                 S 567   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 S 12   
                 1 
                 0 
                 0 
               
               
                   
                 S 34   
                 0 
                 3 
                 0 
               
               
                   
                 S 567   
                 0 
                 0 
                 2 
               
               
                   
                   
               
             
          
         
       
     
         [0023]    Finally, the remaining clusters S 12 , S 34 , and S 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&#39; nodes to μ and generates the following hypothetical evolutionary tree: 
         [0000]    
       
                 
         
             
             
         
       
     
         [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 
       [0000]    
       
         [1] Baum, D. and Smith, S. (2012)  Tree Thinking: An Introduction to Phylogenetic Biology , Roberts and Company Publishers. 
         [2] Hall, B. G. (2011)  Phylogenetic Trees Made Easy: A How to Manual,  4 th  edition, Sinauer Associates. 
         [3] Lerney, P., Salemi, M. and Vandamme, A.-M, editors, (2009)  The Phylogenetic Handbook: A Practical Approach to Phylogenetic Analysis and Hypothesis Testing,  2 nd  edition, Cambridge University Press. 
         [4] Muto. Isamu et al. (2005) Dendogram displaying method, U.S. Pat. No. 6,847,381. 
         [5] Revesz, P. Z., An algorithm for constructing hypothetical evolutionary trees using common mutations similarity matrices, Proceedings of the 4 th  ACM International Conference on Bioinformatics and Computational Biology, ACM Press, pp. 731-734, Bethesda, Md., USA, Sep. 22-25, 2013. 
         [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. 
         [7] Saitou, N. and Nei, M. 1987. The neighbor-joining method: A new method for reconstructing phylogenetic trees.  Molecular Biological Evolution,  4, 406-425. 
         [8] Sayood, K. et al. (2014) System and method for sequence distance measure for phylogenetic tree construction, U.S. Pat. No. 8,725,419. 
         [9] Sokal, R. R. and Michener, C. D. (1958) A statistical method for evaluating systematic relationships.  University of Kansas Science Bulletin,  38, 1409-1438. 
         [10] Jones, N. C. and Pevzner, P. A. (2004)  An Introduction to Bioinformatics Algorithms , MIT Press