Editing Longest common subsequence (section)

=== Traceback approach ===
Calculating the LCS of a row of the LCS table requires only the solutions to the current row and the previous row.  Still, for long sequences, these sequences can get numerous and long, requiring a lot of storage space.  Storage space can be saved by saving not the actual subsequences, but the length of the subsequence and the direction of the arrows, as in the table below.

{| class="wikitable" style="text-align:center"
|+ Storing length, rather than sequences
|-
!   || ε || A || G || C || A || T
|-
! ε
| 0 || 0 || 0 || 0 || 0 || 0
|-
! G
| 0
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>0
| <math>\overset{\nwarrow}{\ }</math>1
| <math>\overset{\ }{\leftarrow}</math>1
| <math>\overset{\ }{\leftarrow}</math>1
| <math>\overset{\ }{\leftarrow}</math>1
|-
! A
| 0
| <math>\overset{\nwarrow}{\ }</math>1
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>1
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>1
| <math>\overset{\nwarrow}{\ }</math>2
| <math>\overset{\ }{\leftarrow}</math>2
|-
! C
| 0
| <math>\overset{\ \uparrow}{\ }</math>1
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>1
| <math>\overset{\nwarrow}{\ }</math>2
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>2
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>2
|-
|}

The actual subsequences are deduced in a "traceback" procedure that follows the arrows backwards, starting from the last cell in the table.  When the length decreases, the sequences must have had a common element.  Several paths are possible when two arrows are shown in a cell.  Below is the table for such an analysis, with numbers colored in cells where the length is about to decrease.  The bold numbers trace out the sequence, (GA).<ref>{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[Clifford Stein]] | title = Introduction to Algorithms | publisher = MIT Press and McGraw-Hill | year = 2001 | isbn = 0-262-53196-8 | edition = 2nd | chapter = 15.4 | pages = 350–355 | title-link = Introduction to Algorithms }}</ref>

{| class="wikitable" style="text-align:center"
|+ Traceback example
|-
!   || ε || A || G || C || A || T
|-
! ε
| 0 || style="background:silver" | '''0''' || 0 || 0 || 0 || 0
|-
! G
| style="background:silver" | 0
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>0
| style="background:silver;color:#FF6600" | <math>\overset{\nwarrow}{\ }</math>'''1'''
| style="background:silver" | <math>\overset{\ }{\leftarrow}</math>'''1'''
| <math>\overset{\ }{\leftarrow}</math>1
| <math>\overset{\ }{\leftarrow}</math>1
|-
! A
| 0
| style="background:silver;color:#FF6600" | <math>\overset{\nwarrow}{\ }</math>1
| style="background:silver" | <math>\overset{\ \ \uparrow}{\leftarrow}</math>1
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>1
| style="background:silver;color:#FF6600" | <math>\overset{\nwarrow}{\ }</math>'''2'''
| style="background:silver" | <math>\overset{\ }{\leftarrow}</math>'''2'''
|-
! C
| 0
| <math>\overset{\ \uparrow}{\ }</math>1
| <math>\overset{\ \ \uparrow}{\leftarrow}</math>1
| style="background:silver;color:#FF6600" | <math>\overset{\nwarrow}{\ }</math>2
| style="background:silver" | <math>\overset{\ \ \uparrow}{\leftarrow}</math>2
| style="background:silver" | <math>\overset{\ \ \uparrow}{\leftarrow}</math>'''2'''
|-
|}