# Compatibility and Conjugacy on Partial Arrays

Authors: S. Vijayachitra; K. Sasikala
Journal: Computational and Mathematical Methods in Medicine
 (2016)

---

## Abstract

Research in combinatorics on words goes back a century. Berstel and Boasson introduced the partial words in the context of gene comparison. Alignment of two genes can be viewed as a construction of two partial words that are said to be compatible. In this paper, we examine to which extent the fundamental properties of partial words such as compatbility and conjugacy remain true for partial arrays. This paper studies a relaxation of the compatibility relation calledk-compability. It also studies k-conjugacy of partial arrays.


---

## Body

## 1. Introduction

The genetic information in almost all organisms is carried by molecules of DNA. A DNA molecule is a quite long but finite string of nucleotides of 4 possible types:a (for adenine), c (for cytosine), g (for guanine), and t (for thymine). The stimulus for recent works on combinatorics is the study of biological sequences such as DNA and protein that play an important role in molecular biology [1–3]. Sequence comparison is one of the primitive operations in molecular biology. Alignment of two sequences is to place one sequence above the other [2, 4] in order to make clear correspondence between similar letters or substrings of the sequences. Partial words appear in comparing genes. Indeed, alignment of two strings can be viewed as a construction of two partial words that are compatible. The compatibility relation [5] considers two arrays with only few isolated insertions (or deletions). In some cases, it allows insertion of letters which relate to errors or mismatches. A problem appears when the same gene is sequenced by two different labs that want to differentiate the gene expression. Also, when the same long sequence is typed twice into the computer, errors appear in typing.Partial arrayA of size (
m
,
n
) over Σ, a finite alphabet, is partial function A
:
Z
+
2
→
Σ, where Z
+ is the set of all positive integers. In this paper, we extend the combinatorial properties of partial words to partial arrays. Also, this paper studies a relation called k-compatibility where a number of insertions and deletions are allowed as well as k-mismatches. The conjugacy result [6] which was proved for partial words is extended to partial arrays. k-Conjugacy of partial arrays is discussed.


## 2. Preliminaries on Partial Words

In this section, we give a brief overview of partial words [7].Definition 1.
Partial wordu of length n over A, a nonempty finite alphabet, is partial map u
:
{
1,2
,
…
,
n
}
→
A. If 1
≤
i
≤
n, then i belongs to the domain of u (denoted by D
o
m
a
i
n
(
u
)) in the case where u
(
i
) is defined, and i belongs to the set of holes of u (denoted by H
o
l
e
(
u
)), otherwise.
A word [8–10] is a partial word over A with an empty set of holes.Definition 2.
Letu be a partial word of length n over A. The companion of u (denoted by u
◊) is map u
◊
:
{
1,2
,
…
,
n
}
→
A
∪
{
◊
} defined by(1)u◊i=uiifi∈Domainu◊otherwise.
The symbol◊ is viewed as a “do not know” symbol. Word u
◊
=
b
a
◊
a
b
◊ is the companion of the partial word. The length of the partial word is 6. D
(
u
)
=
{
1,2
,
4,5
}. H
(
u
)
=
{
3,6
}.Letu and v be two partial words of length n. Partial word u is said to be contained in partial word v (denoted by u
⊂
v), if D
o
m
a
i
n
(
u
)
⊂
D
o
m
a
i
n
(
v
) and u
(
i
)
=
v
(
i
) for all i
∈
D
o
m
a
i
n
(
u
). Partial words u and v are called compatible (denoted by u
↑
v), if there exists partial word w such that u
⊂
w and v
⊂
w (in which case we define u
∨
v by u
⊂
u
∨
v and v
⊂
u
∨
v and D
o
m
a
i
n
(
u
∨
v
)
=
D
o
m
a
i
n
(
u
)
∪
D
o
m
a
i
n
(
v
)). As an example, u
◊
=
a
b
a
◊
◊
a and v
◊
=
a
b
a
b
◊
a.The following rules are useful for computing with partial words:(i)
Multiplication: If u
↑
v and x
↑
y, then u
x
↑
v
y.
(ii)
Simplification: If u
x
↑
v
y and u
=
v, then u
↑
v and x
↑
y.
(iii)
Weakening: If u
↑
v and w
⊂
u, then w
↑
v.Lemma 3.
Letu
,
v
,
x
,
y be partial words such that u
x
↑
v
y. (i)
If|
u
|
≥
|
v
|, then there exist partial words w
,
z such that u
=
w
z, v
↑
w, and y
↑
z
x.
(ii)
If|
u
|
≤
|
v
|, then there exist partial words w
,
z such that b
=
w
z, v
↑
w, and x
↑
z
y.Definition 4.
Two partial wordsu and v are called conjugate, if there exist partial words x and y such that u
⊂
x
y and v
⊂
y
x.Definition 5.
Two partial wordsu and v are called k-conjugate, if there exist nonnegative integers k
1, k
2 whose sum is k and partial words x and y such that u
⊂
k
1
x
y and v
⊂
k
2
y
x.


