# Compatibility and Conjugacy on Partial Arrays.

1. IntroductionThe 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 array A of size (m, n) over [SIGMA], a finite alphabet, is partial function A : [Z.sub.2.sub.+] [right arrow] Z, where [Z.sub.+] 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 word u of length n over A, a nonempty finite alphabet, is partial map u : {1, 2, ..., n} [right arrow] A. If 1 [less than or equal to] i [less than or equal to] n, then i belongs to the domain of u (denoted by Domain(w)) in the case where u(i) is defined, and i belongs to the set of holes of u (denoted by Hole(w)), otherwise.

A word [8-10] is a partial word over A with an empty set of holes.

Definition 2. Let u be a partial word of length n over A. The companion of u (denoted by [u.sub.[??]]) is map [u.sub.[??]] : {1, 2, ..,, n} [right arrow] A [union] {[??]} defined by

[mathematical expression not reproducible]. (1)

The symbol [??] is viewed as a "do not know" symbol. Word [u.sub.[??]] = ba[??]ab[??]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}.

Let u and v be two partial words of length n. Partial word u is said to be contained in partial word v (denoted by u [subset] v), if Domain(u) [subset] Domain(v) and u(i) = v(i) for all i [member of]e Domain(w). Partial words u and v are called compatible (denoted by u [up arrow] v), if there exists partial word w such that u [subset] w and v [subset] w (in which case we define uV v by u c uV v and v [subset] u [disjunction] v and Domain(u) [disjunction] v) = Domain(w) [union] Domain(v)). As an example, [u.sub.[??]] = aba[??][??]a and [v.sub.[??]] = abab[??]a.

The following rules are useful for computing with partial words:

(i) Multiplication: If u [up arrow] v and x [up arrow] y, then ux [up arrow] vy.

(ii) Simplification: If ux [up arrow] vy and [absolute value of u] = [absolute value of v], then u [up arrow] v and x [up arrow] y.

(iii) Weakening: If u [up arrow] v and w [subset] u, then w [up arrow] v.

Lemma 3. Let u, v, x, y be partial words such that ux [up arrow] vy.

(i) If [absolute value of u] [greater than or equal to] [absolute value of v], then there exist partial words w, z such that u = wz, v [up arrow] w, and y [up arrow] zx.

(ii) If [absolute value of u] [less than or equal to] [absolute value of v], then there exist partial words w, z such that b = wz, v [up arrow] w, and x [up arrow] zy.

Definition 4. Two partial words u and v are called conjugate, if there exist partial words x and y such that u [subset] xy and v [subset] yx.

Definition 5. Two partial words u and v are called k-conjugate, if there exist nonnegative integers [k.sub.1], [k.sub.2] whose sum is k and partial words x and y such that [mathematical expression not reproducible].

3. Preliminaries on Partial Arrays

This section is devoted to review the basic concepts on partial arrays [11].

Definition 6. Partial array A of size (m, n) over [SIGMA], a nonempty set or an alphabet, is partial function A: [Z.sup.2.sub.+] [right arrow] [SIGMA], where [Z.sub.+] is the set of all positive integers. For 1 [less than or equal to] i [less than or equal to] m, 1 [less than or equal to] j [less than or equal to] n, and if A(i, j) is defined, then we say that (i, j) belongs to the domain of A (denoted by (i, j) [member of] D(A)). Otherwise, we say that (i, j) belongs to the set of holes of A (denoted by (i, j) [member of] H(A)).

An array [5] over [SIGMA] is a partial array over [SIGMA] with an empty set of holes.

Definition 7. If A is a partial array of size (m, n) over [SIGMA], then the companion of A (denoted by [A.sub.[??]]) is total function [A.sub.[??]]: [Z.sup.2.sub.+] [right arrow] [SIGMA] [union] {[??]} defined by

[mathematical expression not reproducible], (2)

where [??] [not equal to] [SIGMA].

The bijectivity of map A [right arrow] [A.sub.[??]] allows defining the catenation of two partial arrays in a trivial way.

Example 8. Partial array [mathematical expression not reproducible] 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

[mathematical expression not reproducible]. (3)

By column catenation, we mean

[mathematical expression not reproducible]. (4)

By row catenation, we mean

[mathematical expression not reproducible]. (5)

If A and B are two partial arrays of equal size, then A is contained in B denoted by A [subset] B if D(A) [subset or equal to] D(B) and

