Scribd
Upload
30 views1 page

Dynamic Programming 7

The document discusses sequence alignment in genetics which involves transforming one sequence into another using edit operations like replace, insert or remove with an associated cost. The goal is to find the lowest total cost sequence of edits. Dynamic programming using a matrix is used to calculate the optimal alignment cost between subsequences of the two sequences.

Uploaded by

Arvin Hipolito
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
30 views1 page

Dynamic Programming 7

The document discusses sequence alignment in genetics which involves transforming one sequence into another using edit operations like replace, insert or remove with an associated cost. The goal is to find the lowest total cost sequence of edits. Dynamic programming using a matrix is used to calculate the optimal alignment cost between subsequences of the two sequences.

Uploaded by

Arvin Hipolito
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Sequence alignment[edit]

In genetics, sequence alignment is an important application where dynamic programming is


essential.[11] Typically, the problem consists of transforming one sequence into another using edit
operations that replace, insert, or remove an element. Each operation has an associated cost, and
the goal is to find the sequence of edits with the lowest total cost.
The problem can be stated naturally as a recursion, a sequence A is optimally edited into a
sequence B by either:

1. inserting the first character of B, and performing an optimal alignment of A and the tail of B
2. deleting the first character of A, and performing the optimal alignment of the tail of A and B
3. replacing the first character of A with the first character of B, and performing optimal
alignments of the tails of A and B.
The partial alignments can be tabulated in a matrix, where cell (i,j) contains the cost of the optimal
alignment of A[1..i] to B[1..j]. The cost in cell (i,j) can be calculated by adding the cost of the relevant
operations to the cost of its neighboring cells, and selecting the optimum.
Different variants exist, see Smith–Waterman algorithm and Needleman–Wunsch algorithm.

You might also like