# Formulation and Analysis of Patterns in a Score Matrix for Global Sequence Alignment

Authors: James Owusu Asare; Justice Kwame Appati; Kwaku Darkwah
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

Global sequence alignment is one of the most basic pairwise sequence alignment procedures used in molecular biology to understand the similarity that arises among the structure, function, or evolutionary relationship between two nucleotide sequences. The general algorithm associated with global sequence alignment is the dynamic programming algorithm of Needleman and Wunsch. In this paper, patterns are exploited in the score matrix of the Needleman–Wunsch algorithm. With the help of some examples, the general patterns realized are formulated as new a priori propositions and corollaries that are established for both equal and unequal length comparisons of any two arbitrary sequences.


---

## Body

## 1. Introduction

Sequence alignment is the matching of strings or sequences of characters to identify patterns that may lead to informed structural or functional relationships between the strings or sequences matched. Varying situational problems seem to require the use of sequence alignment and examples abound from computer science to molecular biology, where sequences are usually aligned to make more meaning out of them. Bare [1] has discussed how researchers have over the years considered genetic sequences as strings of characters instead of focusing on their intrinsic properties to be able to compute the similarity among two or more related sequences. Global and local sequence alignment are used for matching two sequences, and they are categorized as pairwise sequence alignment or multiple sequence alignment when any alignment matches more than two sequences [2–4]. The Needleman–Wunsch algorithm [5–7] and the Smith–Waterman algorithm [8] are the general algorithms associated with pairwise global and local alignment, respectively. These two algorithms utilize a procedure called the dynamic programming approach. Dynamic programming as coined by Bellman in the 1940s is simply the process of solving a bigger problem by finding optimal solutions to its smaller nested problems [9–11]. Thus, to tackle a problem in the context of dynamic programming, it must possess the notion of recurrence. In [12, 13], an algorithm is said to be a well-defined computational task that accepts input and produces output values after following through a systematic method. Mathematical theory is thus a prerequisite behind the designing of functional programs [14, 15], and the algorithm design specializes in solving such problems. Global sequence alignment is mentioned as one of the vast dynamic programming applications in practical problems [16–18].More recently, Ouzounis and Baichoo [19] have stated that even though pairwise sequence alignment has been dealt with over time, concerns still remain in resolving exact evolutionary distances that demand very specific estimates. They have suggested the existence of theoretical relationships within alignments, algorithms, and data that are yet to be found. Motivated by the display of position-dependent arrays for affine gaps using the Needleman–Wunsch algorithm in [20, 21], we consider the more basic linear gap penalties using arbitrary sequences and proceed to find patterns in the score matrix which were absent in the presentation. This approach was taken because it is found missing in the available stream of literature although it can be likened to the edit graph illustration seen in [1]. To the best of our knowledge, there has never been any theoretical exposition of this kind for the most basic and very fundamental concept of constant linear gap penalties which constitute an implicit part of affine gap penalties. Thus, we focus on finding patterns in global sequence alignment using constant linear gap penalties and attempt the display of completed score matrices of the Needleman–Wunsch algorithm with distinct positional arrays that can be inspected. We give confirmation of this by basic proofs and suggest how predictions can be made. To offer the reader the much needed convenience, concepts that are deemed useful are recalled in brief with corresponding references of comprehensive works that give more in-depth information.


## 2. Needleman–Wunsch Algorithm

Let the recursive formulation for the Needleman–Wunsch algorithm be(1)
Initialization.LetP0,0=0,Pmi,0=Pmi−1,0 + gap penalty, ∀i=1,…,μ1 andPm0,j=Pm0,j−1 + gap penalty, ∀j=1,…,μ2,whereP0,0 is the initialization pivot for the score matrix, Pmi,0 is the initial row pivot for the score matrix, and Pm0,j is the initial column pivot for the score matrix.(2)
Cell Box Calculation.Let(1)Pmi,j=maxPDi,j=Pmi−1,j−1+σαi,βj,PRi,j=Pmi−1,j+gap penalty,PLi,j=Pmi,j−1+gap penalty,where Pmi,j is the pivot for each cell box calculation, PDi,j=Pmi−1,j−1+σαi,βj is the diagonal value of a cell box, PRi,j=Pmi−1,j+ gap penalty is the right value of a cell box, PLi,j=Pmi,j−1+ gap penalty is the left value of a cell box, and σαi,βj is the score for aligning the sequence characters of αi and βj.Specifically, the procedure for the Needleman–Wunsch algorithm follows the dynamic programming approach of the score matrix, traceback, and alignment as outlined in the subsequent sections.


### 2.1. Score Matrix

The score matrix is a tabular box constructed to keep count of score results. The score matrix for the Needleman–Wunsch algorithm begins with an initialization process and ends with the calculation of cell boxes.


#### 2.1.1. Initialization

A sequence matrix is created withμ1+1 columns and μ2+1 rows in order for the initial matrix gap to be aligned where μ1 and μ2 are the lengths of arbitrary sequences, α and β, respectively. The letters of the sequence α fill in the horizontal axis, and similarly, the characters of β fill in the vertical axis of the sequence matrix created. Before the scoring begins from the upper left corner of the initialized matrix to the lower right corner of the matrix, the value P0,0=0 is assigned to the intersection of the first row and the first column of the matrix (i.e., the initial gap). The reason for the gap penalty for an alignment is because of the possibility of mutation which may insert or delete a string character from one of the sequences. Arrows that point in the direction of positional movement (diagonal and left or right) are placed in each cell box of the matrix and only terminate when all the cell boxes are completely filled.


#### 2.1.2. Calculation of Cell Boxes in the Score Matrix

(1)
Fill the initialized gap values first on both the horizontal axis and the vertical axis with a defined constant gap value score(2)
Follow with the calculation of each cell box having the three position-dependent arrays (left/beside, right/bottom, or diagonal)(3)
Allow only a match/mismatch value for a “diagonal” position, and allow the “bottom” or “beside” positions to take linear gap values only(4)
For each computed cell box values, find the maximum score and let that be the pivot(5)
The pivot of a computed cell box directly affects the next cell boxes in the row or the column


### 2.2. Traceback

A simpler score matrix table that contains only the pivot of each cell box calculation is constructed from the original position-dependent arrays of the score matrix table. Arrow pointers are used to direct a path from the highest score or an optimal value in the matrix (which actually occurs at the lower right end corner of the matrix) and traced back to the next biggest value of the predecessors until we reach the intersection of the first row and the column with the initial gap.


### 2.3. Alignment

#### 2.3.1. Alignment Generation from a Traceback

To write the sequence characters that appear from the optimal alignment path of the traceback stage, the following steps are followed:(1)
When the arrow is diagonal, write both characters in the alignment(2)
When the arrow is vertical, write the corresponding horizontal character, and in place of the vertical character, leave a gap(3)
When the arrow is horizontal, write the corresponding vertical character, and in place of the horizontal character, leave a gapThus, for both the vertical and horizontal arrow positions, one character and a gap are written for the alignment, where the gap explicitly replaces a character position in the alignment. An alignment can only be inferred as the best if the optimal value from the score matrix table corresponds to the alignment score calculation (based on the scoring scheme defined).


#### 2.3.2. The Problem of Aligning Any Two Sequences

The problem of aligning any two sequences can be simplified as discovering the optimal means of aligning any two arbitrary sequences sayα and β such that the character “−” noted as a gap is filled into both α and β or either of them where(1)
Any single character inα matches a single character in β or a gap(2)
The final sum of scores from the scoring function over the aligned pairs and the gap penalties as given by the function of gap penalty is maximized


#### 2.3.3. Letter Choice for Arbitrary Sequences

The letter choice of this study shall be that of DNA considered as a string of four characters of adenine—A, guanine—G, cytosine—C, and thymine—T.


## 2.1. Score Matrix

The score matrix is a tabular box constructed to keep count of score results. The score matrix for the Needleman–Wunsch algorithm begins with an initialization process and ends with the calculation of cell boxes.


