MULTIPLE SEQUENCE ALIGNMENT BASED ON NEW APPROACHES OF TREE CONSTRUCTION AND SEQUENCE COMPARISON

A fast algorithm for multiple sequence alignment based on new approaches of tree construction and sequence comparison is suggested. We developed a version of the pairwise sequence alignment algorithm,¹ which was based on analysis of DOT matrix Diagonal fragments (Df) followed by joining of significant Dfe in the final alignment. The algorithm maintains some methodological features of Needleman-Wunsch (NW) type algorithms and uses statistical estimations of similarity of various Dfs. The estimations were entered into a compact “competition matrix” (CM). Homology of sequence positions for multiple alignment was changed to homology of the corresponding rows in the aligned subsets. In addition, instead of one-iteration filling of the CM by Df information, a multi-iteration method was suggested. We assumed that the minimal length of Df used for each iteration must be selected so that the probability of occurrence of homologous subsequences of a given length, by chance, would be low. On the basis of these significant Dfs we reconstructed an initial rough alignment. In the next iteration, calculations were repeated for all gaps in the previous alignment, where no significant homology between aligned sets was fixed. For each such gap, its length was used for the estimation of a new minimal length Df. The method of multiple alignment presented here also uses a new approach for tree reconstruction based on the analysis of the relatively conserved oligonucleotides in a given set. This approach has some advantages compared to traditional methods of phylogenetic tree reconstruction, which as a rule, attribute a definite weight to mutations independent of their location along the sequence. The tree construction was a very fast procedure, which does not require preliminary alignment of sequences.² The method was tested on 5S RNA sequences and its application for contigs joining was discussed.