Let Ak×n be an (m,a,b)-extendable matrix, and let the (k,a,b)-PPM matrix Bm×n be its extension and T(A) be its corresponding tree. Let w be the repeating time function defined on the labeled vertices of T(A) as w(v) = t if and only if v is labeled by r and row r is repeated t times in B. We call (T(A),w) the (m,a,b)-extended tree of A and w(v) the repeating label of v.
Lemma 3. The MAF of column c in B is the sum of the repeating label of the vertices in Tc.
Proof. Let arc = 1. Then, by Lemma 3.2, c is located in a path from root to vertex v with label r. So, v is a vertex of Tc. Let w(v) = t. Corresponding to t repeats of r, we have t ones in column c. Therefore, the MAF of column c is equal to the sum of repeating labels in Tc.
Example 3. For matrices in Example 2, repeating labels and MAFs are shown in . Let Ak×n be an (m,a,b)- extendable matrix and (T(A),w) be the (m,a,b)-extended tree of A. Now, by the previous lemmas, we have the following observations.
Repeating labels and minimum allele frequency (MAF).
- O1: Let u be the ancestor of v in (T(A),w); then the MAF of column u is greater than or equal to the MAF of column v.
- O2: Let v be a leaf with label i in (T(A),w). By proof of Lemma 3.1, column v in Ak×n has only 1 nonzero entry in row i. Since the MAF of column v should be at least a, w(v) ≥ a.
- O3: Let Tui have li leaves and ci labeled internal vertices. By using Lemma 4.1 and O2, the MAF of column ui in B is at least ali + ci.
- O4: Let Tui have li leaves and ci labeled internal vertices. Since the MAF of each column in B is at most b, O3 implies that li ≤ b/a.
- O5: Let x1, x2, …, xd be the children of root r of (T(A),w). Then, using O1 for each labeled vertex xi, we have w(xi)≤b if and only if w(xi)≤b for every labeled vertex of (T(A),w).
In the following theorem, we show that we can always assume that the desired matrix has at least one all-zero row. By the MAF of vertex v in T(A), we mean the MAF of column v in AT.
Theorem 1. There is an (m,a,b)-extendable matrix Ak×n if and only if there is an (m,a,b)-extendable matrix A′k×n that has a zero row.
Proof. It is obvious that root r of T(A) is labeled when A has a zero row.
Let A has no zero rows and r is not labeled. We consider two cases:
- There exists an internal node u, which is labeled by p. In this case, we consider the labeled tree T ′ by removing label p of u and giving p to r.
- Let only the leaves of T(A) be labeled. Consider vertex x such that degree x in Tx is at least 2, and in Tx, every vertex of Tx–x has at most 1 child (as k ≥ 2 and there is no labeled internal node and T(A) has at least two leaves, there exists such x). Let u and v be two leaves of Tx and z be the ancestor of v and the child of x. (If v is a child of x let z = v.) Since u is a leaf of T(A), it has a label such as p. By removing edge xz from T(A), labeling p from u, adding edge uz, and giving p to r, we obtain a new labeled tree T ′ (). In both cases, we define repeating time function w′ on the labeled vertices of T ′ by
New labeled tree T ′ obtained from T.
It is obvious that T ′ is a (k,n)-complete tree, which has a zero row. Now, by using O1, …, O5 and Lemma 3, we conclude that AT′ is (m,a,b)-extendable.