Editing Longest common subsequence (section)

=== Worked example ===
The longest subsequence common to ''R'' = (GAC), and ''C'' = (AGCAT) will be found.  Because the ''LCS'' function uses a "zeroth" element, it is convenient to define zero prefixes that are empty for these sequences:  ''R''<sub>0</sub> =  ε; and ''C''<sub>0</sub> =  ε.  All the prefixes are placed in a table with ''C'' in the first row (making it a <u>c</u>olumn header) and ''R'' in the first column (making it a <u>r</u>ow header).

{| class="wikitable" style="text-align:center"
|+ LCS Strings
|-
!   || ε || A || G || C || A || T
|-
! ε
| ε || ε || ε || ε || ε || ε
|-
! G
| ε
| 
| 
| 
| 
| 
|-
! A
| ε
| 
| 
| 
| 
| 
|-
! C
| ε
| 
| 
| 
| 
| 
|-
|}

This table is used to store the LCS sequence for each step of the calculation.  The second column and second row have been filled in with ε, because when an empty sequence is compared with a non-empty sequence, the longest common subsequence is always an empty sequence.

''LCS''(''R''<sub>1</sub>, ''C''<sub>1</sub>) is determined by comparing the first elements in each sequence.  G and A are not the same, so this LCS gets (using the "second property") the longest of the two sequences, ''LCS''(''R''<sub>1</sub>, ''C''<sub>0</sub>) and  ''LCS''(''R''<sub>0</sub>, ''C''<sub>1</sub>).  According to the table, both of these are empty, so ''LCS''(''R''<sub>1</sub>, ''C''<sub>1</sub>) is also empty, as shown in the table below.  The arrows indicate that the sequence comes from both the cell above, ''LCS''(''R''<sub>0</sub>, ''C''<sub>1</sub>) and the cell on the left, ''LCS''(''R''<sub>1</sub>, ''C''<sub>0</sub>).

''LCS''(''R''<sub>1</sub>, ''C''<sub>2</sub>) is determined by comparing G and G.  They match, so G is appended to the upper left sequence, ''LCS''(''R''<sub>0</sub>, ''C''<sub>1</sub>), which is (ε), giving (εG), which is (G).

For ''LCS''(''R''<sub>1</sub>, ''C''<sub>3</sub>), G and C do not match.  The sequence above is empty; the one to the left contains one element, G.  Selecting the longest of these, ''LCS''(''R''<sub>1</sub>, ''C''<sub>3</sub>) is (G).  The arrow points to the left, since that is the longest of the two sequences.

''LCS''(''R''<sub>1</sub>, ''C''<sub>4</sub>), likewise, is (G).

''LCS''(''R''<sub>1</sub>, ''C''<sub>5</sub>), likewise, is (G).

{| class="wikitable" style="text-align:center"
|+ "G" Row Completed
|-
!   || ε || A || G || C || A || T
|-
! ε
| ε || ε || ε || ε || ε || ε
|-
! G
| ε
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>ε
| <math>\overset{\nwarrow}{\ }</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
|-
! A
| ε
| 
| 
| 
| 
| 
|-
! C
| ε
| 
| 
| 
| 
| 
|-
|}

For ''LCS''(''R''<sub>2</sub>, ''C''<sub>1</sub>), A is compared with A.  The two elements match, so A is appended to ε, giving (A).

For ''LCS''(''R''<sub>2</sub>, ''C''<sub>2</sub>), A and G do not match, so the longest of ''LCS''(''R''<sub>1</sub>, ''C''<sub>2</sub>), which is (G), and ''LCS''(''R''<sub>2</sub>, ''C''<sub>1</sub>), which is (A), is used.  In this case, they each contain one element, so this LCS is given two subsequences:  (A) and (G).

For ''LCS''(''R''<sub>2</sub>, ''C''<sub>3</sub>), A does not match C.  ''LCS''(''R''<sub>2</sub>, ''C''<sub>2</sub>) contains sequences (A) and (G); LCS(''R''<sub>1</sub>, ''C''<sub>3</sub>) is (G), which is already contained in ''LCS''(''R''<sub>2</sub>, ''C''<sub>2</sub>).  The result is that ''LCS''(''R''<sub>2</sub>, ''C''<sub>3</sub>) also contains the two subsequences, (A) and (G).

