New method for global alignment of 2 DNA sequences by the tree data structure

Abstract

We introduce a new approach to investigate problem of DNA sequence alignment. The method consists of three parts: (i) simple alignment algorithm, (ii) extension algorithm for largest common substring, (iii) graphical simple alignment tree (GSA tree). The approach firstly obtains a graphical representation of scores of DNA sequences by the scoring equation R(0)*R-S(0)*S-T(0)*(a+bk). Then a GSA tree is constructed to facilitate solving the problem for global alignment of 2 DNA sequences. Finally we give several practical examples to illustrate the utility and practicality of the approach.

Fig. 1

The building steps of all possible alignments without spaces within G₁ and G₂.

Fig. 2

The figure illustrates the graphical score representation of simple alignments of sequences G₁ and G₂. The scoring equation is $\sum R-\sum S-\sum (a+\mathit{bk})$, where identity score R is 9, substitution score S is 1, gap opening penalty a is 15, and gap extension penalty b is 1.

Fig. 3

Improved simple alignment process with less consuming time (The length of G₁ is M. The length of G₂ is N. And let $M\le N$).

Fig. 4

An example of graphical simple alignment tree (Strings G₁ and G₂ includes 6 substrings in the first level sub-alignment: $U_1^1{C}_2^1{U}_3^1{C}_4^1{U}_5^1{C}_6^1$. The substring $U_1^1$ includes 3 substrings in the second level sub-alignment: $C_1^2{U}_2^2{C}_3^2$. The substring $U_3^1$ includes 2 substrings in the second level sub-alignment: $U_4^2{C}_5^2$. The substring $U_5^1$ includes 3 substrings in the second level sub-alignment: $U_6^2{C}_7^2{U}_8^2$. The substring $U_2^2$ includes 2 substrings in the third level sub-alignment: $U_1^3{C}_2^3$. The substring $U_8^2$ includes 2 substrings in the third level sub-alignment: $C_3^3{U}_4^3$).

Fig. 5

The graphical simple alignment tree to be used to align the sequences G₁ and G₂ (G₁, GGCCTCTGCCTAATCACACAGATCTAACAGGATTATTTC; G₂, GGCCTCTGCCTTATTACACAAATCTTAACAGGACTATTTC).

Fig. 6

The graphical simple alignment tree to be used to align the sequences G₁ and G₂ (G₁, GCCCTCGCGGGCAACATTTAATTCACAGCCAGTTCTCTCAACAG TGATTATC; G₂, CTGGGTCTTCAGGTCCTTTATGCTTAACACAAATCTATC GTTAACAGGACTATTCT).

Fig. 7

The global alignment between string a and string b. Identities: 328/448 (73.2%); Gaps: 8/448 (1.8%); Score: 2772.