## 3. Preliminaries on Partial Arrays

This section is devoted to review the basic concepts on partial arrays [11].Definition 6.
Partial arrayA of size (
m
,
n
) over Σ, a nonempty set or an alphabet, is partial function A
:
Z
+
2
→
Σ, where Z
+ is the set of all positive integers. For 1
≤
i
≤
m, 1
≤
j
≤
n, and if A
(
i
,
j
) is defined, then we say that (
i
,
j
) belongs to the domain of A (denoted by (
i
,
j
)
∈
D
(
A
)
). Otherwise, we say that (
i
,
j
) belongs to the set of holes of A (denoted by (
i
,
j
)
∈
H
(
A
)).
An array [5] over Σ is a partial array over Σ with an empty set of holes.Definition 7.
IfA is a partial array of size (
m
,
n
) over Σ, then the companion of A (denoted by A
◊) is total function A
◊
:
Z
+
2
→
Σ
∪
{
◊
} defined by(2)A◊i,j=Ai,jifi,j∈DA◊otherwise,where ◊
∉
Σ.The bijectivity of mapA
→
A
◊ allows defining the catenation of two partial arrays in a trivial way.Example 8.
Partial arrayA
=
b
a
b
◊
a
b
b
◊
b is the companion of partial array A of size (3, 3), where D
A
=
1,1
,
1,2
,
1,3
,
2,2
,
2,3
,
3,1
,
3,3, H
A
=
2,1
,
3,2
.
Let(3)X=a11⋯a1n⋮⋮am1⋯amn,Y=b11⋯b1n′⋮⋮bm′1⋯bm′n′.By column catenation, we mean(4)X⦶Y=a11⋯a1nb11⋯b1n′⋮⋮⋮⋮am1⋯amnbm′1⋯bm′n′. By row catenation, we mean(5)X⊖Y=a11⋯a1n⋮⋮am1⋯amnb11⋯b1n′⋮⋮bm′1⋯bm′n′.IfA and B are two partial arrays of equal size, then A is contained in B denoted by A
⊂
B if D
(
A
)
⊆
D
(
B
) and(6)Ai,j=Bi,j∀i,j∈DA.Definition 9.
Partial arraysA and B are said to be compatible denoted by A
↑
B, if there exists partial array C such that A
⊂
C and B
⊂
C.


## 4. Compatibiltiy andk-Compatability of Partial Arrays

### 4.1. Compatibility

The rules mentioned for partial words are also true for partial arrays.LetA
,
B
,
X
,
Y be partial arrays.(i)
Multiplication: If A
↑
B and X
↑
Y, then A
X
↑
B
Y either by column catenation or by row catenation.
(ii)
Simplification: If A
X
↑
B
Y either by column catenation or by row catenation with A and B being of same size, then A
↑
B and X
↑
Y.
(iii)
Weakening: If A
↑
B and C
⊂
A, then C
↑
B.Lemma3’s version for partial arrays can be stated as follows.Lemma 10.
LetA
,
B
,
X
,
Y be partial arrays such that A
X
↑
B
Y, either by column catenation or by row catenation. (i)
If order ofA
≥ order of B, then there exist partial arrays C, Z such that A
=
C
Z, B
↑
C, and Y
↑
Z
X.
(ii)
If order ofA
≤ order of B, then there exist partial arrays C, Z such that B
=
C
Z, A
↑
C, and X
↑
Z
Y.


### 4.2.k-Compatibility