### 2.1.1. Initialization

A sequence matrix is created withμ1+1 columns and μ2+1 rows in order for the initial matrix gap to be aligned where μ1 and μ2 are the lengths of arbitrary sequences, α and β, respectively. The letters of the sequence α fill in the horizontal axis, and similarly, the characters of β fill in the vertical axis of the sequence matrix created. Before the scoring begins from the upper left corner of the initialized matrix to the lower right corner of the matrix, the value P0,0=0 is assigned to the intersection of the first row and the first column of the matrix (i.e., the initial gap). The reason for the gap penalty for an alignment is because of the possibility of mutation which may insert or delete a string character from one of the sequences. Arrows that point in the direction of positional movement (diagonal and left or right) are placed in each cell box of the matrix and only terminate when all the cell boxes are completely filled.


### 2.1.2. Calculation of Cell Boxes in the Score Matrix

(1)
Fill the initialized gap values first on both the horizontal axis and the vertical axis with a defined constant gap value score(2)
Follow with the calculation of each cell box having the three position-dependent arrays (left/beside, right/bottom, or diagonal)(3)
Allow only a match/mismatch value for a “diagonal” position, and allow the “bottom” or “beside” positions to take linear gap values only(4)
For each computed cell box values, find the maximum score and let that be the pivot(5)
The pivot of a computed cell box directly affects the next cell boxes in the row or the column


## 2.1.1. Initialization

A sequence matrix is created withμ1+1 columns and μ2+1 rows in order for the initial matrix gap to be aligned where μ1 and μ2 are the lengths of arbitrary sequences, α and β, respectively. The letters of the sequence α fill in the horizontal axis, and similarly, the characters of β fill in the vertical axis of the sequence matrix created. Before the scoring begins from the upper left corner of the initialized matrix to the lower right corner of the matrix, the value P0,0=0 is assigned to the intersection of the first row and the first column of the matrix (i.e., the initial gap). The reason for the gap penalty for an alignment is because of the possibility of mutation which may insert or delete a string character from one of the sequences. Arrows that point in the direction of positional movement (diagonal and left or right) are placed in each cell box of the matrix and only terminate when all the cell boxes are completely filled.


## 2.1.2. Calculation of Cell Boxes in the Score Matrix

(1)
Fill the initialized gap values first on both the horizontal axis and the vertical axis with a defined constant gap value score(2)
Follow with the calculation of each cell box having the three position-dependent arrays (left/beside, right/bottom, or diagonal)(3)
Allow only a match/mismatch value for a “diagonal” position, and allow the “bottom” or “beside” positions to take linear gap values only(4)
For each computed cell box values, find the maximum score and let that be the pivot(5)
The pivot of a computed cell box directly affects the next cell boxes in the row or the column


## 2.2. Traceback

A simpler score matrix table that contains only the pivot of each cell box calculation is constructed from the original position-dependent arrays of the score matrix table. Arrow pointers are used to direct a path from the highest score or an optimal value in the matrix (which actually occurs at the lower right end corner of the matrix) and traced back to the next biggest value of the predecessors until we reach the intersection of the first row and the column with the initial gap.


## 2.3. Alignment

### 2.3.1. Alignment Generation from a Traceback

To write the sequence characters that appear from the optimal alignment path of the traceback stage, the following steps are followed:(1)
When the arrow is diagonal, write both characters in the alignment(2)
When the arrow is vertical, write the corresponding horizontal character, and in place of the vertical character, leave a gap(3)
When the arrow is horizontal, write the corresponding vertical character, and in place of the horizontal character, leave a gapThus, for both the vertical and horizontal arrow positions, one character and a gap are written for the alignment, where the gap explicitly replaces a character position in the alignment. An alignment can only be inferred as the best if the optimal value from the score matrix table corresponds to the alignment score calculation (based on the scoring scheme defined).


### 2.3.2. The Problem of Aligning Any Two Sequences

The problem of aligning any two sequences can be simplified as discovering the optimal means of aligning any two arbitrary sequences sayα and β such that the character “−” noted as a gap is filled into both α and β or either of them where(1)
Any single character inα matches a single character in β or a gap(2)
The final sum of scores from the scoring function over the aligned pairs and the gap penalties as given by the function of gap penalty is maximized


### 2.3.3. Letter Choice for Arbitrary Sequences

The letter choice of this study shall be that of DNA considered as a string of four characters of adenine—A, guanine—G, cytosine—C, and thymine—T.


## 2.3.1. Alignment Generation from a Traceback

To write the sequence characters that appear from the optimal alignment path of the traceback stage, the following steps are followed:(1)
When the arrow is diagonal, write both characters in the alignment(2)
When the arrow is vertical, write the corresponding horizontal character, and in place of the vertical character, leave a gap(3)
When the arrow is horizontal, write the corresponding vertical character, and in place of the horizontal character, leave a gapThus, for both the vertical and horizontal arrow positions, one character and a gap are written for the alignment, where the gap explicitly replaces a character position in the alignment. An alignment can only be inferred as the best if the optimal value from the score matrix table corresponds to the alignment score calculation (based on the scoring scheme defined).


## 2.3.2. The Problem of Aligning Any Two Sequences

The problem of aligning any two sequences can be simplified as discovering the optimal means of aligning any two arbitrary sequences sayα and β such that the character “−” noted as a gap is filled into both α and β or either of them where(1)
Any single character inα matches a single character in β or a gap(2)
The final sum of scores from the scoring function over the aligned pairs and the gap penalties as given by the function of gap penalty is maximized


## 2.3.3. Letter Choice for Arbitrary Sequences

The letter choice of this study shall be that of DNA considered as a string of four characters of adenine—A, guanine—G, cytosine—C, and thymine—T.


## 3. Scheme for Scoring

Definition 1.
The constant gap penalty,vk=g×k, where g is an assigned constant and k is the sequence length count of i=1,…,μ1 for the score matrix row and j=1,…,μ2 for the score matrix column. This is the penalty awarded to gaps and is also known as the linear gap function.Definition 2.
The affine gap penalty is the penalty awarded to gaps where a greatest consecutive sequence ofk gaps is given as vk=q+gk, where q is the penalty charged for opening the gap and g is the penalty charged for extending it.
Thus, more formally we define(1)
A constant linear gap as(2)vk=gk.(2)
An affine gap as(3)vk=q+gk,k≥1,0,k=0.
Altschul’s theory: assign positive scores to an identity and conserved replacements, and assign negative scores to less likely replacements.Remark 1.
Needleman and Wunsch use the “identity matrix” in scoring with 1 for a match and0 for a mismatch. Needleman–Wunsch’s score was criticised for not reflecting observations from the nature because purine-purine or pyrimidine-pyrimidine is less prone to be mutated in comparison with mutations of purine-pyrimidine. Because there is no definite defined score for DNA alignment, the choice of scoring for this study is +5 for a match, −1 for a mismatch, and −2 for a gap as proposed in [18] following the above theory.
More formally, let(4)σαi,βj=+5,forαi,βjcharacter match,−1,forαi,βjcharacter mismatch,∀i=1,…,μ1and∀j=1,…,μ2.
Also, let the linear gap penalty,vk=gk, where g is a constant of “−2” and k is the sequence length count of i=1,…,μ1 for the score matrix row and j=1,…,μ2 for the score matrix column.


## 4. Results and Discussion

### 4.1. Pattern Investigations in the Score Matrix of Needleman–Wunsch Algorithm

The sequencesα and β that will be used are arbitrary sample sequences that were chosen based on consideration of the following:(1)
μ1=μ2 (equal character length of sequences)(2)
μ1≠μ2 (unequal character length of sequences)


#### 4.1.1. Equal Character Lengthμ1=μ2=μ

