lcs.pdf-Longest Common Subsequence A sub...
lcs.pdf-Longest Common Subsequence A subsequence of
Showing 1-8 out of 8
lcs.pdf-Longest Common Subsequence A subsequence o...
lcs.pdf-Longest Common Subsequence A subsequence of
lcs.pdf-Longest Common Subsequence ...
lcs.pdf-Longest 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-
to-right 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 prefix
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:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
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