Shen S., Tuszynski J.A. Theory and Mathematical Methods for Bioformatics
Подождите немного. Документ загружается.
7.1 Construction of Alignment Space and Its Basic Theorems 221
7.1.2 The Alignment Space Under General Metric
Now we discuss how to measure the problem of generalization errors. There
are many types of metric for measuring generalization errors; e.g., the Lev-
enshtein distance, evolutionary distance, etc. The sequence alignment theory
is very well-established, and its application in bioinformatics is very broad.
Therefore, in this chapter we discuss in detail alignment distance and the cor-
responding alignment space. We also discuss the properties and applications
of the alignment space under general conditions.
General Metric Space
Let V be a finite or infinite set. Let V
+
= V ∪{−}be an expansion of V ,
which includes V and a virtual symbol “−”.
Definition 34. Let V
+
be the expansion of V and let d
+
(a, b) and d(a, b) de-
note the distance functions defined on V
+
and V , respectively. If their distance
functions are consistent, i.e., d(a, b)=d
+
(a, b) holds for all a, b ∈ V ,thenV is
called the topological subspace of V
+
, alternatively, V
+
is called the topological
expansion of V .
The main types of metric expansion space are as follows:
1. The finite set (discrete). In this case, V = V
q
= {0, 1, ···,q−1} is a finite
set, V
+
= V
q+1
= {0, 1, ···,q−1,q}.Asq changes, the finite set has a dif-
ferent meaning. Typically, for q =4,V
q
= {a, c, g, t} or V
q
= {a, c, g, u}
form the familiar nucleotide table; and for q = 20, V
q
is the familiar amino
acid table.
On a finite set V , the distance function d(a, b) is represented by a distance
matrix D =(d(a, b))
a,b∈V
, e.g., the Hamming matrix of (1.6), or the WT-
matrix of (1.7), etc. In this case, {V,D} is a metric space.
2. The bounded infinite set. For example, V =[0,q], q>0 is a bounded
interval, and a continuous set. There are many ways to express the distance
between pairs of elements. For example, the mean square error (MSE)
distance is: d(a, b)=(b − a)
2
, absolute error distance is: d(a, b)=|b − a|,
etc. Endowed with any one distance, {V,D} is a metric space. Using any
one of the above mentioned distance functions, the expansion distance
function defined on the expansion space V
+
can be extended as follows:
d
+
(a, b)=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
d(a, b) , if both a, b =“−”,
0 , if both a, b =“−”,
q, if only one of a, b is “−”, while d(a, b)isthe
absolute error distance,
q
2
, if only one of a, b is “−”, while d(a, b)isthe
mean square error distance,
(7.1)
then {V
+
,D
+
} is a metric space.
222 7 Alignment Space
3. The unbounded infinite set. For example, V =(0, ∞) is an unbounded
interval. Then the mean square error (MSE) distance, absolute error dis-
tance, etc., can be employed as the distance d(a, b)onV . The extended
distance on the expansion space V
+
can be defined as follows:
d
+
(a, b)=
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
d(a, b) , if both a, b =“− ”,
0 , if both a, b =“−”,
δ + d(a, 0) , if a ∈ V and b =“−”,
δ + d(0,b) , if b ∈ V and a =“−”,
(7.2)
where δ>0 is a constant. Under this distance, we know that {V
+
,D
+
} is
a metric space.
The Problem of Sequence Alignment and the Definition
of Alignment Space
The definition of pairwise alignment in this section is the same as that in
Sect. 1.4.2. The slight difference is that here, V,V
+
are general metric spaces.
For any two sequences A =(a
1
,a
2
, ··· ,a
n
a
)andB =(b
1
,b
2
, ··· ,b
n
b
)whose
range of values is in V , the corresponding terms involved in pairwise alignment
are stated as follows.
Definition 35. 1. If A and A
are two sequences in V and V
+
, respectively,
A
is the expansion of A if A remains after all the “−”inA
are deleted.
2. If A, B are two sequences ranging into V , (A
,B
) is the alignment of
(A, B) if A
and B
are the expansions of A and B, respectively, and their
lengths are the same n
.
If (A
,B
) are the alignment of (A, B),andd
+
(a, b),a,b ∈ V
+
is the dis-
tance function on V
+
,thend
+
(A
,B
)=
n
i=1
d
+
(a
i
,b
i
) is defined as the
distance between A
and B
.
3. Given a distance function d
+
, (A
,B
) is the minimum penalty align-
ment of (A, B) if (A
,B
) are the alignment sequences of (A, B),and
d
+
(A
,B
) ≤ d
+
(A
,B
) holds for any other alignment (A
,B
).
d
A
(A, B)=d
+
(A
,B
) is called the alignment distance of (A, B).Itis
also referred to simply as the A-distance.
Based on Definition 35, we find the alignment distance uniquely for any
pair A, B with values ranging on V , and this is a perfectly computational
method for evaluating the distance in bioinformatics. For discrete or con-
tinuous bounded metric spaces, we may use the Smith–Waterman dynamic
programming-based algorithm directly to compute the distance. For con-
tinuous unbounded metric space, the computation principle of the Smith–
Waterman dynamic programming-based algorithm still may be used with
a minor revision if we adapt the distance function defined by (7.2). Thus
7.1 Construction of Alignment Space and Its Basic Theorems 223
the corresponding software used in bioinformatics may still be used, albeit
with revisions.
The elements in alignment space are the sequences with values ranging in
V with different lengths. Let V
n
be the set of all sequences with length n and
whose values range in V , so that the alignment space V
∗
may be represented
by V
∗
=
-
∞
n=1
V
n
. Typically, following from Definition 35, we know that for
any A, B ∈ V
∗
q
, the A-distance is determined, and (V
∗
q
,d
A
) is an alignment
spaceoranA-spaceforshort.
The Levenshtein Distance of Generalization Errors
We have mentioned the Levenshtein distance and evolutionary distance in the
context of the alignment distance. In most cases, they are not equivalent. To
understand how to process the generalization errors, we show the correspond-
ing definitions and discuss their relationships. There are many ways to define
the Levenshtein distance. Let A, B be two sequences with values ranging in
V .
Definition 36. 1. (s, i, j) is an operation on A, which means that we change
s many symbols in A,inserti many components, and delete j many com-
ponents.
2. B is an output of A under the operation (s, i, j) if A turns into B via the
operation (s, i, j).Then(s, i, j) is called an operation from A to B.
3. (s
0
,i
0
,d
0
) is a minimum operation from A to B if (s
0
,i
0
,j
0
) is an opera-
tion from A to B,ands
0
+ i
0
+ j
0
≤ s +i + j holds for any other operation
(s, i, j) from A to B.Letd
L
1
(A, B)=s
0
+ i
0
+ j
0
be the L
1
-distance
of A, B, which is also called the evolutionary distance (or E-distance for
short).
The L
1
-distance can be also extended to the case where (s, i, j) has a different
weight. If V is a general metric space with distance function d(a, b), then the
L
1
-distance d
L
1
(A, B) involves both the errors caused by s, i, j and the symbol
of s, i, j.
The definition of L
2
-distance for a sequence pair (A, B)isasfollows:
Let W =(w
1
,w
2
, ··· ,w
n
w
) be a sequence; if there is a subsequence 1 ≤
i
1
<i
2
< ···<i
n
w
≤ n
a
such that a
i
j
= w
j
,j=1, 2, ··· ,n
w
holds, then W
is a subsequence of A.Thenlet
ρ(A, B)=max{|W |: W is the common subsequence of A, B} , (7.3)
where |W | is the length of sequence W .IfW
0
is the common subsequence
of A, B and |W
0
| = ρ(A, B), then W
0
is the largest common subsequence of
A, B.TheL
2
-distance is defined as follows:
d
L
2
(A, B)=|A|+ |B|−2 · ρ(A, B) . (7.4)
224 7 Alignment Space
The evolutionary distance is equivalent to the alignment distance, however,
we discuss them in different ways. For the L-distance and the A-distance, we
can describe their simple properties as follows:
If the penalty matrix d
+
is given, then for every pair of sequences A, B
with values ranging on V ,theirL
1
-distance, L
2
-distance, and A-distance are
uniquely determined. However, both the largest common subsequence W
0
of
(A, B) and the minimum penalty alignment sequences (A
,B
)of(A, B)are
not unique, and the minimum operation from A to B is not unique either.
The L
1
-distance is equivalent to the A-distance. Nevertheless, the L
2
-
distance may not be equivalent to the A-distance. We illustrate this with
the following example.
Example 21. If
A = 00000111 ,
B = 11111000 ,
and if the penalty matrix is the Hamming matrix, we have
d
A
(A, B)=8,ρ(A, B)=3,d
L
(A, B)=16− 2 × 3=10=8.
The Generalization of the Basic Theorem About the A-Distance
In Theorem 23, we proved that {V
∗
,D
A
} is a metric space if {V
+
,D
+
} is
a general metric space. The conclusion can be extended to the more general
topological metric space.
Theorem 29. If {V
+
,D
+
} is a general metric space, then {V
∗
,D
A
} is a met-
ricspace,wherethedefinitionsofsetV
∗
and the A-distance d
A
(A, B) are the
same as Definition 35. d
A
(A, B) is the distance function defined on V
∗
,which
means d
A
(A, B) satisfies the three conditions of a distance function: nonneg-
ativity, symmetry, and the triangle inequality.
The proof is the same as that of Theorem 23. We can easily extend the proof
of Theorem 23 to the general topological metric space {V
+
,D
+
},sowedonot
need to repeat it here.
7.2 The Analysis of Data Structures in Alignment Spaces
For any pair of sequences A, B ∈ V
∗
q
, we may discuss structures beyond the
A-distance. We will describe these other structures gradually.
7.2.1 Maximum Score Alignment and Minimum Penalty
Alignment
The definitions of the maximum score alignment and the minimum penalty
alignment have been mentioned before this section. We have explained that
the maximum score alignment and the minimum penalty alignment are not
the same in the general case. We now explain this in more detail.
7.2 The Analysis of Data Structures in Alignment Spaces 225
The Uniqueness Problem of Optimal Alignment
In Example 2 we have shown that the minimum penalty alignment is not gen-
erally unique. The same example can also be used to explain the nonunique-
ness of the maximum score alignment. Here, we explain why the minimum
penalty alignment as well as the lengths of the alignment sequences may not
be generally unique.
Example 22. If
A = 00000111 ,
B = 11111000 ,
and if the penalty matrix is the Hamming matrix, then we have d
A
(A, B)=8.
If we construct the sequences
A
1
= 200000111 ,
B
1
= 111110002 ,
A
2
= 2200000111 ,
B
2
= 1111100022 ,
A
3
= 22200000111 ,
B
3
= 11111000222 ,
then
d
H
(A, B)=d
H
(A
1
,B
1
)=d
H
(A
2
,B
2
)=d
H
(A
3
,B
3
)=8.
All of these are minimum penalty alignment sequences of (A, B), and their
corresponding lengths are found as follows:
|A| = |B| =8, |A
1
| = |B
1
| =9, |A
2
| = |B
2
| =10, |A
3
| = |B
2
| =11.
Thus, the lengths of minimum penalty alignment sequences may not be
unique.
For a fixed pair (A, B), let n
0
(A, B) be the smallest length among the optimal
alignment of (A, B), and we denote by n
1
(A, B) the largest length of the
optimal alignment sequences of (A, B).
The Relationship Between the Maximum Score Alignment
and the Minimum Penalty Alignment
Based on Definitions 3, we introduce the definition of the maximum score
alignment sequence if g
H
(a, b)=1− d
H
(a, b), a, b ∈ V
5
. Following from Ex-
ample 22, we find that the maximum score alignment and minimum penalty
alignment are not the same. For example, here, (A
1
,B
1
)and(A
2
,B
2
)arethe
minimum penalty alignment sequences of (A, B), which do not represent its
maximum score alignment sequences. (A
3
,B
3
) are both the minimum penalty
and maximum score alignment sequences of (A, B).
Lemma 2. The propositions below hold under the Hamming penalty and scor-
ing matrix condition.
226 7 Alignment Space
1. The minimum penalty alignment sequences (A
,B
) of sequences (A, B)
are the maximum score alignment sequences of (A, B) if and only if the
length n
of (A
,B
) is the largest length of the minimum alignment se-
quences of (A, B).
2. The maximum score alignment sequences (A
∗
,B
∗
) of sequences (A, B)
are the minimum penalty alignment sequences of (A, B) if and only if the
length n
∗
of (A
∗
,B
∗
) is the smallest length of maximum score alignment
sequences of (A, B).
Proof. Under the Hamming penalty and scoring matrix condition, for any
alignment sequences (A
,B
)of(A, B) such that the equation n
= d
H
(A
,B
)
+ g
H
(A
,B
)holds;if(A
,B
) are the minimum penalty alignment sequences,
then only if n
is the maximal value do we have that (A
,B
)arethemax-
imum score alignment sequences of (A, B). Proposition 1 of the lemma is
correct.
Proposition 2 can be proved similarly.
Lemma 2 gives a necessary condition under which the minimum penalty align-
ment sequences are the maximum score alignment sequences. The following
example expresses this: the maximum score alignment sequences are not al-
ways the minimum penalty alignment sequences.
Example 23. If
A = 00001011 ,
B = 10111000 ,
then A
= A, B
= B are the minimum penalty alignment sequences,
d
A
(A, B)=d
H
(A
,B
) = 5, while the maximum score alignment sequences
are
A
∗
= 000010211222 ,
B
∗
= 222210111000 ,
maximum score g(A
∗
,B
∗
)=4(g(A
,B
) = 3). However, d
H
(A
∗
,B
∗
)=8,so
(A
∗
,B
∗
) are not the minimum penalty alignment sequences of (A, B).
7.2.2 The Structure Mode of the Envelope of Pairwise Sequences
The definitions of the envelope and core of multiple sequences, minimal
(minimum) envelope and maximal (maximum) core, are given in Sect. 3.1.
They are closely related to the data structure of alignment space. Let
A =(a
1
,a
2
, ··· ,a
n
a
), B =(b
1
,b
2
, ··· ,b
n
b
) be two sequences with values
ranging in V
q
;letC =(c
1
,c
2
, ··· ,c
n
c
), D =(d
1
,d
2
, ··· ,d
n
d
)betheenve-
lope and core of A, B. We now discuss the relationship between their struc-
tures.
7.2 The Analysis of Data Structures in Alignment Spaces 227
The Structure Mode of the Envelope
If sequence C is the envelope of sequences A, B, then there must be two subsets
Δ
a
and Δ
b
in N
c
such that c
Δ
a
= A and c
Δ
b
= B hold. Δ
a
,Δ
b
are the sets
of envelope sites. We discuss them as follows:
1. Let
Δ
0
= Δ
a
∩ Δ
b
,Δ
1
= Δ
a
− Δ
0
,Δ
2
= Δ
b
− Δ
0
,
Δ
3
= N
c
− (Δ
a
∪ Δ
b
)=N
c
− (Δ
0
∪ Δ
1
∪Δ
2
) .
Then Δ
0
, Δ
1
, Δ
2
, Δ
3
are four disjoint sets and their union is N
c
.
2. If C is the minimal envelope of A and B,thenΔ
3
must be an empty set.
We now discuss the structure under the minimal envelope condition.
3. For each i ∈ N
c
, we define the structure functions τ
i
=0, 1, 2, if i ∈
Δ
0
,Δ
1
,Δ
2
of sequence C. Obviously, the envelope C and the structure
function ¯τ =(τ
1
,τ
2
, ··· ,τ
n
c
) determine each other uniquely if sequences
A and B are determined.
The structure function ¯τ is called the structure mode of the envelope C.
The Permutation of the Envelope
Let C be the envelope of sequences A and B. For any positions i<j∈ N
c
,
permutated by c
i
and c
j
, sequence C becomes:
C
=(c
1
,c
2
, ··· ,c
i−1
,c
j
,c
i+1
,c
i+2
, ··· ,c
j−1
,c
i
,c
j+1
, ··· ,c
n
c
) .
Let C
= σ
i,j
(C). If C
is also the envelope of A and B, then the permuta-
tion σ
i,j
is called an isotone permutation. Then C and C
are the equivalent
envelopes of A and B.
Lemma 3. In the structure mode ¯τ of the envelope C,ifτ
i
= τ
i+1
∈{1, 2},
the permutation σ
i,i+1
must be the isotone permutation of C.
The proof is obvious.
The Standard Structure Mode of the Envelope C
Definition 37. If the structure mode ¯τ of the envelope C satisfies the fol-
lowing conditions, we may say that the envelope C has a standard structure
mode:
1. Vector ¯τ can be decomposed into several alternating subvectors, let
¯τ =((¯e
0,1
, ¯e
0,2
, ¯e
0,0
), (¯e
1,1
, ¯e
1,2
, ¯e
1,0
), ··· , (¯e
k
c
,1
, ¯e
k
c
,2
, ¯e
k
c
,0
)) , (7.5)
where ¯e
k,τ
=(
k,τ
( )* +
τ,τ,··· ,τ) is a vector with a value τ ∈{0, 1, 2} and length
k,τ
.
228 7 Alignment Space
2. In formula (7.5), the inequalities
0,1
+
0,2
+
0,0
> 0 and
k
c
,1
+
k
c
,2
+
k
c
,0
> 0
hold. For any k =0, 1, ··· ,k
c
,
k,3
> 0 ,
0,1
,
k,2
,
k,0
≥ 0 (7.6)
holds. If
k,τ
=0,thenvector¯e
k,τ
does not exist.
Example 24. The following mode is a standard structure mode of an envelope.
¯τ =(11, 222, 0, 1111, 22, 00000, 2222, 0000000, 11111, 000, 111, 22, 0000, 111) ,
where k
c
= 5, and the value of
k,τ
is assigned as follows:
0,1
=2,
0,2
=3,
0,0
=1,
1,1
=4,
1,2
=2,
1,0
=5,
2,1
=0,
2,2
=4,
2,0
=7,
3,1
=5,
3,2
=0,
3,0
=3,
4,1
=3,
4,2
=2,
4,0
=4,
5,1
=3,
5,2
=0,
5,0
=0.
Using Lemma 3, we may conclude that all envelopes of sequences A and B
must be equivalent to an envelope with a standard structure mode.
In the standard structure mode of the envelope, the sequence C may always
be denoted by:
C =(c
δ
0
,c
δ
1
, ··· ,c
δ
k
c
) , (7.7)
where δ
k
=(δ
k,1
,δ
k,2
,δ
k,3
), and each δ
k,τ
is an integer vector of length
k,τ
.
These were arranged in order. Then, c
δ
k
=(c
δ
k,1
,c
δ
k,2
,c
δ
k,3
) is called a struc-
ture segment of envelope C.
In the structure segment c
δ
k
, c
δ
k,3
is called the last half-part of the struc-
ture segment, and (c
δ
k,1
,c
δ
k,2
) is called the first half-part of the structure
segment.
The length of the last half-part of the structure segment c
δ
k
in envelope C
is
k,1
+
k,2
,where
k,1
components are selected from A,and
k,2
components
are selected from B. Thus, the number of different selection methods is
(
k,1
+
k,2
)!
k,1
!
k,2
!
.
The number of the envelopes which are equivalent to envelope C is
M(C)=
k
c
k=1
(
k,1
+
k,2
)!
k,1
!
k,2
!
. (7.8)
7.2 The Analysis of Data Structures in Alignment Spaces 229
Properties of the Minimal (Minimum) Envelope
Let C be an envelope of multiple sequences A and let ¯α =(α
1
,α
2
, ··· ,α
m
)
be the set of generation positions of envelope C,herec
α
s
= A
s
, where s =
1, 2, ··· ,m holds. If Δ is a subset of N
c
,letα
s
(Δ
)=α
s
∩ Δ
,thenc
α
s
(Δ
)
must be a subsequence of A
s
.
Lemma 4. If C is a minimal (minimum) envelope of A and B,thenc
Δ
must
be a minimal (minimum) envelope of c
α
s
(Δ
)
, s =1, 2, ···,m.
Proof. We prove this proposition by reduction to absurdity. If c
Δ
is not a min-
imal envelope of c
α
s
(Δ
)
, where s =1, 2, ··· ,m, then there exists a j ∈ Δ
such that c
Δ
is an envelope of ¯c(Δ
), here Δ
= Δ
−{j}. There now is
a subset β
s
⊂ Δ
such that c
β
s
= c
α
s
(Δ
)
,wheres =1, 2, ··· ,m.
Since C is an envelope of (A, B), then c
(Δ
)
c
must be an envelope of
¯c((Δ
)
c
)=
c
α
1
((Δ
)
c
)
,c
α
2
((Δ
)
c
)
, ··· ,c
α
m
((Δ
)
c
)
,
where α
s
((Δ
)
c
)=α
s
∩(Δ
)
c
, while (Δ
)
c
= N
c
−Δ
. On the other hand, we
obtain
A
s
= c
α
s
=
c
α
s
(Δ
)
,c
α
s
((Δ
)
c
)
=
c
β
s
,c
α
s
((Δ
)
c
)
. (7.9)
If we let N
c
= {1, 2, ···,j−1,j+1, ··· ,n
c
}, then β
s
∪(Δ
)
c
⊂ N
c
. Following
from (7.9), we find that c
N
c
=(c
1
,c
2
, ··· ,c
j−1
,c
j+1
, ··· ,c
n
c
)isanenvelope
of (A, B). This contradicts the definition that C is a minimal envelope of
(A, B). Therefore, the lemma is proved.
Theorem 30. If C is a minimum envelope of A, B with a standard structure
mode, and c
δ
k
is a structure segment of C, then in the first half-part of the
structure segment, any component in vector c
δ
k,1
is different from that in c
δ
k,2
.
Proof. We prove this proposition by reduction to absurdity. For a standard
structure mode in (7.7), let
1=j
0,1
≤ j
0,2
≤ j
0,0
≤ j
1,1
≤ j
1,2
≤ j
1,0
≤···
≤ j
k
c
,1
≤ j
k
c
,2
≤ j
k
c
,0
≤ j
k
c
+1,1
= n
c
, (7.10)
where
k,τ
= j
k,τ+1
− j
k,τ
,τ =1, 2, 3. We denote j
k,4
= j
k+1,1
.Then
k,τ
satisfies formula (7.6).
If there is a structure segment c
δ
k
such that the conclusion of the theorem
is wrong, then there must be a 0 ≤ k ≤ k
c
such that a component in c
δ
k,1
is
the same as that in c
δ
k,2
.Letj
1
,j
2
satisfy c
j
1
= c
j
2
and let j
k,1
<j
1
≤ j
k,2
<
j
2
≤ j
k+1,0
hold. We construct a new sequence C
as follows:
C
=(c
1
,c
2
, ··· ,c
j
1
−1
,c
j
k,2
+1
,c
j
k,2
+2
, ··· ,c
j
2
−1
,c
j
, ··· ,c
n
c
) , (7.11)
230 7 Alignment Space
where j = j
1
−1 −j
k,1
+ j
2
−1 −j
k,2
. C
is also the envelope of sequences A
and B with a standard structure mode as follows:
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
δ
k
,τ
= δ
k,τ
,k
=0, 1, ··· ,k−1 ,τ=1, 2, 3 ,
δ
k,1
=[j
k,1
+1,j
1
− 1] ,
δ
k,2
=[j
k,2
+1,j
2
− 1] ,
δ
k,0
= {j} = {j
1
− 1 −j
k,1
+ j
2
− 1 −j
k,2
},
δ
k+1,1
=[j +1,j+ j
k,2
− j
1
] ,
δ
k+1,2
=[j + j
k,2
− j
1
+ j
k,0
− j
2
] ,
δ
k+1,0
= δ
k,0
,
δ
k+k
,τ
= δ
k+k
,τ
,k
=2, 3, ··· ,k
c
− k +1,τ=1, 2, 3 .
(7.12)
However, the length of C
is n
c
− 1. This contradicts the definition that C is
the minimum envelope of A, B. The theorem is therefore proved.
7.2.3 Uniqueness of the Maximum Core and Minimum Envelope
of Pairwise Sequences
The following example tells us that the maximum core and minimum envelope
of pairwise sequences are not generally unique.
Example 25. 1. Let
A = (11111011111)
B = (11110111111) ,
then their maximum cores are as follows:
D = (1111011111) ,D
= (1111111111) .
Then |D| = |D
| = 10, and they are both the largest subsequence of A
and B. In other words, they are both the maximum core of A and B.It
follows that the maximum core of pairwise sequences is not always unique.
In this example the minimum envelope C = (111110111111) of A and B
is unique.
2. Let
A = (11111011110)
B = (111101111111) ,
then the maximum core: D = (1111011110) is unique, but the minimum
envelopes are not unique, which is stated as follows:
C
1
= (11111011110111) ,C
2
= (11111011111011) ,
C
3
= (11111011111101) ,C
4
= (11111011111110) .
These two examples show that maximum core and minimum envelope of pair-
wise sequences are not always unique. They are unable to determine each
other.