Example 1.
Letα=CTTGA and β=CTAGA. Because the length of the sequence characters of α and β is μ1=μ2=5, respectively, we align α and β in a score matrix following the above formulation.(1)
Initialization:P0,0=0 for score matrix initialization, and then for the initial row pivot, Pmi,0=Pmi−1,0 + gap penalty, where ∀k=i, we find the gap penalty as follows:(5)fori=1,Pm1,0=P0,0+gap penalty,⟹0+−2=−2,fori=2,Pm2,0=Pm1,0+gap penalty,⟹−2+−2=−4,fori=3,Pm3,0=Pm2,0+gap penalty,⟹−4+−2=−6,fori=4,Pm4,0=Pm3,0+gap penalty,⟹−6+−2=−8,fori=5,Pm5,0=Pm4,0+gap penalty,⟹−8+−2=−10, and for the initial column pivot, Pm0,j=Pm0,j−1 + gap penalty, ∀k=j, the gap penalty is obtained as follows:(6)forj=1,Pm0,1=P0,0+gap penalty,⟹0+−2=−2,forj=2,Pm0,2=Pm0,1+gap penalty,⟹−2+−2=−4,forj=3,Pm0,3=Pm0,2+gap penalty,⟹−4+−2=−6,forj=4,Pm0,4=Pm0,3+gap penalty,⟹−6+−2=−8,forj=5,Pm0,5=Pm0,4+gap penalty,⟹−8+−2=−10.Before following with further calculation, some identification is placed on each cell box for easy noting as shown in Table1.Table 1
Identifying cell boxes of CTTGA and CTAGA.
CTTGA0−2−4−6−8−10C−2iiiiiiivvT−4viviiviiiixxA−6xixiixiiixivxvG−8xvixviixviiixixxxA−10xxixxiixxiiixxivxxv(2)
Cell box calculations:(7)Pm1,1=maxPD1,1=P0,0+σC,C=0+5=5,PR1,1=Pm0,1+gap=−2+−2=−4,PL1,1=Pm1,0+gap=−2+−2=−4.Remark 2.
σC,C in PD1,1 was “5” because that is the assigned score for matched characters. Pm1,1=maxPD1,1,PR1,1,PL1,1=max5−4−4=5.(8)Pm1,2=maxPD1,2=Pm0,1+σC,T=−2+−1=−3,PR1,2=Pm0,2+gap=−4+−2=−6,PL1,2=Pm1,1+gap=5+−2=3.Remark 3.
σC,T in PD1,2 was “−1” because that is the assigned score for mismatched characters. Pm1,2=maxPD1,2,PR1,2,PL1,2=max−3,−6,3=3.(9)Pm1,3=maxPD1,3=Pm0,2+σC,A=−4+−1=−5,PR1,3=Pm0,3+gap=−6+−2=−8,PL1,3=Pm1,2+gap=3+−2=1.Remark 4.
σC,A in PD1,3 was “−1” because that is the assigned score for mismatched characters. Pm1,3=maxPD1,3,PR1,3,PL1,3=max−5,−8,1=1.
Consequently, the recursion follows similarly until all the cell boxes are filled. In the event of a pivot tie in a cell box, one tie value is picked. For the tabular display, these notations are used interchangeably;PDi,j is the same as DV, PLi,j is the same as LV, PRi,j is the same as RV, and Pmi,j is the same as the pivot.


#### 4.1.2. Pattern Results for Equal Character Length

With reference to Tables1 and 2 and Figure 1,(1)
The filled-in cell boxes for column 1, i.e., cell boxesi,vi,xi,xvi,and xxi, have values coinciding with that of row 1, .i.e., cell boxes i,ii,iii,iv,and v(2)
The leading value (pivot) of each cell box in both row 1 and column 1 remains the same(3)
The bottom value in column 1 switches to become the beside value in row 1 and vice versa(4)
For each 3 pointed arrow intersecting any 4 cell boxes, the beside value of a 2nd cell box also coincides with the bottom value of a 3rd cell box(5)
For each cell box, the value of the preceding bottom value is less than the value of the immediate next adjacent diagonal valueTable 2
Filled-in table of CTTGA and CTAGA.
i.DV = 5LV = −4RV = −4Pivot = 5ii.DV = −3LV = 3RV = −6Pivot = 3iii.DV = −5LV = 1RV = −8Pivot = 1iv.DV = −7LV = −1RV = −10Pivot = −1v.DV = −9LV = −3RV = −12Pivot = −3vi.DV = −3LV = −6RV = 3Pivot = 3vii.DV = 10LV = 1RV = 1Pivot = 10viii.DV = 8LV = 8RV = −1Pivot = 8ix.DV = 0LV = 6RV = −3Pivot = 6x.DV = −2LV = 4RV = −5Pivot = 4xi.DV = −5LV = −8RV = 1Pivot = 1xii.DV = 2LV = −1RV = 8Pivot = 8xiii.DV = 9LV = 6RV = 6Pivot = 9xiv.DV = 7LV = 7RV = 4Pivot = 7xv.DV = 11LV = 5RV = 2Pivot = 11xvi.DV = −7LV = −10RV = −1Pivot = −1xvii.DV = 0LV = −3RV = 6Pivot = 6xviii.DV = 7LV = 4RV = 7Pivot = 7xix.DV = 14LV = 5RV = 5Pivot = 14xx.DV = 6LV = 12RV = 9Pivot = 12xxi.DV = −9LV = −12RV = −3Pivot = −3xxii.DV = −2LV = −5RV = 4Pivot = 4xxiii.DV = 5LV = 2RV = 5Pivot = 5xxiv.DV = 6LV = 3RV = 12Pivot = 12xxv.DV = 19LV = 10RV = 10Pivot = 19Figure 1
Score matrix of the cell boxes of CTTGA and CTAGA.


#### 4.1.3. Traceback and Alignment for Equal Character Length

The traceback and alignment stages for equal character length of sequences are, respectively, shown in this section.Figure2 shows the pivot of each cell box calculation of the score matrix table of CTTGA and CTAGA in Figure 1. Thus, Figure 2 is a simpler score matrix table constructed from the original score matrix table of CTTGA and CTAGA in Figure 1. The arrow pointers direct the path from the optimal value and traceback to the initialization value of zero. Based on the traceback and the diagonal direction of the arrow pointers, the alignment is written as(10)CTTGA,CTAGA.Figure 2
Traceback in the score matrix of CTTGA and CTAGA.To confirm the correctness of the alignment done, we check using calculations. Recall the scoring scheme: match = +5, mismatch = −1, and gap = −2. We have four alignment matches:C−C, T−T, G−G, and A−A and one mismatched alignment: T−A. Hence,(11)5+5−1+5+5=19,which is the same as the optimal value from the score matrix table. The alignment is thus optimal.


#### 4.1.4. Unequal Character Lengthμ1≠μ2

Example 2.
Supposeα = AGCTG and β TCAG, then to fill in the score matrix values of the cell boxes, the prior-stated recursive formulation is used. This results in Figures 3 and 4.Figure 3
Score matrix of AGCTG and TCAG.Figure 4
Labelling of the cell boxes of AGCTG and TCAG.


#### 4.1.5. Pattern Results for Unequal Character Length

(1)
The filled-in cell boxes for column 1, i.e.,i,vi,xi,and xvi cell boxes, have consistent values with that of row 1, i.e., i,ii,iii,and iv, up until where they terminate at v and at the inconsistent iii(2)
Except for where an inconsistency is noted atv and iii, the pivot values for each cell box of row 1 and column 1 remain the same(3)
For each 3 pointed arrows intersecting any 4 cell boxes, the beside value of a2nd cell box also coincides with the bottom value of a 3rd cell box(4)
For each cell box, the value of the preceding bottom value is seen to be always less than the value of the immediate next adjacent diagonal value


#### 4.1.6. Traceback and Alignment for Unequal Character Length