Definition 11.
IfA and B are two partial arrays of same size and k is nonnegative integer, then A is said to be k-contained in B denoted by A
⊂
k
B if D
(
A
)
⊂
D
(
B
) and there exists subset E of D
(
A
) of cardinality k called the error set such that (7)Ai,j=Bi,j∀i,j∈DA∖E,Ai,j≠Bi,j∀i,j∈E.Definition 12.
IfA and B are two partial arrays of same order and k is a nonnegative integer, then A and B are called k-compatible denoted by A
↑
k
B if there exist partial array Z and nonnegative integers k
1
,
k
2 such that(i)
A
⊂
k
1
Z with error set E
1;
(ii)
B
⊂
k
2
Z with error set E
2;
(iii)
E
1
∩
E
2
=
ϕ;
(iv)
k
1
+
k
2
=
k.Example 13.
A
=
b
a
b
a
◊
c, B
=
a
b
a
a
◊
c, then there exists partial array Z
=
a
b
b
a
◊
c with E
1
=
{
(
1,1
)
,
(
1,2
)
}, E
2
=
{
(
1,3
)
} and k
1
=
2, k
2
=
1
⇒
k
=
3; that is, A
↑
3
B.
Equivalently,A and B are k-compatible, if there exists subset E of D
(
A
)
∩
D
(
B
) of cardinality k called the error set such that (i)
A
(
i
,
j
)
=
B
(
i
,
j
)
∀
(
i
,
j
)
∈
D
(
A
)
∩
D
(
B
)
∖
E;
(ii)
A
(
i
,
j
)
≠
B
(
i
,
j
)
∀
(
i
,
j
)
∈
E
.If A and B are arrays, then A
↑
∘
B means A
=
B. We sometimes use notation A
↑
≤
k
B, if set E has cardinality ≤
k.Multiplication. If A
↑
k
1
B and X
↑
k
2
Y, then A
X
↑
k
1
+
k
2
B
Y where A
,
B
,
X, and Y are partial arrays and k
1
,
k
2 are nonnegative integers, using column catenation.Example 14.
A
=
◊
a
a
b
b
◊
a
b
a, B
=
b
b
◊
a
a
◊
a
a
b, X
=
b
◊
a
a
b
a
a
◊
b, Y
=
a
b
b
b
a
b
◊
◊
a.
A
X
↑
6
+
7
B
Y.Simplification. If A
X
↑
k
B
Y and order of A is equal to order of B, then A
↑
k
1
B and X
↑
k
2
Y for some k
1
,
k
2, satisfying k
1
+
k
2
=
k.Example 15.
A
=
◊
a
a
b
b
◊
a
b
a, B
=
b
b
◊
a
◊
a
b
a
b, X
=
b
◊
a
b
a
◊, Y
=
a
b
b.
A
X
↑
8
B
Y
⇒
A
↑
5
B and X
↑
3
Y with 5 + 3 = 8.Weakening. If A
↑
k
B and Z
⊂
A, then Z
↑
≤
k
B.Example 16.
A
=
◊
a
a
b
b
◊
a
b
a, B
=
b
b
◊
◊
a
◊
b
a
b, Z
=
a
a
b
◊
b
a.
Z
↑
≤
7
B with k
=
7.Theorem 17.
LetA and B be partial arrays of orders a
×
b and a
×
c, respectively. If there exist array Z of order a
×
d and integers k
1
,
k
2
,
m, and n such that A
⊂
k
1
Z
m with error set E
1 and B
⊂
k
2
Z
n with error set E
2, then there exist integers p and q such that A
p
↑
≤
k
B
q with(8)
k
=
D
A
a
,
b
,
p
∩
E
2
a
,
c
,
q
∪
D
B
a
,
c
,
q
∩
E
1
a
,
b
,
p
.Moreover, if E
1
a
,
b
,
n
∩
E
2
a
,
c
,
m
=
ϕ, then A
p
↑
k
B
q.Proof.
LetA and B be partial arrays of a
×
b and a
×
c, respectively. Let array z of order a
×
d exist such that, by using column catenation, A
⊂
k
1
Z
m and B
⊂
k
2
Z
n for some integers k
1
,
k
2
,
m, and n. Let E
1 be the error set of cardinality k
1 such that A
(
i
,
j
)
=
Z
m
(
i
,
j
) for all (
i
,
j
)
∈
D
(
A
)
∖
E
1 and A
(
i
,
j
)
≠
Z
m
(
i
,
j
) for all (
i
,
j
)
∈
E
1 and E
2 be the error set of cardinality k
2 such that B
(
i
,
j
)
=
Z
n
(
i
,
j
) for all (
i
,
j
)
∈
D
(
B
)
∖
E
2 and B
(
i
,
j
)
≠
Z
n
(
i
,
j
) for all (
i
,
j
)
∈
E
2. We have A
n
⊂
n
k
1
Z
m
n with error set E
1
(
a
,
|
b
|
,
n
) of cardinality n
k
1 and B
m
⊂
m
k
2
Z
m
n with error set E
2
(
a
,
|
c
|
,
m
) of cardinality m
k
2.
Let(
1,1
)
≤
(
i
,
j
)
≤
(
a
,
d
m
n
) and Z
m
n
(
i
,
j
)
=
a for some letter a. There are 4 possibilities.
Case 1. If (
i
,
j
)
∉
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∉
E
2
(
a
,
|
c
|
,
m
), then A
n
(
i
,
j
)
∈
{
◊
,
a
} and B
m
(
i
,
j
)
∈
{
◊
,
a
}. It does not give any error, when we align A
n with B
m.
Case 2. If (
i
,
j
)
∉
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∈
E
2
(
a
,
|
c
|
,
m
), then A
n
(
i
,
j
)
∈
{
◊
,
a
} and B
m
(
i
,
j
)
=
b for some b
≠
a. It gives an error in the alignment of A
n with B
m only when A
n
(
i
,
j
)
=
a or when (
i
,
j
)
∈
D
(
A
)
(
a
,
|
b
|
,
n
).
Case 3. If (
i
,
j
)
∈
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∈
E
2
(
a
,
|
c
|
,
m
), then B
m
(
i
,
j
)
∈
{
◊
,
a
} and A
n
(
i
,
j
)
=
b for some b
≠
a. It gives an error in the alignment of A
n with B
m only when B
m
(
i
,
j
)
=
a or when (
i
,
j
)
∈
D
(
B
)
(
a
,
|
c
|
,
m
).
Case 4. If (
i
,
j
)
∈
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∈
E
2
(
a
,
|
c
|
,
m
), then A
n
(
i
,
j
)
=
b for some b
≠
a and B
m
(
i
,
j
)
=
c for some c
≠
a. It gives an error in the alignment of A
n with B
m only when b
≠
c.
Therefore, ifE
1
(
a
,
|
b
|
,
n
)
∩
E
2
(
a
,
|
c
|
,
m
)
=
ϕ then A
n
↑
k
B
m with k
=
(
D
(
a
)
(
a
,
|
b
|
,
n
)
∩
E
2
(
a
,
|
c
|
,
m
)
)
∪
(
D
(
B
)
(
a
,
|
c
|
,
m
)
∩
E
1
(
a
,
|
b
|
,
n
) and E
1
(
a
,
|
b
|
,
n
)
∩
E
2
(
a
,
|
c
|
,
m
)
≠
ϕ then A
n
↑
≤
k
B
m.Example 18.
A
=
a
b
◊
c
a
b
◊
b
a, B
=
a
c
c
b
◊
b, Z
=
a
c
b
.
We haveA
⊂
4
Z
3 with error set E
1
=
1,2
,
2,2
,
2,3
,
3,3, and  B
⊂
2
Z
2 with error set E
2
=
{
(
1,2
)
,
(
2,2
)
}.k
=
6:
(i)
D
(
A
)
=
1,1
,
1,2
,
2,1
,
2,2
,
2,3
,
3,2,3,3.
D
(
B
)
=
1,1
,
1,2
,
2,1
,
2,2
,
3,2
(ii)
D
A
a
,
b
,
2
=
{
1,1
,
1,2
,
2,1
,
2,2, 2,3
,
3,2
,
3,3
,
1,4
,
1,5
,
2,4
,
2,5, 2,6
,
3,5
,
3,6
}.
D
(
B
)
(
a
,
c
,
3
)
=
1,1
,
1,2
,
2,1
,
2,2, 3,2
,
1,3
,
1,4
,
2,3
,
2,4
,
3,4
,
1,5, 1,6
,
2,5
,
2,6
,
3,6
(iii)
E
1
(
a
,
b
,
2
)
=
(
1,2
)
,
(
2,2
)
,
(
2,3
)
,
(
3,3
)
,
(
1,5
), 2,5
,
(
2,6
)
,
(
3,6
).
E
2
a
,
c
,
3
=
{
1,2
,
2,2
,
1,4
,
2,4
,
1,6, 2,6
}.
E
1
(
a
,
b
,
2
)
∩
E
2
(
a
,
c
,
3
)
≠
ϕ.
k
=
(
D
(
A
)
(
a
,
b
,
2
)
∩
E
2
(
a
,
c
,
3
)
)
∪
(
D
(
B
)
(
a
,
c
,
3
)
∩
E
1
(
a
,
b
,
2
)
)
=
(
(
1,1
)
,
(
1,2
)
,
(
2,1
)
,
(
2,2
)
,
(
2,3
), (
3,2
)
,
(
3,3
)
,
(
1,4
)
,
(
1,5
)
,
(
2,4
)
,
(
2,5
)
,
(
2,6
), (
3,5
)
,
(
3,6
)
∩
(
(
1,2
)
,
(
2,2
)
,
(
1,4
)
,
(
2,4
)
,
(
1,6
), 2,6
)
)
∪
(
(
(
1,1
)
,
(
1,2
)
,
(
2,1
)
,
(
2,2
)
,
(
3,2
)
,
(
1,3
)
,
(
1,4
), (
2,3
)
,
(
2,4
)
,
(
3,4
)
,
(
1,5
)
,
(
1,6
)
,
(
2,5
), (
2,6
)
,
(
3,6
)
)
∩
(
(
1,2
)
,
(
2,2
)
,
(
2,3
)
,
(
3,3
)
,
(
1,5
)
,
(
2,5
), (
2,6
)
,
(
3,6
)
)
)
=
(
1,2
)
,
(
1,4
)
,
(
1,5
), (
2,2
)
,
2,3
,
2,4
,
2,5
,
(
2,6
)
,
(
3,6
).
k
=
9:
A
2
↑
≤
9
B
3
(
A
2
↑
6
B
3
).


## 4.1. Compatibility

The rules mentioned for partial words are also true for partial arrays.LetA
,
B
,
X
,
Y be partial arrays.(i)
Multiplication: If A
↑
B and X
↑
Y, then A
X
↑
B
Y either by column catenation or by row catenation.
(ii)
Simplification: If A
X
↑
B
Y either by column catenation or by row catenation with A and B being of same size, then A
↑
B and X
↑
Y.
(iii)
Weakening: If A
↑
B and C
⊂
A, then C
↑
B.Lemma3’s version for partial arrays can be stated as follows.Lemma 10.
LetA
,
B
,
X
,
Y be partial arrays such that A
X
↑
B
Y, either by column catenation or by row catenation. (i)
If order ofA
≥ order of B, then there exist partial arrays C, Z such that A
=
C
Z, B
↑
C, and Y
↑
Z
X.
(ii)
If order ofA
≤ order of B, then there exist partial arrays C, Z such that B
=
C
Z, A
↑
C, and X
↑
Z
Y.


## 4.2.k-Compatibility

Definition 11.
IfA and B are two partial arrays of same size and k is nonnegative integer, then A is said to be k-contained in B denoted by A
⊂
k
B if D
(
A
)
⊂
D
(
B
) and there exists subset E of D
(
A
) of cardinality k called the error set such that (7)Ai,j=Bi,j∀i,j∈DA∖E,Ai,j≠Bi,j∀i,j∈E.Definition 12.
IfA and B are two partial arrays of same order and k is a nonnegative integer, then A and B are called k-compatible denoted by A
↑
k
B if there exist partial array Z and nonnegative integers k
1
,
k
2 such that(i)
A
⊂
k
1
Z with error set E
1;
(ii)
B
⊂
k
2
Z with error set E
2;
(iii)
E
1
∩
E
2
=
ϕ;
(iv)
k
1
+
k
2
=
k.Example 13.
A
=
b
a
b
a
◊
c, B
=
a
b
a
a
◊
c, then there exists partial array Z
=
a
b
b
a
◊
c with E
1
=
{
(
1,1
)
,
(
1,2
)
}, E
2
=
{
(
1,3
)
} and k
1
=
2, k
2
=
1
⇒
k
=
3; that is, A
↑
3
B.
Equivalently,A and B are k-compatible, if there exists subset E of D
(
A
)
∩
D
(
B
) of cardinality k called the error set such that (i)
A
(
i
,
j
)
=
B
(
i
,
j
)
∀
(
i
,
j
)
∈
D
(
A
)
∩
D
(
B
)
∖
E;
(ii)
A
(
i
,
j
)
≠
B
(
i
,
j
)
∀
(
i
,
j
)
∈
E
.If A and B are arrays, then A
↑
∘
B means A
=
B. We sometimes use notation A
↑
≤
k
B, if set E has cardinality ≤
k.Multiplication. If A
↑
k
1
B and X
↑
k
2
Y, then A
X
↑
k
1
+
k
2
B
Y where A
,
B
,
X, and Y are partial arrays and k
1
,
k
2 are nonnegative integers, using column catenation.Example 14.
A
=
◊
a
a
b
b
◊
a
b
a, B
=
b
b
◊
a
a
◊
a
a
b, X
=
b
◊
a
a
b
a
a
◊
b, Y
=
a
b
b
b
a
b
◊
◊
a.
A
X
↑
6
+
7
B
Y.Simplification. If A
X
↑
k
B
Y and order of A is equal to order of B, then A
↑
k
1
B and X
↑
k
2
Y for some k
1
,
k
2, satisfying k
1
+
k
2
=
k.Example 15.
A
=
◊
a
a
b
b
◊
a
b
a, B
=
b
b
◊
a
◊
a
b
a
b, X
=
b
◊
a
b
a
◊, Y
=
a
b
b.
A
X
↑
8
B
Y
⇒
A
↑
5
B and X
↑
3
Y with 5 + 3 = 8.Weakening. If A
↑
k
B and Z
⊂
A, then Z
↑
≤
k
B.Example 16.
A
=
◊
a
a
b
b
◊
a
b
a, B
=
b
b
◊
◊
a
◊
b
a
b, Z
=
a
a
b
◊
b
a.
Z
↑
≤
7
B with k
=
7.Theorem 17.
LetA and B be partial arrays of orders a
×
b and a
×
c, respectively. If there exist array Z of order a
×
d and integers k
1
,
k
2
,
m, and n such that A
⊂
k
1
Z
m with error set E
1 and B
⊂
k
2
Z
n with error set E
2, then there exist integers p and q such that A
p
↑
≤
k
B
q with(8)
k
=
D
A
a
,
b
,
p
∩
E
2
a
,
c
,
q
∪
D
B
a
,
c
,
q
∩
E
1
a
,
b
,
p
.Moreover, if E
1
a
,
b
,
n
∩
E
2
a
,
c
,
m
=
ϕ, then A
p
↑
k
B
q.Proof.
LetA and B be partial arrays of a
×
b and a
×
c, respectively. Let array z of order a
×
d exist such that, by using column catenation, A
⊂
k
1
Z
m and B
⊂
k
2
Z
n for some integers k
1
,
k
2
,
m, and n. Let E
1 be the error set of cardinality k
1 such that A
(
i
,
j
)
=
Z
m
(
i
,
j
) for all (
i
,
j
)
∈
D
(
A
)
∖
E
1 and A
(
i
,
j
)
≠
Z
m
(
i
,
j
) for all (
i
,
j
)
∈
E
1 and E
2 be the error set of cardinality k
2 such that B
(
i
,
j
)
=
Z
n
(
i
,
j
) for all (
i
,
j
)
∈
D
(
B
)
∖
E
2 and B
(
i
,
j
)
≠
Z
n
(
i
,
j
) for all (
i
,
j
)
∈
E
2. We have A
n
⊂
n
k
1
Z
m
n with error set E
1
(
a
,
|
b
|
,
n
) of cardinality n
k
1 and B
m
⊂
m
k
2
Z
m
n with error set E
2
(
a
,
|
c
|
,
m
) of cardinality m
k
2.
Let(
1,1
)
≤
(
i
,
j
)
≤
(
a
,
d
m
n
) and Z
m
n
(
i
,
j
)
=
a for some letter a. There are 4 possibilities.
Case 1. If (
i
,
j
)
∉
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∉
E
2
(
a
,
|
c
|
,
m
), then A
n
(
i
,
j
)
∈
{
◊
,
a
} and B
m
(
i
,
j
)
∈
{
◊
,
a
}. It does not give any error, when we align A
n with B
m.
Case 2. If (
i
,
j
)
∉
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∈
E
2
(
a
,
|
c
|
,
m
), then A
n
(
i
,
j
)
∈
{
◊
,
a
} and B
m
(
i
,
j
)
=
b for some b
≠
a. It gives an error in the alignment of A
n with B
m only when A
n
(
i
,
j
)
=
a or when (
i
,
j
)
∈
D
(
A
)
(
a
,
|
b
|
,
n
).
Case 3. If (
i
,
j
)
∈
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∈
E
2
(
a
,
|
c
|
,
m
), then B
m
(
i
,
j
)
∈
{
◊
,
a
} and A
n
(
i
,
j
)
=
b for some b
≠
a. It gives an error in the alignment of A
n with B
m only when B
m
(
i
,
j
)
=
a or when (
i
,
j
)
∈
D
(
B
)
(
a
,
|
c
|
,
m
).
Case 4. If (
i
,
j
)
∈
E
1
(
a
,
|
b
|
,
n
) and (
i
,
j
)
∈
E
2
(
a
,
|
c
|
,
m
), then A
n
(
i
,
j
)
=
b for some b
≠
a and B
m
(
i
,
j
)
=
c for some c
≠
a. It gives an error in the alignment of A
n with B
m only when b
≠
c.
Therefore, ifE
1
(
a
,
|
b
|
,
n
)
∩
E
2
(
a
,
|
c
|
,
m
)
=
ϕ then A
n
↑
k
B
m with k
=
(
D
(
a
)
(
a
,
|
b
|
,
n
)
∩
E
2
(
a
,
|
c
|
,
m
)
)
∪
(
D
(
B
)
(
a
,
|
c
|
,
m
)
∩
E
1
(
a
,
|
b
|
,
n
) and E
1
(
a
,
|
b
|
,
n
)
∩
E
2
(
a
,
|
c
|
,
m
)
≠
ϕ then A
n
↑
≤
k
B
m.Example 18.
A
=
a
b
◊
c
a
b
◊
b
a, B
=
a
c
c
b
◊
b, Z
=
a
c
b
.
We haveA
⊂
4
Z
3 with error set E
1
=
1,2
,
2,2
,
2,3
,
3,3, and  B
⊂
2
Z
2 with error set E
2
=
{
(
1,2
)
,
(
2,2
)
}.k
=
6:
(i)
D
(
A
)
=
1,1
,
1,2
,
2,1
,
2,2
,
2,3
,
3,2,3,3.
D
(
B
)
=
1,1
,
1,2
,
2,1
,
2,2
,
3,2
(ii)
D
A
a
,
b
,
2
=
{
1,1
,
1,2
,
2,1
,
2,2, 2,3
,
3,2
,
3,3
,
1,4
,
1,5
,
2,4
,
2,5, 2,6
,
3,5
,
3,6
}.
D
(
B
)
(
a
,
c
,
3
)
=
1,1
,
1,2
,
2,1
,
2,2, 3,2
,
1,3
,
1,4
,
2,3
,
2,4
,
3,4
,
1,5, 1,6
,
2,5
,
2,6
,
3,6
(iii)
E
1
(
a
,
b
,
2
)
=
(
1,2
)
,
(
2,2
)
,
(
2,3
)
,
(
3,3
)
,
(
1,5
), 2,5
,
(
2,6
)
,
(
3,6
).
E
2
a
,
c
,
3
=
{
1,2
,
2,2
,
1,4
,
2,4
,
1,6, 2,6
}.
E
1
(
a
,
b
,
2
)
∩
E
2
(
a
,
c
,
3
)
≠
ϕ.
k
=
(
D
(
A
)
(
a
,
b
,
2
)
∩
E
2
(
a
,
c
,
3
)
)
∪
(
D
(
B
)
(
a
,
c
,
3
)
∩
E
1
(
a
,
b
,
2
)
)
=
(
(
1,1
)
,
(
1,2
)
,
(
2,1
)
,
(
2,2
)
,
(
2,3
), (
3,2
)
,
(
3,3
)
,
(
1,4
)
,
(
1,5
)
,
(
2,4
)
,
(
2,5
)
,
(
2,6
), (
3,5
)
,
(
3,6
)
∩
(
(
1,2
)
,
(
2,2
)
,
(
1,4
)
,
(
2,4
)
,
(
1,6
), 2,6
)
)
∪
(
(
(
1,1
)
,
(
1,2
)
,
(
2,1
)
,
(
2,2
)
,
(
3,2
)
,
(
1,3
)
,
(
1,4
), (
2,3
)
,
(
2,4
)
,
(
3,4
)
,
(
1,5
)
,
(
1,6
)
,
(
2,5
), (
2,6
)
,
(
3,6
)
)
∩
(
(
1,2
)
,
(
2,2
)
,
(
2,3
)
,
(
3,3
)
,
(
1,5
)
,
(
2,5
), (
2,6
)
,
(
3,6
)
)
)
=
(
1,2
)
,
(
1,4
)
,
(
1,5
), (
2,2
)
,
2,3
,
2,4
,
2,5
,
(
2,6
)
,
(
3,6
).
k
=
9:
A
2
↑
≤
9
B
3
(
A
2
↑
6
B
3
).


## 5. Conjugacy andk-Conjugacy of Partial Arrays

### 5.1. Conjugacy

Definition 19.
Two partial arraysA and B of same order are called conjugate if there exist partial arrays X and Y such that A
⊂
X
Y and B
⊂
Y
X using row catenation or column catenation.0-conjugacy on partial arrays with same order is trivially reflexive and symmetric but not transitive.Example 20.
A
=
a
◊
b
b
c
a
a
a
◊, B
=
b
c
◊
a
a
◊
a
c
b, C
=
b
a
◊
b
a
◊
a
b
c.
By takingX
=
a
c
b and Y
=
b
c
a
a
a
◊, we get A
⊂
X
Y and B
⊂
Y
X showing that A and B are conjugate similarly and, by taking X
′
=
b
c
◊ and Y
′
=
a
c
b, we get B
⊂
X
′
Y
′ and C
⊂
Y
′
X
′ showing that B and C are conjugate. But A and C are not conjugate.
That is, conjugate relation is not transitive.Proposition 21.
LetA and B be nonempty partial arrays of same size. If A and B are conjugate, then there exists partial array C such that A
C
↑
C
B, either by column catenation or by row catenation.Proof.
LetA and B be nonempty partial arrays of same order. Suppose A and B are conjugate and let X
,
Y be partial arrays such that A
⊂
X
Y and B
⊂
Y
X either by column catenation or by row catenation; then A
X
⊂
X
Y
X and X
B
⊂
X
Y
X. So, for C
=
X, we have A
C
↑
C
B.


### 5.2.k-Conjugacy

Definition 22.
Two partial arraysA and B of same order are k-conjugate, if there exist nonnegative integers k
1
k
2 whose sum is k and partial arrays X and Y such that A
⊂
k
1
X
Y and B
⊂
k
2
Y
X with row or column catenation.Theorem 23.
LetA and B be nonempty partial arrays of same order. If A and B are k-conjugate, then there exists partial array Z such that A
Z
↑
≤
k
Z
B.Proof.
LetA
,
B be two partial arrays of same order. Supposing that A and B are k-conjugate, then, by definition, there exist nonnegative integers k
1, k
2 whose sum is k and partial arrays X and Y such that A
⊂
k
1
X
Y with error set E
1 and B
⊂
k
2
Y
X with error set E
2 using row catenation or column catenation accordingly.
Then,A
X
⊂
k
1
X
Y
X with error set E
1 and X
B
⊂
k
2
X
Y
X with error set E
2
′
=
{
(
i
+
n
u
m
b
e
r
o
f
r
o
w
s
o
f
X
,
j
)
/
(
i
,
j
)
∈
E
2
} or E
2
′
=
{
(
i
,
j
+
n
u
m
b
e
r
o
f
c
o
l
u
m
n
s
o
f
X
)
/
(
i
,
j
)
∈
E
2
} according to row or column catenation and so, for Z
=
X, we have A
Z
↑
≤
k
Z
B.Example 24.
GivenA
=
a
◊
b
b
c
a
a
a
◊, B
=
b
c
b
a
a
◊
a
◊
b.
There existX
=
a
◊
b and Y
=
c
a
b
a
a
◊ with A
⊂
3
X
Y and B
⊂
2
Y
X, k
=
k
1
+
k
2
=
5.
There existZ
=
a
◊
b such that A
Z
↑
≤
5
Z
B.


## 5.1. Conjugacy

Definition 19.
Two partial arraysA and B of same order are called conjugate if there exist partial arrays X and Y such that A
⊂
X
Y and B
⊂
Y
X using row catenation or column catenation.0-conjugacy on partial arrays with same order is trivially reflexive and symmetric but not transitive.Example 20.
A
=
a
◊
b
b
c
a
a
a
◊, B
=
b
c
◊
a
a
◊
a
c
b, C
=
b
a
◊
b
a
◊
a
b
c.
By takingX
=
a
c
b and Y
=
b
c
a
a
a
◊, we get A
⊂
X
Y and B
⊂
Y
X showing that A and B are conjugate similarly and, by taking X
′
=
b
c
◊ and Y
′
=
a
c
b, we get B
⊂
X
′
Y
′ and C
⊂
Y
′
X
′ showing that B and C are conjugate. But A and C are not conjugate.
That is, conjugate relation is not transitive.Proposition 21.
LetA and B be nonempty partial arrays of same size. If A and B are conjugate, then there exists partial array C such that A
C
↑
C
B, either by column catenation or by row catenation.Proof.
LetA and B be nonempty partial arrays of same order. Suppose A and B are conjugate and let X
,
Y be partial arrays such that A
⊂
X
Y and B
⊂
Y
X either by column catenation or by row catenation; then A
X
⊂
X
Y
X and X
B
⊂
X
Y
X. So, for C
=
X, we have A
C
↑
C
B.


## 5.2.k-Conjugacy

Definition 22.
Two partial arraysA and B of same order are k-conjugate, if there exist nonnegative integers k
1
k
2 whose sum is k and partial arrays X and Y such that A
⊂
k
1
X
Y and B
⊂
k
2
Y
X with row or column catenation.Theorem 23.
LetA and B be nonempty partial arrays of same order. If A and B are k-conjugate, then there exists partial array Z such that A
Z
↑
≤
k
Z
B.Proof.
LetA
,
B be two partial arrays of same order. Supposing that A and B are k-conjugate, then, by definition, there exist nonnegative integers k
1, k
2 whose sum is k and partial arrays X and Y such that A
⊂
k
1
X
Y with error set E
1 and B
⊂
k
2
Y
X with error set E
2 using row catenation or column catenation accordingly.
Then,A
X
⊂
k
1
X
Y
X with error set E
1 and X
B
⊂
k
2
X
Y
X with error set E
2
′
=
{
(
i
+
n
u
m
b
e
r
o
f
r
o
w
s
o
f
X
,
j
)
/
(
i
,
j
)
∈
E
2
} or E
2
′
=
{
(
i
,
j
+
n
u
m
b
e
r
o
f
c
o
l
u
m
n
s
o
f
X
)
/
(
i
,
j
)
∈
E
2
} according to row or column catenation and so, for Z
=
X, we have A
Z
↑
≤
k
Z
B.Example 24.
GivenA
=
a
◊
b
b
c
a
a
a
◊, B
=
b
c
b
a
a
◊
a
◊
b.
There existX
=
a
◊
b and Y
=
c
a
b
a
a
◊ with A
⊂
3
X
Y and B
⊂
2
Y
X, k
=
k
1
+
k
2
=
5.
There existZ
=
a
◊
b such that A
Z
↑
≤
5
Z
B.


## 6. Conclusion

Motivated by compatibility and conjugacy properties of partial words, we define the conjugacy of partial array and derive the compatibility properties of partial arrays. By giving relaxation to the compatibility relation, we discussk-compatibility and k-conjugacy of partial arrays. We prove that, given partial arrays A
,
B and integers p
,
q satisfying |
A
|
p
=
|
B
|
q, we find k such that A
p
↑
k
B
q. Also, there exists partial array Z such that A
Z
↑
≤
k
Z
B.



---

*Source: 5010316-2016-09-28.xml*