Showing 18 out of 8
lcs.pdfLongest Common Subsequence A subsequence o...
lcs.pdfLongest Common Subsequence A subsequence of
lcs.pdfLongest Common Subsequence ...
lcs.pdfLongest Common Subsequence A subsequence of
Page 1
Longest Common Subsequence
A
subsequence
of a string
S
, is a set of characters that appear in left
toright order, but not necessarily consecutively.
Example
ACTTGCG
•
ACT
,
ATTC
,
T
,
ACTTGC
are all subsequences.
•
TTA
is not a subequence
A
common subequence
of two strings is a subsequence that appears in
both strings.
A
longest common subequence
is a common subsequence
of maximal length.
Example
S
1
=
AAACCGTGAGTTATTCGTTCTAGAA
S
2
=
CACCCCTAAGGTACCTTTGGTTC
Page 2
Example
S
1
=
AA
ACC
G
T
G
AG
T
TA
TT
C
G
TT
C
T
A
G
AA
S
2
=
C
A
CC
CCTA
AG
GT AC
C
TTTG
GTTC
LCS is
ACCTAGTACTTTG
Has applications in many areas including biology.
Page 3
Algorithm 1
Enumerate all subsequences of
S
1
, and check if they are subsequences of
S
2
.
Questions:
•
How do we implement this?
•
How long does it take?
Page 4
Optimal Substructure
Theorem
Let
X
=
<x
1
,x
2
,...,x
m
>
and
Y
=
<y
1
,y
2
,...,y
n
>
be sequences,
and let
Z
=
<z
1
,z
2
,...,z
k
>
be any LCS of
X
and
Y
.
1. If
x
m
=
y
n
, then
z
k
=
x
m
=
y
n
and
Z
k

1
is an LCS of
X
m

1
and
Y
n

1
.
2. If
x
m
=
y
n
, then
z
k
=
x
m
implies that
Z
is an LCS of
X
m

1
and
Y
.
3. If
x
m
=
y
n
, then
z
k
=
y
n
implies that
Z
is an LCS of
X
and
Y
n

1
.
Page 5
Proof
Let
X
=
<x
1
,x
2
,...,x
m
>
and
Y
=
<y
1
,y
2
,...,y
n
>
be sequences, and let
Z
=
<z
1
,z
2
,...,z
k
>
be any LCS of
X
and
Y
.
1. If
x
m
=
y
n
, then
z
k
=
x
m
=
y
n
and
Z
k

1
is an LCS of
X
m

1
and
Y
n

1
.
2. If
x
m
=
y
n
, then
z
k
=
x
m
implies that
Z
is an LCS of
X
m

1
and
Y
.
3. If
x
m
=
y
n
, then
z
k
=
y
n
implies that
Z
is an LCS of
X
and
Y
n

1
.
Proof
1. If
z
k
=
x
m
, then we could append
x
m
=
y
n
to
Z
to obtain a common
subsequence of
X
and
Y
of length
k
+1
, contradicting the supposition
that
Z
is a
longest
common subsequence of
X
and
Y
. Thus, we must have
z
k
=
x
m
=
y
n
. Now, the preﬁx
Z
k

1
is a length
(
k

1)
common subsequence
of
X
m

1
and
Y
n

1
. We wish to show that it is an LCS. Suppose for the
purpose of contradiction that there is a common subsequence
W
of
X
m

1
and
Y
n

1
with length greater than
k

1
.
Then, appending
x
m
=
y
n
to
W
produces a common subsequence of
X
and
Y
whose length is greater
than
k
, which is a contradiction.
2. If
z
k
=
x
m
, then
Z
is a common subsequence of
X
m

1
and
Y
. If there were
a common subsequence
W
of
X
m

1
and
Y
with length greater than
k
,
then
W
would also be a common subsequence of
X
m
and
Y
, contradicting
the assumption that
Z
is an LCS of
X
and
Y
.
Page 6
3. The proof is symmetric to the previous case.
Page 7
Recursion for length
c
[
i, j
]=
0
if
i
=0
or
j
=0
,
c
[
i

1
,j

1] + 1
if
i, j >
0
and
x
i
=
y
j
,
max(
c
[
i, j

1]
,c
[
i

1
,j
])
if
i, j >
0
and
x
i
=
y
j
.
(1)
Page 8
Code
LCS

Length
(
X, Y
)
1
m
←
length
[
X
]
2
n
←
length
[
Y
]
3
for
i
←
1
to
m
4
do
c
[
i,
0]
←
0
5
for
j
←
0
to
n
6
do
c
[0
,j
]
←
0
7
for
i
←
1
to
m
8
do for
j
←
1
to
n
9
do if
x
i
=
y
j
10
then
c
[
i, j
]
←
c
[
i

1
,j

1] + 1
11
b
[
i, j
]
←
“
”
12
else
if
c
[
i

1
,j
]
≥
c
[
i, j

1]
13
then
c
[
i, j
]
←
c
[
i

1
,j
]
14
b
[
i, j
]
←
“
↑
”
15
else
c
[
i, j
]
←
c
[
i, j

1]
16
b
[
i, j
]
←
“
←
”
17
return
c
and
b
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Rajasthan Technical Unive...
Rajasthan_Technical_University
School:
Analysis_of_Algorithms
Course:
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106