The traceback and alignment stages for the example on unequal character length of sequences are, respectively, shown below. Figure5 shows the pivot of each cell box calculation of the score matrix table of AGCTG and TCAG of Table 3. Based on the traceback and the direction of the arrow pointers, the alignment is written as(12)AGCTG,T−CAG.Figure 5
Traceback in the score matrix of AGCTG and TCAG.Table 3
Filled-in table of AGCTG and TCAG.
i.DV = −1LV = −4RV = −4Pivot = −1ii.DV = −3LV = −3RV = −6Pivot = −3iii.DV = −5LV = −5RV = −8Pivot = −5iv.DV = −1LV = −7RV = −10Pivot = −1v.DV = −9LV = −3RV = −12Pivot = −3vi.DV = −3LV = −6RV = −3Pivot = −3vii.DV = −2LV = −5RV = −5Pivot = −2viii.DV = 2LV = −4RV = −7Pivot = 2ix.DV = −6LV = 0RV = −3Pivot = 0x.DV = −2LV = −2RV = −5Pivot = −2xi.DV = 1LV = −8RV = −5Pivot = 1xii.DV = −4LV = −1RV = −4Pivot = −1xiii.DV = −3LV = −3RV = 0Pivot = 0xiv.DV = 1LV = −2RV = −2Pivot = −2xv.DV = −1LV = −1RV = −4Pivot = −1xvi.DV = −7LV = −10RV = −1Pivot = −1xvii.DV = 6LV = −3RV = −3Pivot = 6xviii.DV = −2LV = 4RV = −2Pivot = 4xix.DV = −1LV = 2RV = −1Pivot = 2xx.DV = 6LV = 0RV = −3Pivot = 6We check the correctness of the alignment done using calculations. Recall the scoring scheme: match = +5, mismatch = −1, and gap = −2. We have two alignment matches:G−G and C−C, two alignment mismatches: AT and TA, and one gapped alignment: G−. Hence,(13)−1−2+5−1+5=6,which is the same as the optimal value from the score matrix table. The alignment is thus optimal.


### 4.2. Propositions and Proofs for Equal Sequence Length

The following propositions area priori results deduced from the pattern results of equal character length of sequences.Definition 3.
Let the linear gap penalty bevk=gk, where g is a constant of −2 and k is the sequence length count of k=1,…,μ1 for the score matrix row and k=1,…,μ2 for the score matrix column.Definition 4.
DefineP0,0=0 to be the initialization pivot for the score matrix.Definition 5.
DefinePmi,0=Pmi−1,0 + gap penalty, ∀i=1,…,μ1, to be the initial row pivot for the score matrix.Definition 6.
DefinePm0,j=Pm0,j−1 + gap penalty, ∀j=1,…,μ2, to be the initial column pivot for the score matrix.Definition 7.
Define(14)Pmi,j=maxPDi,j=Pmi−1,j−1+σαi,βj,PRi,j=Pmi−1,j+gap penalty,PLi,j=Pmi,j−1+gap penalty,∀i=1,…,μ1 and ∀j=1,…,μ2, where Pmi,j is the pivot for each cell box calculation, PDi,j=Pmi−1,j−1+σαi,βj is the diagonal value of a cell box, PRi,j=Pmi−1,j+ gap penalty is the right value of a cell box, PLi,j=Pmi,j−1+ gap penalty is the left value of a cell box, and σαi,βj is the score for aligning the sequence characters of αi and βj.Definition 8.
Define(15)σαi,βj=+5,forαi,βjcharacter match,−1,forαi,βjcharacter mismatch,∀i=1,…,μ1 and ∀j=1,…,μ2.Proposition 2.
Filled-in cell boxes forPm1,j,∀j=1,…,μ2 are analogous to filled-in cell boxes for Pmi,1,∀i=1,…,μ1 for equal length comparison of sequences.Proof.
By Definition7, we have(16)Pm1,j=maxPD1,j=Pm0,j−1+σα1,βj,PR1,j=Pm0,j+gap,PL1,j=Pm1,j−1+gap,Pmi,1=maxPDi,1=Pmi−1,0+σαi,β1,PRi,1=Pmi−1,1+gap,PLi,1=Pmi,0+gap,∀i,j=1,…,μ since μ1=μ2=μ. Again, by Definitions 5 and 6,(17)Pmi,0=Pmi−1,0+gap,⟹PLi,1=Pmi,0+gap=Pmi−1,0+gap+gap,also,(18)Pm0,j=Pm0,j−1+gap,⟹PR1,j=Pm0,j+gap=Pm0,j−1+gap+gap.
Using Definitions5 and 6 and applying induction, Pm1,0=P0,0+gap and Pm0,1=P0,0+gap, thus Pm1,0=Pm0,1 is true. Assume Pmk,0=Pm0,k is always true, then(19)Pmk+1,0=Pmk,0+gap=Pm0,k+gap=Pm0,k+1,∴Pmi,0=Pm0,j.
Recall that the gap is constant, so we writePLi,1=Pmi,0+gap=PR1,j=Pm0,j+gap, thus PLi,1=PR1,j which completes the first part of our proof.
Again, fromPL1,j=Pm1,j−1+gap, PRi,1=Pmi−1,1+gap, and by induction, let i=1=j, then(20)PL1,j=Pm1,0+gap=P0,0+gap+gap=P0,0+2gaps,PRi,1=Pm0,1+gap=P0,0+gap+gap=P0,0+2gaps.
AssumePmk,0=Pm0,k, then(21)Pmk+1,0=Pmk,0+gap=Pm0,k+gap=Pm0,k+1,∴PRi,1=PL1,j,wherei=j,which completes the second part of our proof.
Recall,(22)PLi,1=Pmi−1,0+2gaps,PR1,j=Pm0,j−1+2gaps,PLi,1=PR1,jwas established.
It follows thatPmi−1,0=Pm0,j−1 is obvious. Thus, PD1,j=Pm0,j−1+σα1,βj and PDi,1=Pmi−1,0+σαi,β1. We are left to show that σα1,βj=σαi,β1.
Fori=j=1, σα1,βj=σαi,β1 since α1 and β1 match. For i=j≠1, α1 and βj mismatch and αi and β1 also mismatch. Thus,(23)σα1,βj=σαi,β1,∀i,j∈1,…,μ.
Hence,PD1,j=PDi,1 since Pmi−1,0=Pm0,j−1.Corollary 3.
The right value of filled-in cell boxes forPm1,j,∀j=1,…,μ2 becomes the left value of filled-in cell boxes for Pmi,1,∀i=1,…,μ1 and vice versa.Proof.
From Proposition2 and Definitions 5–7, it is clear that(24)PLi,1=PR1,j,PRi,1=PL1,j,wherei=j.Corollary 4.
The pivot values,Pm1,j,∀j=1,…,μ2 and Pmi,1,∀i=1,…,μ1, are the same for comparison of equal length of sequences.Proof.
By Definition7,(25)Pm1,j=maxPD1,j,PR1,j,PL1,j,∀j=1,…,μ2,Pmi,1=maxPDi,1,PRi,1,PLi,1,∀i=1,…,μ1,and by Proposition 2, we can write that Pm1,j=Pmi,1. Hence, it is proved.Proposition 5.
For each three pointed arrows intersecting any four cell boxes, the left value of a 2nd cell box corresponds to the right value of a 3rd cell box.Proof.
LetPmi,j,Pmi+1,j,Pmi,j+1, and Pmi+1,j+1 be any four cell boxes, then we are to show that PLi,j+1=PRi+1,j. By Definition 7,(26)Pmi,j=maxPDi,j=Pmi−1,j−1+σαi,βj,PRi,j=Pmi−1,j+gap penalty,PLi,j=Pmi,j−1+gap penalty,Pmi+1,j=maxPDi+1,j=Pmi,j−1+σαi+1,βj,PRi+1,j=Pmi,j+gap penalty,PLi+1,j=Pmi+1,j−1+gap penalty,Pmi,j+1=maxPDi,j+1=Pmi−1,j+σαi,βj+1,PRi,j+1=Pmi−1,j+1+gap penalty,PLi,j+1=Pmi,j+gap penalty,Pmi+1,j+1=maxPDi+1,j+1=Pmi,j+σαi+1,βj+1,PRi+1,j+1=Pmi,j+1+gap penalty,PLi+1,j+1=Pmi+1,j+gap penalty,PRi+1,j=Pmi,j+gap penalty,PLi,j+1=Pmi,j+gap penalty.
Since the linear gap penalty is equal in both cases and it is obvious thatPmi,j is the same in both cases, we write PLi,j+1=PRi+1,j.Corollary 6.
For any two adjacent row cell boxes, the right value of a preceding cell box is less than the diagonal value of the next cell box.Proof.
LetPmi,j and Pmi,j+1 be any two adjacent cell boxes. Then, by Proposition 5, we write(27)PRi,j=Pmi−1,j+gap penalty,PDi,j+1=Pmi−1,j+σαi,βj+1.
We are left to show thatgap penalty<σαi,βj+1.Remark 5.
By Altschul’s theory, a match and mismatch are chosen to be greater than a gap penalty. We recall the scoring scheme of the constantg being “−2” in the linear gap penalty gk and the diagonal score being “−1” when there is a mismatch and “+5” when there is a match.
For anyk count, ∀k=1,…,μ, the linear gap penalty gk decreases, and thus the gap penalty can never be greater than or equal to any of the diagonal scores allocated for match and mismatch. Thus,(28)gap penaltyσαi,βj+1︸mismatch diagonal scorematch diagonal score,∀i,j=1,…,μ.
Hence,PRi,j<PDi,j+1,∀i,j=1,…,μ.