For ''LCS''(''R''<sub>2</sub>, ''C''<sub>4</sub>), A matches A, which is appended to the upper left cell, giving (GA).

For ''LCS''(''R''<sub>2</sub>, ''C''<sub>5</sub>), A does not match T.  Comparing the two sequences, (GA) and (G), the longest is (GA), so ''LCS''(''R''<sub>2</sub>, ''C''<sub>5</sub>) is (GA).

{| class="wikitable" style="text-align:center"
|+ "G" & "A" Rows Completed
|-
!   || ε || A || G || C || A || T
|-
! ε
| ε || ε || ε || ε || ε || ε
|-
! G
| ε
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>ε
| <math>\overset{\nwarrow}{\ }</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
|-
! A
| ε
| <math>\overset{\nwarrow}{\ }</math>(A)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(A) & (G)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(A) & (G)
| <math>\overset{\nwarrow}{\ }</math>(GA)
| <math>\overset{\ }{\leftarrow}</math>(GA)
|-
! C
| ε
| 
| 
| 
| 
| 
|-
|}

For ''LCS''(''R''<sub>3</sub>, ''C''<sub>1</sub>), C and A do not match, so ''LCS''(''R''<sub>3</sub>, ''C''<sub>1</sub>) gets the longest of the two sequences, (A).

For ''LCS''(''R''<sub>3</sub>, ''C''<sub>2</sub>), C and G do not match.  Both ''LCS''(''R''<sub>3</sub>, ''C''<sub>1</sub>) and ''LCS''(''R''<sub>2</sub>, ''C''<sub>2</sub>) have one element.  The result is that ''LCS''(''R''<sub>3</sub>, ''C''<sub>2</sub>) contains the two subsequences, (A) and (G).

For ''LCS''(''R''<sub>3</sub>, ''C''<sub>3</sub>), C and C match, so C is appended to ''LCS''(''R''<sub>2</sub>, ''C''<sub>2</sub>), which contains the two subsequences, (A) and (G), giving (AC) and (GC).

For ''LCS''(''R''<sub>3</sub>, ''C''<sub>4</sub>), C and A do not match.  Combining ''LCS''(''R''<sub>3</sub>, ''C''<sub>3</sub>), which contains (AC) and (GC), and ''LCS''(''R''<sub>2</sub>, ''C''<sub>4</sub>), which contains (GA), gives a total of three sequences:  (AC), (GC), and (GA).

Finally, for ''LCS''(''R''<sub>3</sub>, ''C''<sub>5</sub>), C and T do not match.  The result is that ''LCS''(''R''<sub>3</sub>, ''C''<sub>5</sub>) also contains the three sequences, (AC), (GC), and (GA).

{| class="wikitable" style="text-align:center"
|+ Completed LCS Table
|-
!   || ε || A || G || C || A || T
|-
! ε
| ε || ε || ε || ε || ε || ε
|-
! G
| ε
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>ε
| <math>\overset{\nwarrow}{\ }</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
| <math>\overset{\ }{\leftarrow}</math>(G)
|-
! A
| ε
| <math>\overset{\nwarrow}{\ }</math>(A)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(A) & (G)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(A) & (G)
| <math>\overset{\nwarrow}{\ }</math>(GA)
| <math>\overset{\ }{\leftarrow}</math>(GA)
|-
! C
| ε
| <math>\overset{\ \uparrow}{\ }</math>(A)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(A) & (G)
| <math>\overset{\nwarrow}{\ }</math>(AC) & (GC)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(AC) & (GC) & (GA)
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>(AC) & (GC) & (GA)
|-
|}

The final result is that the last cell contains all the longest subsequences common to (AGCAT) and (GAC); these are (AC), (GC), and (GA).  The table also shows the longest common subsequences for every possible pair of prefixes.  For example, for (AGC) and (GA), the longest common subsequence are (A) and (G).