Longest Common Subsequence in Dynamic Programming
Dynamic Programming (3)
Longest Common Subsequence
(LCS)
What is a subsequence ?
Sequence: ABCBDABBBACD
What is a subsequence ?
Sequence: A
B
CB
D
A
BB
BA
C
D
BDBBC
is a subsequence
What is a subsequence ?
Sequence:
AB
CBDABB
B
AC
D
ABBD
is a subsequence
Definition of a subsequence
The Longest Common Subsequence Problem
The Longest Common Subsequence Problem
The Longest Common Subsequence Problem
A more interesting input
https://www.ncbi.nlm.nih.gov/nuccore/MN908947
X=
……….
A more interesting input
https://www.ncbi.nlm.nih.gov/nuccore/NC_004718.3
Y=
……….
Some notation
A recursive solution
A recursive solution
A recursive solution
•
A simple recursive procedure will solve the same problem multiple
times
•
Solve all subproblems by filling a table in increasing subproblem size
The table we need to fill
Y
X
Filling the table
Filling the table
Filling the table
Filling the table
Filling the table
Filling the table
Filling the table
P-code for the algorithm
O(nm) time and space
Recovering the longest sequence
We actually can get away
without the matrix b
Can use linear space if we
are just interested in the
length of the LCS
Learn about subsequences, the longest common subsequence problem, and how to find common subsequences of two given strings using dynamic programming. Explore examples and understand the concept with visuals for better comprehension.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Dynamic Programming (3) Longest Common Subsequence (LCS)
What is a subsequence ? Sequence: ABCBDABBBACD
What is a subsequence ? Sequence: ABCBDABBBACD BDBBC is a subsequence
What is a subsequence ? Sequence: ABCBDABBBACD ABBD is a subsequence
Definition of a subsequence ? = ?1?2 ??is a subsequence of ? = ?1?2 ??if there are indices 1 ?1 ?2 ?? ? such that ???= ??for all 1 ? ? How many subsequences does ?1?2 ??have ?
The Longest Common Subsequence Problem Given two strings ? = ?1?2 ??and ? = ?1?2 ?? Find a common subsequence Z of ? and ? of maximum length X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA
The Longest Common Subsequence Problem Given two strings ? = ?1?2 ??and ? = ?1?2 ?? Find a common subsequence Z of ? and ? of maximum length X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Z = GTCGTCGGAAGCCGGCCGAA
The Longest Common Subsequence Problem Given two strings ? = ?1?2 ??and ? = ?1?2 ?? Find a common subsequence Z of ? and ? of maximum length X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Z = GTCGTCGGAAGCCGGCCGAA
A more interesting input https://www.ncbi.nlm.nih.gov/nuccore/MN908947 X= .
A more interesting input https://www.ncbi.nlm.nih.gov/nuccore/NC_004718.3 Y= .
Some notation Recall ? = ?1?2 ?? and ? = ?1?2 ?? Let ??= ?1?2 ?? (in particular ? = ??) Let ??= ?1?2 ?? (in particular ? = ??)
A recursive solution Case 1: X and Y end with the same character. That is ??= ??: X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Lemma 1 If ? = ??= ?? then any LCS of ? and Y is of the form ?? where ? is an LCS of ?? 1 and ?? 1
A recursive solution Case 2: X and Y do not end with the same character. That is ?? ??: X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAB Lemma 2 If ?? ?? then any LCS of ? and Y is either an LCS of ?? 1 and ? or and LCS of ?? 1 and ?, the largest among them
A recursive solution Globals ?,? 0 ? = 0 ?? ? = 0 ?,? > 0 ??? ??= ?? ?,? > 0 ??? ?? ?? ??? ? 1,? 1 + 1 max{??? ? 1,? ,??? ?,? 1 } ??? ?,? = A simple recursive procedure will solve the same problem multiple times Solve all subproblems by filling a table in increasing subproblem size
The table we need to fill ? 0 1 2 3 4 5 6 ? ? Y B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 2 B 0 3 C 0 4 B 0 5 D 0 6 A 0 7 B 0 X
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 3 C 0 4 B 0 5 D 0 6 A 0 7 B 0
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 4 B 0 5 D 0 6 A 0 7 B 0
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 5 D 0 6 A 0 7 B 0
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 6 A 0 7 B 0
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 3 6 A 0 7 B 0
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 3 6 A 0 1 2 2 3 3 4 7 B 0
Filling the table ? 0 1 2 3 4 5 6 ? ? B D C A B A ? 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 3 6 A 0 1 2 2 3 3 4 7 B 0 1 2 2 3 4 4
P-code for the algorithm O(nm) time and space
Recovering the longest sequence We actually can get away without the matrix b Can use linear space if we are just interested in the length of the LCS