### 4.3. Proposition and Proof for Unequal Sequence Length

The following proposition holdsa priori from the pattern results of unequal character length of sequences. We state and prove the following general results by adhering to the same definitions stated earlier under the equal character length of sequences.Proposition 7.
For each three pointed arrows intersecting any four cell boxes, the left value of a 2nd cell box corresponds to the right value of a 3rd cell box.Proof.
LetPmi,j,Pmi+1,j,Pmi,j+1, and Pmi+1,j+1 be any four cell boxes, then we are to show that Pmi+1,j=Pmi,j+1. Refer to the proof of Proposition 5. Despite the unequal sequence length of μ1≠μ2, the supposed disparity in length has no bearing on the proof.Corollary 8.
For any two adjacent row cell boxes, the right value of a preceding cell box is less than the diagonal value of the next cell box.Proof.
Refer to the proof of Corollary6. Again, despite the unequal sequence length of μ1≠μ2, the supposed disparity in length has no bearing on the proof.


## 4.1. Pattern Investigations in the Score Matrix of Needleman–Wunsch Algorithm

The sequencesα and β that will be used are arbitrary sample sequences that were chosen based on consideration of the following:(1)
μ1=μ2 (equal character length of sequences)(2)
μ1≠μ2 (unequal character length of sequences)


### 4.1.1. Equal Character Lengthμ1=μ2=μ

Example 1.
Letα=CTTGA and β=CTAGA. Because the length of the sequence characters of α and β is μ1=μ2=5, respectively, we align α and β in a score matrix following the above formulation.(1)
Initialization:P0,0=0 for score matrix initialization, and then for the initial row pivot, Pmi,0=Pmi−1,0 + gap penalty, where ∀k=i, we find the gap penalty as follows:(5)fori=1,Pm1,0=P0,0+gap penalty,⟹0+−2=−2,fori=2,Pm2,0=Pm1,0+gap penalty,⟹−2+−2=−4,fori=3,Pm3,0=Pm2,0+gap penalty,⟹−4+−2=−6,fori=4,Pm4,0=Pm3,0+gap penalty,⟹−6+−2=−8,fori=5,Pm5,0=Pm4,0+gap penalty,⟹−8+−2=−10, and for the initial column pivot, Pm0,j=Pm0,j−1 + gap penalty, ∀k=j, the gap penalty is obtained as follows:(6)forj=1,Pm0,1=P0,0+gap penalty,⟹0+−2=−2,forj=2,Pm0,2=Pm0,1+gap penalty,⟹−2+−2=−4,forj=3,Pm0,3=Pm0,2+gap penalty,⟹−4+−2=−6,forj=4,Pm0,4=Pm0,3+gap penalty,⟹−6+−2=−8,forj=5,Pm0,5=Pm0,4+gap penalty,⟹−8+−2=−10.Before following with further calculation, some identification is placed on each cell box for easy noting as shown in Table1.Table 1
Identifying cell boxes of CTTGA and CTAGA.
CTTGA0−2−4−6−8−10C−2iiiiiiivvT−4viviiviiiixxA−6xixiixiiixivxvG−8xvixviixviiixixxxA−10xxixxiixxiiixxivxxv(2)
Cell box calculations:(7)Pm1,1=maxPD1,1=P0,0+σC,C=0+5=5,PR1,1=Pm0,1+gap=−2+−2=−4,PL1,1=Pm1,0+gap=−2+−2=−4.Remark 2.
σC,C in PD1,1 was “5” because that is the assigned score for matched characters. Pm1,1=maxPD1,1,PR1,1,PL1,1=max5−4−4=5.(8)Pm1,2=maxPD1,2=Pm0,1+σC,T=−2+−1=−3,PR1,2=Pm0,2+gap=−4+−2=−6,PL1,2=Pm1,1+gap=5+−2=3.Remark 3.
σC,T in PD1,2 was “−1” because that is the assigned score for mismatched characters. Pm1,2=maxPD1,2,PR1,2,PL1,2=max−3,−6,3=3.(9)Pm1,3=maxPD1,3=Pm0,2+σC,A=−4+−1=−5,PR1,3=Pm0,3+gap=−6+−2=−8,PL1,3=Pm1,2+gap=3+−2=1.Remark 4.
σC,A in PD1,3 was “−1” because that is the assigned score for mismatched characters. Pm1,3=maxPD1,3,PR1,3,PL1,3=max−5,−8,1=1.
Consequently, the recursion follows similarly until all the cell boxes are filled. In the event of a pivot tie in a cell box, one tie value is picked. For the tabular display, these notations are used interchangeably;PDi,j is the same as DV, PLi,j is the same as LV, PRi,j is the same as RV, and Pmi,j is the same as the pivot.


### 4.1.2. Pattern Results for Equal Character Length

With reference to Tables1 and 2 and Figure 1,(1)
The filled-in cell boxes for column 1, i.e., cell boxesi,vi,xi,xvi,and xxi, have values coinciding with that of row 1, .i.e., cell boxes i,ii,iii,iv,and v(2)
The leading value (pivot) of each cell box in both row 1 and column 1 remains the same(3)
The bottom value in column 1 switches to become the beside value in row 1 and vice versa(4)
For each 3 pointed arrow intersecting any 4 cell boxes, the beside value of a 2nd cell box also coincides with the bottom value of a 3rd cell box(5)
For each cell box, the value of the preceding bottom value is less than the value of the immediate next adjacent diagonal valueTable 2
Filled-in table of CTTGA and CTAGA.
i.DV = 5LV = −4RV = −4Pivot = 5ii.DV = −3LV = 3RV = −6Pivot = 3iii.DV = −5LV = 1RV = −8Pivot = 1iv.DV = −7LV = −1RV = −10Pivot = −1v.DV = −9LV = −3RV = −12Pivot = −3vi.DV = −3LV = −6RV = 3Pivot = 3vii.DV = 10LV = 1RV = 1Pivot = 10viii.DV = 8LV = 8RV = −1Pivot = 8ix.DV = 0LV = 6RV = −3Pivot = 6x.DV = −2LV = 4RV = −5Pivot = 4xi.DV = −5LV = −8RV = 1Pivot = 1xii.DV = 2LV = −1RV = 8Pivot = 8xiii.DV = 9LV = 6RV = 6Pivot = 9xiv.DV = 7LV = 7RV = 4Pivot = 7xv.DV = 11LV = 5RV = 2Pivot = 11xvi.DV = −7LV = −10RV = −1Pivot = −1xvii.DV = 0LV = −3RV = 6Pivot = 6xviii.DV = 7LV = 4RV = 7Pivot = 7xix.DV = 14LV = 5RV = 5Pivot = 14xx.DV = 6LV = 12RV = 9Pivot = 12xxi.DV = −9LV = −12RV = −3Pivot = −3xxii.DV = −2LV = −5RV = 4Pivot = 4xxiii.DV = 5LV = 2RV = 5Pivot = 5xxiv.DV = 6LV = 3RV = 12Pivot = 12xxv.DV = 19LV = 10RV = 10Pivot = 19Figure 1
Score matrix of the cell boxes of CTTGA and CTAGA.