A(i, j) = B(i, j) y(i, j) [member of] D(A). (6)

Definition 9. Partial arrays A and B are said to be compatible denoted by A [up arrow] B, if there exists partial array C such that A [subset] C and B [subset] C.

4. Compatibiltiy and k-Compatability of Partial Arrays

4.1. Compatibility. The rules mentioned for partial words are also true for partial arrays.

Let A, B, X, Y be partial arrays.

(i) Multiplication: If A [up arrow] B and X [up arrow] Y, then AX [up arrow] BY either by column catenation or by row catenation.

(ii) Simplification: If AX [up arrow] BY either by column catenation or by row catenation with A and B being of same size, then A [up arrow] B and X [up arrow] Y.

(iii) Weakening: If A [up arrow] B and C [subset] A, then C [up arrow] B.

Lemma 3's version for partial arrays can be stated as follows.

Lemma 10. Let A, B, X, Y be partial arrays such that AX [up arrow] BY, either by column catenation or by row catenation.

(i) If order of A [greater than or equal to] order of B, then there exist partial arrays C, Z such that A = CZ, B [up arrow] C, and Y [up arrow] ZX.

(ii) If order of A [less than or equal to] order of B, then there exist partial arrays C, Z such that B = CZ, A [up arrow] C, and X [up arrow] ZY.

4.2. k-Compatibility

Definition 11. If A 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 [subset] [sub.k]B if D(A) [subset] D(B) and there exists subset E of D(A) of cardinality k called the error set such that

[mathematical expression not reproducible]. (7)

Definition 12. If A 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 [up arrow] [sub.k]B if there exist partial array Z and nonnegative integers [k.sub.1], [k.sub.2] such that

(i) [mathematical expression not reproducible];

(ii) [mathematical expression not reproducible];

(iii) [E.sub.1] [intersection] [E.sub.2] = [phi];

(iv) [k.sub.1] + [k.sub.2] = k.

Example 13. [mathematical expression not reproducible], then there exists partial array [mathematical expression not reproducible] with [E.sub.1] = {(1, 1), (1, 2)}, [E.sub.2] = {(1, 3)} and [k.sub.1] = 2, [k.sub.2] = 1 [??] k = 3; that is, A [up arrow] [sub.3]B.

Equivalently, A and B are k-compatible, if there exists subset E of D(A) [intersection] D(B) of cardinality k called the error set such that

(i) A(i, j) = B(i, j) [for all] (i, j) [member of] D(A) [intersection] D(B) \ E;

(ii) A(i, j) [not equal to] B(i,j) [for all] (i, j) [member of] E.

If A and B are arrays, then A [up arrow] [sup.[??]]B means A = B. We sometimes use notation A [up arrow] [sub.[less than or equal to]k]B, if set E has cardinality [less than or equal to] k.

Multiplication. If [mathematical expression not reproducible] where A, B, X, and Y are partial arrays and [k.sub.1], [k.sub.2] are nonnegative integers, using column catenation.

Example 14. [mathematical expression not reproducible].

Simplification. If AX [up arrow] [sub.k]BY and order of A is equal to order of B, then [mathematical expression not reproducible] for some [k.sub.1], [k.sub.2], satisfying [k.sub.1] + [k.sub.2] = k.

Example 15. [mathematical expression not reproducible].

Weakening. If A [up arrow] [sub.k]B and Z [subset] A, then Z [up arrow] [sub.[less than or equal to]k]B.

Example 16. [mathematical expression not reproducible].

Theorem 17. Let A and B be partial arrays of orders a x b and a x c, respectively. If there exist array Z of order a x d and integers [k.sub.1], [k.sub.2], m, and n such that [mathematical expression not reproducible] with error set [mathematical expression not reproducible] with error set [E.sub.2], then there exist integers p and q such that [A.sup.p] [up arrow] [sub.[less than or equal to]k][B.sup.q] with

[mathematical expression not reproducible]. (8)

Moreover, [mathematical expression not reproducible].