### 4.1.3. Traceback and Alignment for Equal Character Length

The traceback and alignment stages for equal character length of sequences are, respectively, shown in this section.Figure2 shows the pivot of each cell box calculation of the score matrix table of CTTGA and CTAGA in Figure 1. Thus, Figure 2 is a simpler score matrix table constructed from the original score matrix table of CTTGA and CTAGA in Figure 1. The arrow pointers direct the path from the optimal value and traceback to the initialization value of zero. Based on the traceback and the diagonal direction of the arrow pointers, the alignment is written as(10)CTTGA,CTAGA.Figure 2
Traceback in the score matrix of CTTGA and CTAGA.To confirm the correctness of the alignment done, we check using calculations. Recall the scoring scheme: match = +5, mismatch = −1, and gap = −2. We have four alignment matches:C−C, T−T, G−G, and A−A and one mismatched alignment: T−A. Hence,(11)5+5−1+5+5=19,which is the same as the optimal value from the score matrix table. The alignment is thus optimal.


### 4.1.4. Unequal Character Lengthμ1≠μ2

Example 2.
Supposeα = AGCTG and β TCAG, then to fill in the score matrix values of the cell boxes, the prior-stated recursive formulation is used. This results in Figures 3 and 4.Figure 3
Score matrix of AGCTG and TCAG.Figure 4
Labelling of the cell boxes of AGCTG and TCAG.


### 4.1.5. Pattern Results for Unequal Character Length

(1)
The filled-in cell boxes for column 1, i.e.,i,vi,xi,and xvi cell boxes, have consistent values with that of row 1, i.e., i,ii,iii,and iv, up until where they terminate at v and at the inconsistent iii(2)
Except for where an inconsistency is noted atv and iii, the pivot values for each cell box of row 1 and column 1 remain the same(3)
For each 3 pointed arrows intersecting any 4 cell boxes, the beside value of a2nd cell box also coincides with the bottom value of a 3rd cell box(4)
For each cell box, the value of the preceding bottom value is seen to be always less than the value of the immediate next adjacent diagonal value


### 4.1.6. Traceback and Alignment for Unequal Character Length

The traceback and alignment stages for the example on unequal character length of sequences are, respectively, shown below. Figure5 shows the pivot of each cell box calculation of the score matrix table of AGCTG and TCAG of Table 3. Based on the traceback and the direction of the arrow pointers, the alignment is written as(12)AGCTG,T−CAG.Figure 5
Traceback in the score matrix of AGCTG and TCAG.Table 3
Filled-in table of AGCTG and TCAG.
i.DV = −1LV = −4RV = −4Pivot = −1ii.DV = −3LV = −3RV = −6Pivot = −3iii.DV = −5LV = −5RV = −8Pivot = −5iv.DV = −1LV = −7RV = −10Pivot = −1v.DV = −9LV = −3RV = −12Pivot = −3vi.DV = −3LV = −6RV = −3Pivot = −3vii.DV = −2LV = −5RV = −5Pivot = −2viii.DV = 2LV = −4RV = −7Pivot = 2ix.DV = −6LV = 0RV = −3Pivot = 0x.DV = −2LV = −2RV = −5Pivot = −2xi.DV = 1LV = −8RV = −5Pivot = 1xii.DV = −4LV = −1RV = −4Pivot = −1xiii.DV = −3LV = −3RV = 0Pivot = 0xiv.DV = 1LV = −2RV = −2Pivot = −2xv.DV = −1LV = −1RV = −4Pivot = −1xvi.DV = −7LV = −10RV = −1Pivot = −1xvii.DV = 6LV = −3RV = −3Pivot = 6xviii.DV = −2LV = 4RV = −2Pivot = 4xix.DV = −1LV = 2RV = −1Pivot = 2xx.DV = 6LV = 0RV = −3Pivot = 6We check the correctness of the alignment done using calculations. Recall the scoring scheme: match = +5, mismatch = −1, and gap = −2. We have two alignment matches:G−G and C−C, two alignment mismatches: AT and TA, and one gapped alignment: G−. Hence,(13)−1−2+5−1+5=6,which is the same as the optimal value from the score matrix table. The alignment is thus optimal.


## 4.1.1. Equal Character Lengthμ1=μ2=μ

Example 1.
Letα=CTTGA and β=CTAGA. Because the length of the sequence characters of α and β is μ1=μ2=5, respectively, we align α and β in a score matrix following the above formulation.(1)
Initialization:P0,0=0 for score matrix initialization, and then for the initial row pivot, Pmi,0=Pmi−1,0 + gap penalty, where ∀k=i, we find the gap penalty as follows:(5)fori=1,Pm1,0=P0,0+gap penalty,⟹0+−2=−2,fori=2,Pm2,0=Pm1,0+gap penalty,⟹−2+−2=−4,fori=3,Pm3,0=Pm2,0+gap penalty,⟹−4+−2=−6,fori=4,Pm4,0=Pm3,0+gap penalty,⟹−6+−2=−8,fori=5,Pm5,0=Pm4,0+gap penalty,⟹−8+−2=−10, and for the initial column pivot, Pm0,j=Pm0,j−1 + gap penalty, ∀k=j, the gap penalty is obtained as follows:(6)forj=1,Pm0,1=P0,0+gap penalty,⟹0+−2=−2,forj=2,Pm0,2=Pm0,1+gap penalty,⟹−2+−2=−4,forj=3,Pm0,3=Pm0,2+gap penalty,⟹−4+−2=−6,forj=4,Pm0,4=Pm0,3+gap penalty,⟹−6+−2=−8,forj=5,Pm0,5=Pm0,4+gap penalty,⟹−8+−2=−10.Before following with further calculation, some identification is placed on each cell box for easy noting as shown in Table1.Table 1
Identifying cell boxes of CTTGA and CTAGA.
CTTGA0−2−4−6−8−10C−2iiiiiiivvT−4viviiviiiixxA−6xixiixiiixivxvG−8xvixviixviiixixxxA−10xxixxiixxiiixxivxxv(2)
Cell box calculations:(7)Pm1,1=maxPD1,1=P0,0+σC,C=0+5=5,PR1,1=Pm0,1+gap=−2+−2=−4,PL1,1=Pm1,0+gap=−2+−2=−4.Remark 2.
σC,C in PD1,1 was “5” because that is the assigned score for matched characters. Pm1,1=maxPD1,1,PR1,1,PL1,1=max5−4−4=5.(8)Pm1,2=maxPD1,2=Pm0,1+σC,T=−2+−1=−3,PR1,2=Pm0,2+gap=−4+−2=−6,PL1,2=Pm1,1+gap=5+−2=3.Remark 3.
σC,T in PD1,2 was “−1” because that is the assigned score for mismatched characters. Pm1,2=maxPD1,2,PR1,2,PL1,2=max−3,−6,3=3.(9)Pm1,3=maxPD1,3=Pm0,2+σC,A=−4+−1=−5,PR1,3=Pm0,3+gap=−6+−2=−8,PL1,3=Pm1,2+gap=3+−2=1.Remark 4.
σC,A in PD1,3 was “−1” because that is the assigned score for mismatched characters. Pm1,3=maxPD1,3,PR1,3,PL1,3=max−5,−8,1=1.
Consequently, the recursion follows similarly until all the cell boxes are filled. In the event of a pivot tie in a cell box, one tie value is picked. For the tabular display, these notations are used interchangeably;PDi,j is the same as DV, PLi,j is the same as LV, PRi,j is the same as RV, and Pmi,j is the same as the pivot.


## 4.1.2. Pattern Results for Equal Character Length

With reference to Tables1 and 2 and Figure 1,(1)
The filled-in cell boxes for column 1, i.e., cell boxesi,vi,xi,xvi,and xxi, have values coinciding with that of row 1, .i.e., cell boxes i,ii,iii,iv,and v(2)
The leading value (pivot) of each cell box in both row 1 and column 1 remains the same(3)
The bottom value in column 1 switches to become the beside value in row 1 and vice versa(4)
For each 3 pointed arrow intersecting any 4 cell boxes, the beside value of a 2nd cell box also coincides with the bottom value of a 3rd cell box(5)
For each cell box, the value of the preceding bottom value is less than the value of the immediate next adjacent diagonal valueTable 2
Filled-in table of CTTGA and CTAGA.
i.DV = 5LV = −4RV = −4Pivot = 5ii.DV = −3LV = 3RV = −6Pivot = 3iii.DV = −5LV = 1RV = −8Pivot = 1iv.DV = −7LV = −1RV = −10Pivot = −1v.DV = −9LV = −3RV = −12Pivot = −3vi.DV = −3LV = −6RV = 3Pivot = 3vii.DV = 10LV = 1RV = 1Pivot = 10viii.DV = 8LV = 8RV = −1Pivot = 8ix.DV = 0LV = 6RV = −3Pivot = 6x.DV = −2LV = 4RV = −5Pivot = 4xi.DV = −5LV = −8RV = 1Pivot = 1xii.DV = 2LV = −1RV = 8Pivot = 8xiii.DV = 9LV = 6RV = 6Pivot = 9xiv.DV = 7LV = 7RV = 4Pivot = 7xv.DV = 11LV = 5RV = 2Pivot = 11xvi.DV = −7LV = −10RV = −1Pivot = −1xvii.DV = 0LV = −3RV = 6Pivot = 6xviii.DV = 7LV = 4RV = 7Pivot = 7xix.DV = 14LV = 5RV = 5Pivot = 14xx.DV = 6LV = 12RV = 9Pivot = 12xxi.DV = −9LV = −12RV = −3Pivot = −3xxii.DV = −2LV = −5RV = 4Pivot = 4xxiii.DV = 5LV = 2RV = 5Pivot = 5xxiv.DV = 6LV = 3RV = 12Pivot = 12xxv.DV = 19LV = 10RV = 10Pivot = 19Figure 1
Score matrix of the cell boxes of CTTGA and CTAGA.


## 4.1.3. Traceback and Alignment for Equal Character Length

The traceback and alignment stages for equal character length of sequences are, respectively, shown in this section.Figure2 shows the pivot of each cell box calculation of the score matrix table of CTTGA and CTAGA in Figure 1. Thus, Figure 2 is a simpler score matrix table constructed from the original score matrix table of CTTGA and CTAGA in Figure 1. The arrow pointers direct the path from the optimal value and traceback to the initialization value of zero. Based on the traceback and the diagonal direction of the arrow pointers, the alignment is written as(10)CTTGA,CTAGA.Figure 2
Traceback in the score matrix of CTTGA and CTAGA.To confirm the correctness of the alignment done, we check using calculations. Recall the scoring scheme: match = +5, mismatch = −1, and gap = −2. We have four alignment matches:C−C, T−T, G−G, and A−A and one mismatched alignment: T−A. Hence,(11)5+5−1+5+5=19,which is the same as the optimal value from the score matrix table. The alignment is thus optimal.


## 4.1.4. Unequal Character Lengthμ1≠μ2

Example 2.
Supposeα = AGCTG and β TCAG, then to fill in the score matrix values of the cell boxes, the prior-stated recursive formulation is used. This results in Figures 3 and 4.Figure 3
Score matrix of AGCTG and TCAG.Figure 4
Labelling of the cell boxes of AGCTG and TCAG.


## 4.1.5. Pattern Results for Unequal Character Length

(1)
The filled-in cell boxes for column 1, i.e.,i,vi,xi,and xvi cell boxes, have consistent values with that of row 1, i.e., i,ii,iii,and iv, up until where they terminate at v and at the inconsistent iii(2)
Except for where an inconsistency is noted atv and iii, the pivot values for each cell box of row 1 and column 1 remain the same(3)
For each 3 pointed arrows intersecting any 4 cell boxes, the beside value of a2nd cell box also coincides with the bottom value of a 3rd cell box(4)
For each cell box, the value of the preceding bottom value is seen to be always less than the value of the immediate next adjacent diagonal value


## 4.1.6. Traceback and Alignment for Unequal Character Length

The traceback and alignment stages for the example on unequal character length of sequences are, respectively, shown below. Figure5 shows the pivot of each cell box calculation of the score matrix table of AGCTG and TCAG of Table 3. Based on the traceback and the direction of the arrow pointers, the alignment is written as(12)AGCTG,T−CAG.Figure 5
Traceback in the score matrix of AGCTG and TCAG.Table 3
Filled-in table of AGCTG and TCAG.
i.DV = −1LV = −4RV = −4Pivot = −1ii.DV = −3LV = −3RV = −6Pivot = −3iii.DV = −5LV = −5RV = −8Pivot = −5iv.DV = −1LV = −7RV = −10Pivot = −1v.DV = −9LV = −3RV = −12Pivot = −3vi.DV = −3LV = −6RV = −3Pivot = −3vii.DV = −2LV = −5RV = −5Pivot = −2viii.DV = 2LV = −4RV = −7Pivot = 2ix.DV = −6LV = 0RV = −3Pivot = 0x.DV = −2LV = −2RV = −5Pivot = −2xi.DV = 1LV = −8RV = −5Pivot = 1xii.DV = −4LV = −1RV = −4Pivot = −1xiii.DV = −3LV = −3RV = 0Pivot = 0xiv.DV = 1LV = −2RV = −2Pivot = −2xv.DV = −1LV = −1RV = −4Pivot = −1xvi.DV = −7LV = −10RV = −1Pivot = −1xvii.DV = 6LV = −3RV = −3Pivot = 6xviii.DV = −2LV = 4RV = −2Pivot = 4xix.DV = −1LV = 2RV = −1Pivot = 2xx.DV = 6LV = 0RV = −3Pivot = 6We check the correctness of the alignment done using calculations. Recall the scoring scheme: match = +5, mismatch = −1, and gap = −2. We have two alignment matches:G−G and C−C, two alignment mismatches: AT and TA, and one gapped alignment: G−. Hence,(13)−1−2+5−1+5=6,which is the same as the optimal value from the score matrix table. The alignment is thus optimal.


## 4.2. Propositions and Proofs for Equal Sequence Length