Proof. Let A and B be partial arrays of a x b and a x x, respectively. Let array z of order a x d exist such that, by using column catenation, [mathematical expression not reproducible] for some integers [k.sub.1], [k.sub.2], m, and n. Let [E.sub.1] be the error set of cardinality [k.sub.1] such that A(i, j) = [Z.sup.m](i, j) for all (i, j) [member of] D(A) \ [E.sub.1] and A(i, j) [not equal to] [Z.sup.m](i, j) for all (i, j) [member of] [E.sub.1] and [E.sub.2] be the error set of cardinality [k.sub.2] such that B(i, j) = [Z.sup.n](i, j) for all (i, j) [member of] D(B) \ [E.sub.2] and B(i, j) [not equal to] [Z.sup.n](i, j) for all (i, j) [member of] [E.sub.2]. We have [mathematical expression not reproducible] with error set [E.sub.1] (a, [absolute value of b], n) of cardinality [mathematical expression not reproducible] with error set [E.sub.2] (a, [absolute value of c], m) of cardinality m[k.sub.2].

Let (1, 1) [less than or equal to] (i, j) [less than or equal to] (a, [d.sup.mn]) and [Z.sup.mn] (i, j) = a for some letter a. There are 4 possibilities.

Case 1. [mathematical expression not reproducible]. It does not give any error, when we align [A.sup.n] with [B.sup.m].

Case 2. [mathematical expression not reproducible]. It gives an error in the alignment of [A.sup.n] with [B.sup.m] only when [A.sup.n](i, j) = a or when (i, j) [member of] D(A)(a, [absolute value of b], n).

Case 3. [mathematical expression not reproducible]. It gives an error in the alignment of [A.sup.n] with [B.sup.m] only when [B.sup.m](i, j) = a or when (i, j) [member of] D(B)(a, [absolute value of c], m).

Case 4. [mathematical expression not reproducible]. It gives an error in the alignment of [A.sup.n] with [B.sup.m] only when b [not equal to] c.

Therefore, [mathematical expression not reproducible].

Example 18. [mathematical expression not reproducible].