The following propositions area priori results deduced from the pattern results of equal character length of sequences.Definition 3.
Let the linear gap penalty bevk=gk, where g is a constant of −2 and k is the sequence length count of k=1,…,μ1 for the score matrix row and k=1,…,μ2 for the score matrix column.Definition 4.
DefineP0,0=0 to be the initialization pivot for the score matrix.Definition 5.
DefinePmi,0=Pmi−1,0 + gap penalty, ∀i=1,…,μ1, to be the initial row pivot for the score matrix.Definition 6.
DefinePm0,j=Pm0,j−1 + gap penalty, ∀j=1,…,μ2, to be the initial column pivot for the score matrix.Definition 7.
Define(14)Pmi,j=maxPDi,j=Pmi−1,j−1+σαi,βj,PRi,j=Pmi−1,j+gap penalty,PLi,j=Pmi,j−1+gap penalty,∀i=1,…,μ1 and ∀j=1,…,μ2, where Pmi,j is the pivot for each cell box calculation, PDi,j=Pmi−1,j−1+σαi,βj is the diagonal value of a cell box, PRi,j=Pmi−1,j+ gap penalty is the right value of a cell box, PLi,j=Pmi,j−1+ gap penalty is the left value of a cell box, and σαi,βj is the score for aligning the sequence characters of αi and βj.Definition 8.
Define(15)σαi,βj=+5,forαi,βjcharacter match,−1,forαi,βjcharacter mismatch,∀i=1,…,μ1 and ∀j=1,…,μ2.Proposition 2.
Filled-in cell boxes forPm1,j,∀j=1,…,μ2 are analogous to filled-in cell boxes for Pmi,1,∀i=1,…,μ1 for equal length comparison of sequences.Proof.
By Definition7, we have(16)Pm1,j=maxPD1,j=Pm0,j−1+σα1,βj,PR1,j=Pm0,j+gap,PL1,j=Pm1,j−1+gap,Pmi,1=maxPDi,1=Pmi−1,0+σαi,β1,PRi,1=Pmi−1,1+gap,PLi,1=Pmi,0+gap,∀i,j=1,…,μ since μ1=μ2=μ. Again, by Definitions 5 and 6,(17)Pmi,0=Pmi−1,0+gap,⟹PLi,1=Pmi,0+gap=Pmi−1,0+gap+gap,also,(18)Pm0,j=Pm0,j−1+gap,⟹PR1,j=Pm0,j+gap=Pm0,j−1+gap+gap.
Using Definitions5 and 6 and applying induction, Pm1,0=P0,0+gap and Pm0,1=P0,0+gap, thus Pm1,0=Pm0,1 is true. Assume Pmk,0=Pm0,k is always true, then(19)Pmk+1,0=Pmk,0+gap=Pm0,k+gap=Pm0,k+1,∴Pmi,0=Pm0,j.
Recall that the gap is constant, so we writePLi,1=Pmi,0+gap=PR1,j=Pm0,j+gap, thus PLi,1=PR1,j which completes the first part of our proof.
Again, fromPL1,j=Pm1,j−1+gap, PRi,1=Pmi−1,1+gap, and by induction, let i=1=j, then(20)PL1,j=Pm1,0+gap=P0,0+gap+gap=P0,0+2gaps,PRi,1=Pm0,1+gap=P0,0+gap+gap=P0,0+2gaps.
AssumePmk,0=Pm0,k, then(21)Pmk+1,0=Pmk,0+gap=Pm0,k+gap=Pm0,k+1,∴PRi,1=PL1,j,wherei=j,which completes the second part of our proof.
Recall,(22)PLi,1=Pmi−1,0+2gaps,PR1,j=Pm0,j−1+2gaps,PLi,1=PR1,jwas established.
It follows thatPmi−1,0=Pm0,j−1 is obvious. Thus, PD1,j=Pm0,j−1+σα1,βj and PDi,1=Pmi−1,0+σαi,β1. We are left to show that σα1,βj=σαi,β1.
Fori=j=1, σα1,βj=σαi,β1 since α1 and β1 match. For i=j≠1, α1 and βj mismatch and αi and β1 also mismatch. Thus,(23)σα1,βj=σαi,β1,∀i,j∈1,…,μ.
Hence,PD1,j=PDi,1 since Pmi−1,0=Pm0,j−1.Corollary 3.
The right value of filled-in cell boxes forPm1,j,∀j=1,…,μ2 becomes the left value of filled-in cell boxes for Pmi,1,∀i=1,…,μ1 and vice versa.Proof.
From Proposition2 and Definitions 5–7, it is clear that(24)PLi,1=PR1,j,PRi,1=PL1,j,wherei=j.Corollary 4.
The pivot values,Pm1,j,∀j=1,…,μ2 and Pmi,1,∀i=1,…,μ1, are the same for comparison of equal length of sequences.Proof.
By Definition7,(25)Pm1,j=maxPD1,j,PR1,j,PL1,j,∀j=1,…,μ2,Pmi,1=maxPDi,1,PRi,1,PLi,1,∀i=1,…,μ1,and by Proposition 2, we can write that Pm1,j=Pmi,1. Hence, it is proved.Proposition 5.
For each three pointed arrows intersecting any four cell boxes, the left value of a 2nd cell box corresponds to the right value of a 3rd cell box.Proof.
LetPmi,j,Pmi+1,j,Pmi,j+1, and Pmi+1,j+1 be any four cell boxes, then we are to show that PLi,j+1=PRi+1,j. By Definition 7,(26)Pmi,j=maxPDi,j=Pmi−1,j−1+σαi,βj,PRi,j=Pmi−1,j+gap penalty,PLi,j=Pmi,j−1+gap penalty,Pmi+1,j=maxPDi+1,j=Pmi,j−1+σαi+1,βj,PRi+1,j=Pmi,j+gap penalty,PLi+1,j=Pmi+1,j−1+gap penalty,Pmi,j+1=maxPDi,j+1=Pmi−1,j+σαi,βj+1,PRi,j+1=Pmi−1,j+1+gap penalty,PLi,j+1=Pmi,j+gap penalty,Pmi+1,j+1=maxPDi+1,j+1=Pmi,j+σαi+1,βj+1,PRi+1,j+1=Pmi,j+1+gap penalty,PLi+1,j+1=Pmi+1,j+gap penalty,PRi+1,j=Pmi,j+gap penalty,PLi,j+1=Pmi,j+gap penalty.
Since the linear gap penalty is equal in both cases and it is obvious thatPmi,j is the same in both cases, we write PLi,j+1=PRi+1,j.Corollary 6.
For any two adjacent row cell boxes, the right value of a preceding cell box is less than the diagonal value of the next cell box.Proof.
LetPmi,j and Pmi,j+1 be any two adjacent cell boxes. Then, by Proposition 5, we write(27)PRi,j=Pmi−1,j+gap penalty,PDi,j+1=Pmi−1,j+σαi,βj+1.
We are left to show thatgap penalty<σαi,βj+1.Remark 5.
By Altschul’s theory, a match and mismatch are chosen to be greater than a gap penalty. We recall the scoring scheme of the constantg being “−2” in the linear gap penalty gk and the diagonal score being “−1” when there is a mismatch and “+5” when there is a match.
For anyk count, ∀k=1,…,μ, the linear gap penalty gk decreases, and thus the gap penalty can never be greater than or equal to any of the diagonal scores allocated for match and mismatch. Thus,(28)gap penaltyσαi,βj+1︸mismatch diagonal scorematch diagonal score,∀i,j=1,…,μ.
Hence,PRi,j<PDi,j+1,∀i,j=1,…,μ.


## 4.3. Proposition and Proof for Unequal Sequence Length

The following proposition holdsa priori from the pattern results of unequal character length of sequences. We state and prove the following general results by adhering to the same definitions stated earlier under the equal character length of sequences.Proposition 7.
For each three pointed arrows intersecting any four cell boxes, the left value of a 2nd cell box corresponds to the right value of a 3rd cell box.Proof.
LetPmi,j,Pmi+1,j,Pmi,j+1, and Pmi+1,j+1 be any four cell boxes, then we are to show that Pmi+1,j=Pmi,j+1. Refer to the proof of Proposition 5. Despite the unequal sequence length of μ1≠μ2, the supposed disparity in length has no bearing on the proof.Corollary 8.
For any two adjacent row cell boxes, the right value of a preceding cell box is less than the diagonal value of the next cell box.Proof.
Refer to the proof of Corollary6. Again, despite the unequal sequence length of μ1≠μ2, the supposed disparity in length has no bearing on the proof.


## 5. Conclusion

In this paper, the score matrix of the Needleman–Wunsch algorithm was exploited for possible patterns. Given any two arbitrary sequences of equal or unequal length, a general pattern was formulated as newa priori propositions and corollaries. These new formulated propositions and corollaries are justified with their corresponding proofs.



---

*Source: 3858057-2020-06-01.xml*