We have A [subset] [sub.4][Z.sup.3] with error set El = {(1, 2), (2, 2), (2, 3), (3, 3)}, and B [subset] [sub.2][Z.sup.2] with error set [E.sub.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, [absolute value of 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, [absolute value of 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.sub.1] (a, [absolute value of b], 2) = {(1, 2), (2, 2), (2,3), (3,3), (1, 5), (2, 5), (2, 6), (3, 6)}.

[E.sub.2] (a, [absolute value of c], 3) = {(1, 2), (2, 2), (1, 4), (2, 4), (1, 6), (2, 6)}.

[E.sub.l] (a, [absolute value of b], 2) [intersection] [E.sub.2] (a, [absolute value of c], 3) [not equal to] [phi].

[mathematical expression not reproducible].

5. Conjugacy and k-Conjugacy of Partial Arrays

5.1. Conjugacy

Definition 19. Two partial arrays A and B of same order are called conjugate if there exist partial arrays X and Y such that A [subset] XY and B [subset] YX using row catenation or column catenation.

0-conjugacy on partial arrays with same order is trivially reflexive and symmetric but not transitive.

Example 20. [mathematical expression not reproducible].

By taking X = (a c b) and[mathematical expression not reproducible], we get A [subset] XY and B [subset] YX showing that A and B are conjugate similarly and, by taking X' = (b c [??]) and Y' = (a c b), we get B [subset] X'Y' and C [subset] 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. Let A and B be nonempty partial arrays of same size. If A and B are conjugate, then there exists partial array C such that AC [up arrow] CB, either by column catenation or by row catenation.

Proof. Let A 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 [subset] XY and B [subset] YX either by column catenation or by row catenation; then AX [subset] XYX and XB [subset] XYX. So, for C = X, we have AC [up arrow] CB.

5.2. k-Conjugacy

Definition 22. Two partial arrays A and B of same order are k-conjugate, if there exist nonnegative integers [k.sub.1][k.sub.2] whose sum is k and partial arrays X and Y such that [mathematical expression not reproducible] with row or column catenation.

Theorem 23. Let A and B be nonempty partial arrays of same order. If A and B are k-conjugate, then there exists partial array Z such that AZ [up arrow] [sub.k]ZB.

Proof. Let A, B be two partial arrays of same order. Supposing that A and B are k-conjugate, then, by definition, there exist nonnegative integers [k.sub.l], [k.sub.2] whose sum is k and partial arrays X and Y such that [mathematical expression not reproducible] with error set [mathematical expression not reproducible] with error set [E.sub.2] using row catenation or column catenation accordingly.

Then, [mathematical expression not reproducible] with error set [E.sub.1] and [mathematical expression not reproducible] with error set [E'.sub.2] = {(i + number of rows of X, j)/(i, j) [member of] [E.sub.2]} or [E'.sub.2] = {(i, j + number of columns of X)/(i, j) [member of] [E.sub.2]} according to row or column catenation and so, for Z = X, we have AZ [up arrow] [sub.[less than or equal to]k]ZB.

Example 24. [mathematical expression not reproducible].

There exist [mathematical expression not reproducible].

There exist Z = (a [??] b) such that AZ [up arrow] [sub.[less than or equal to]5]ZB.

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 discuss k-compatibility and k-conjugacy of partial arrays. We prove that, given partial arrays A, B and integers p, q satisfying [[absolute value of A].sup.P] = [[absolute value of B].sup.P], we find k such that [A.sup.p] [up arrow] [sub.k][B.sup.q]. Also, there exists partial array Z such that AZ [up arrow] [sub.[less than or equal to]k]ZB.

http://dx.doi.org/10.1155/2016/5010316

Disclosure

S. Vijayachitra is a Research Scholar at Department of Science and Humanity Sathyabama University, Chennai, India.

Competing Interests

The authors declare that they have no competing interests.

References

[1] D. G. Arques and Ch. J. Michel, "A possible code in the genetic code," in STACS 95, vol. 900 of Lecture Notes in Computer Science, pp. 640-651, Springer, Berlin, Germany, 1995.

[2] F. Blanchet-Sadri and R. A. Hegstrom, "Partial words and a theorem of Fine and Wilf revisited," Theoretical Computer Science, vol. 270, no. 1-2, pp. 401-419, 2002.

[3] A. Colosimo and A. de Luca, "Special factors in biological strings," Journal of Theoretical Biology, vol. 204, no. 1, pp. 29-46, 2000.

[4] F. Blanchet-Sadri, D. Dakota Blair, and R. V. Lewis, "Equations on partial words," RAIRO--Theoretical Informatics and Applications, vol. 43, pp. 23-29, 2009.

[5] F. Sweety, D. G. Thomas, and T. Kalyani, "Collage of hexagonal arrays," in Advances in Visual Computing, G. Bebis, R. Boyle, B. Parvin et al., Eds., vol. 5359 of Lecture Notes in Computer Science, pp. 1167-1175, Springer, Berlin, Germany, 2008.

[6] F. Blanchet-Sadri and D. K. Luhmann, "Conjugacy on partial words," Theoretical Computer Science, vol. 289, no. 1, pp. 297-312, 2002.

[7] J. Berstel and L. Boasson, "Partial words and a theorem of Fine and Wilf," Theoretical Computer Science, vol. 218, no. 1, pp. 135-141, 1999.

[8] A. de Luca, "On the combinatorics of finite words," Theoretical Computer Science, vol. 218, no. 1, pp. 13-39, 1999.

[9] C. Choffrut and J. Karthumaki, "Combinatorics of words," in Handbook of Formal Languages, G. Rozenberg and A. Salomaa, Eds., vol. 1, chapter 6, pp. 329-438, Springer, Berlin, Germany, 1999.

[10] M. Lothaire, Combinatorics on Words, Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK, 1997.

[11] F. Sweety, D. G. Thomas, and V R. Dare, "Subarray complexity of partial arrays," in Intelligent Optimization Modeling, pp. 85-94, Allied, 2006.

S. Vijayachitra (1) and K. Sasikala (2)

(1) Department of Science and Humanity, Sathyabama University, Chennai, India

(2) Department of Mathematics, St. Joseph's College of Engineering, Chennai, India

Correspondence should be addressed to S. Vijayachitra; vijayachitra@live.com

Received 27 March 2016; Revised 28 July 2016; Accepted 3 August 2016

Academic Editor: Qi Dai

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Vijayachitra, S.; Sasikala, K. |

Publication: | Computational and Mathematical Methods in Medicine |

Date: | Jan 1, 2016 |

Words: | 3437 |

Previous Article: | A Computational Model for Investigating Tumor Apoptosis Induced by Mesenchymal Stem Cell-Derived Secretome. |

Next Article: | A Simulation Study to Assess the Effect of the Number of Response Categories on the Power of Ordinal Logistic Regression for Differential Item... |

Topics: |