Ancestral Recombinations Graph: A Reconstructability Perspective Using Random-Graphs Framework

Lemma 1

Proof Sketch: We first prove the following two lemmas.

Lemma 2

Let v_l at row g > 1 be an LCA.

(a) For an LCA v at row g′ > g, there exists no path from v to v_l in the pedigree graph.

Proof. (a) This follows directly from the definition of the LCA, i.e., it is not possible to have more than one LCA in a any path on the pedigree graph. (b) Assume the contrary. Case 1: There exists no vertex in row g′ < g with a path from v_l. This is a contradiction since in a pedigree graph there must exist a path from g_l to at least one of the extant vertices. Case 2: There is only one vertex v′ at row g′ < g such that there is a path from v_l. Since v_l is an LCA, there exist paths to all the extant vertices and thus there exist paths from v′ to all the extant vertices contradicting the fact that v_l is an LCA.

Lemma 3

Let an LCA occur at depth g_l with at least one LCA at a depth g′ < g_l and with at least one LCA at a depth g″ > g_l. Then row g_l must have at least five vertices.

Proof. Observe that for each vertex v at any row g, there exist at least two vertices, say v₁ and v₂, in rows > g with paths from v₁ and v₂ to v. If v is an LCA, we call v₁ and v₂ of each row as block-vertices in the proof below. Thus, row g_l has at least two block-vertices corresponding to the LCA at row g′. Also by Lemma 2(b), row g_l has at least two path-vertices. The result follows from the fact that all these vertices are distinct.

Corollary 1

For 1 ≤ N ≤ 2, there exists no instance with infinitely many LCAs.

Proof. Assume the contrary. Then there must exist at least three rows g′ < g_l < g″ with LCAs in each of these rows. Then row g_l must have at least five vertices, leading to a contradiction.

Back to the proof of Lemma 1: Case 1: We construct an instance of the pedigree graph with no LCAs, i.e., Z(K,N) = 0. Let N ≥ 2. This construction is done in the following two steps. Let N = N₁ + N₂ and K = K₁ + K₂ with N₁,N₂ ≥ 1 and K₁,K₂ ≥ 1. In Step 1, construct an instance G¹ of the pedigree graph G_PG(K₁,N₁) and an instance G² of the pedigree graph G_PG(K₂,N₂). In Step 2, construct the union of the two graphs assuming that the two vertex sets are nonoverlapping (distinct labels in the two instances). It can be easily verified that this union is an instance of the pedigree graph G_PG(K,N) and since it has at least two connected components, it has no LCAs.

Case 2: By Corollary 1, N > 2. We create an instance of the random graph G_PG(4,3) that has an infinite number of LCAs, i.e., Z(K,N) =  ∞  (Fig. 3). The construction is as follows. Row 0 has the four extant vertices. The outgoing edges from vertices in Row 0 and 1 are constructed as shown in the figure. The vertices in row 3 and higher are of three categories: (1) Two vertices of different colors called the blocked-vertices (two left vertices in the figure); (2) one vertex, called the LCA-vertex of any color (the middle vertex in the figure); (3) two vertices of the same color, but different from the color of the LCA-vertex called the path-vertices (two right vertices in the figure). The edge constructions follow a simple pattern as shown in the figure. Under this construction, the following can be verified: (1) the instance of the pedigree graph is valid, i.e., the color of the two parents of a node are of different colors, (2) every LCA-vertex of row 2 and higher is indeed the LCA of all the extant vertices.

OPEN IN VIEWER

FIG. 3.

An instance of the pedigree graph G_PG(4,3) (i.e., 4 extant vertices and population of size 3 for each gender at every generation) with an infinite number of LCAs. A possible coloring (or gender assignment) is shown for rows 1 and above; the colors of vertices of row 0 are immaterial. Only the first six rows are shown, marked from 1 to 5 (bottom row is 0). The LCAs are shown with an extra concentric ring. Rows 2 or higher: The block-vertices are the two leftmost vertices; the path-vertices are the two vertices in the right; the LCA-vertex is in the center. The same pattern of edges can be followed for all rows to define an infinite number of LCAs.

Corollary 2

For fixed parameters, K > 1 and N > 2,

1. there are infinite number of instances of G_PG(K,N) each with no LCAs.

Next we make the assumption that any ancestor of an LCA is not of consequence and can be excised from the relevant pedigree graph. Is the pedigree graph after excising all the ancestors of all the LCAs finite? To summarize the answer to the question of finiteness of the excised pedigree graph with fixed parameters K(>1) and N(>2):

It is possible that an instance of the (excised) pedigree graph is infinite.

Lemma 4

The monochromatic subgraph is a forest (tree), i.e., the graph has no closed paths.

Hence the monochromatic subgraph is written as G_PT(K,N).

Lemma 5

Given an instance of a monochromatic subgraph G_PT(K,N):

1. The number of vertices can neither increase with depth nor be zero at any row, i.e., \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} K \geq k_1 \geq k_2 \geq k_3 \geq , \ldots , (\geq 1) . \end{align*} \end{document}

Proof Sketch: 1. This follows from the fact that the graph is a tree. 2. Assume the contrary that an instance has l > 1 LCAs. Let v₁ and v₂ be two distinct LCAs. Then there must exist vertices u₁ and u₂ (possibly with u₁ = u₂) where u₂ is an extant vertex and there is a path from v₁ to u₁, a path from v₂ to u₁ and a path from u₁ to u₂. Further let u₁ be such that there is no other vertex u′ with a path from v₁ to u′, v₂ to u′ and u′ to u₁ (if such is the case then we call u′ as u₁). Observe that each vertex of the monochromatic subgraph has at most one parent. However, u₁ must have at least two parents (each on the two distinct paths to the two LCAs v₁ and v₂) contradicting this fact. Hence the assumption must be wrong and the number of LCAs l ≤ 1. 3. This follows from 2.

Corollary 3

For fixed parameters, K > 1 and N ≥ 1, there are infinitely many monochromatic subgraphs with no LCAs.

Lemma 6

Given G, an instance of a mixed subgraph G_PGE(K,N,M), the following hold.

1. For each vertex v and each edge e of G, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} gm (v) , gm (e) \ne \emptyset. \end{align*} \end{document}

Proof Sketch: (1) This follows from the definition of the mixed subgraph (each node must have genetic material that flows to at least one extant vertex). (2a) Assume that the result is not true: For some m, T_m has a closed path. By the nature of the direction of the edges in the pedigree graph, then there exists a vertex v with two distinct paths P₁ and P₂ to u. Without loss of generality, let the two paths be nonintersecting, except at v and u. Clearly, by Rule 1, the two incoming edges e₁ and e₂ on u cannot be such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$m \in gm (e_1) , gm (e_2)$$ \end{document} . This leads to a contradiction and the assumption is false. (2b) Let the vertex set of G be V and the edge set be E. Then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} V_1 \cup V_2 \cup \ldots \cup V_M \subseteq V , & \qquad \hbox{(\rm by definition of $V_m$)} \\ V \subseteq V_1 \cup V_2 \cup \ldots \cup V_M. & \qquad \hbox{(\rm by (1) each $v$ \rm of $G$ \rm must belong to at lease one of $T_m$)} \end{align*} \end{document}

Thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} V & = V_1 \cup V_2 \cup \ldots \cup V_M , \\ E & = E_1 \cup E_2 \cup \ldots \cup E_M. \qquad \hbox{(\rm by similar arguments)} \end{align*} \end{document}

Hence, the result. (3a, 3b) In each T_m the number of vertices per row does not exceed K. Also, each vertex in T_m must be annotated with the genetic element m. Thus, by 2(b), the number of vertices in G cannot exceed KM and the number of nodes with nonmixing element m cannot exceed K.

See Equation 1 for all possible gm annotations for some fixed values of M,K,k_g. An example is shown in Figure 5 of the embedded trees in an instance of a mixed subgraph. An instance of a graph where each vertex v has genetic material gm(v) defined is said to be gm-annotated. Note that in a monochromatic subgraph, for any two distinct vertices v₁ and v₂, gm(v₁) = gm(v₂). Thus, a monochromatic subgraph can be considered to be always gm-annotated. Also we write the gm annotation of vertex v_i simply as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} gm_i \end{align*} \end{document}

OPEN IN VIEWER

FIG. 5.

(a) An instance of a mixed subgraph G_GE(4,N,7). (b) For clarity, the chain-paths have been replaced by a single edge. (c) G with possible annotation of genetic units {1,2,3,4,5,6,7}. (d–j) The 7 distinct trees (forests), induced by each nonmixing unit i, embedded in G. In other words, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$G = \bigcup\nolimits_{i = 1}^7 T_i.$$ \end{document}

(instead of gm(v_i)). Also if vertex v_i is in row g, the annotation may be also written as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} gm_{g , i}. \end{align*} \end{document}

3.2.1 Topological definition of GMRCA: least common ancestor with ancestry (LCAA)

Conceptually the term LCA is equivalent to MRCA. However, LCA is not equivalent to GMRCA, which additionally is also ancestral to the genetic material in the extant vertices. This is due to the following fact: If node v_a is an ancestor of some node v in G_PG(K,N), then it is possible that not all the genetic material of v_a is ancestral to the genetic material of v. It is also possible that v_a is ancestral to no genetic material of v. In the latter case a topological ancestor is not a “genetic” ancestor. For example, see Figure 6. A natural question is if there exists a purely topology-based definition that captures the notion of a GMRCA. We call this the LCA with ancestry or LCAA, a graph-theory based term for the GMRCA (it is defined in the lemma below). Given G an instance of a mixed subgraph G_PGE(K,N,M), by Lemma 6, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} G = T_1 \cup T_2 \cup \ldots \cup T_M. \end{align*} \end{document}

OPEN IN VIEWER

FIG. 6.

Ancestor without ancestry: Each node is annotated with the genetic material labeled as a combination of A, B, C, D, or -. The symbol “-” denotes material that is not ancestral to any in the extant units. The LCA (shown with an extra concentric ring) has no ancestral material although it is the LCA of the two extant vertices with genetic material AB and CD, respectively. Thus this LCA is an ancestor without any ancestry.

Then,

Lemma 7

Proof Sketch: We prove the second statement first. 2. Let every genetic unit (say a nucleotide) be tagged by a two tuple, its position in the chromosome and the label of extant vertex. Thus, assuming there are c nucleotides and K extant units, there are cK distinct tuples. Next the genetic flow from vertex to vertex through the edges is marked by the tuples. It is easy to see that a path marked with a specific tuple is a chain (that does not branch). Thus, if vertex v is a GMRCA, then by definition, v is on all the cK paths. Thus there cannot exist more than one GMRCA since all the marked paths are chains. 1. Let v″ be the LCAA by definition (a). Note that in tree, T_m, 1 ≤ m ≤ M, the LCA of T_m, say vertex v_m, is also the LCAA of the extant units, corresponding to genetic material m. Further let v′ be the LCA of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$v_1 , v_2 , \ldots , v_M$$ \end{document} . Then, clearly, v′ is a CAA (common ancestor with ancestry) of the K extant units. Case 1: If v″ is an ancestor of v′, it contradicts the definition of LCAA and v′ = v″. Case 2: If v′ is an ancestor of v″, it contradicts the definition of LCA of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$v_1 , v_2 , \ldots , v_M$$ \end{document} and v′ = v″. Case 3: There is no path between v′ and v″. Then both are LCAAs but this contradicts 2. and v′ = v″. Next, let v″ be the LCAA by definition (b). Then v″ is also a CAA of the K extant units. Let v′ be an LCAA. By considering the three cases as before, we show that v′ = v″. 3. This follows from 1. and 2.

Lemma 8

The effective value of M for a pedigree graph with N blue or red vertices at some depth is: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} M = NK^{- 1}. \end{align*} \end{document}

Example 1

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_0 (\cdot)$$ \end{document} ) Let M = 2 and K = 2. Then, the possible gm annotations of three vertices is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal Q}_0 (3) = \left\{\begin{matrix} \left(\{1 \} , \{1 , 2 \} , \{2 \} \right) , & \left(\{1 \} , \{2 \} , \{1 , 2 \} \right) , & \left(\{2 \} , \{1 , 2 \} , \{1 \} \right) , \\ \left(\{2 \} , \{1 \} , \{1 , 2 \} \right) , & \left(\{1 \} , \{2 \} , \{1 , 2 \} \right) , & \left(\{1 , 2 \} , \{2 \} , \{1 \} \right) , \\ \hfill \left(\{1 \} , \{1 \} , \{2 \} \right) , & \hfill \left(\{1 \} , \{2 \} , \{1 \} \right) , &\hfill \left(\{2 \} , \{1 \} , \{1 \} \right) , \\ \hfill \left(\{2 \} , \{2 \} , \{1 \} \right) , &\hfill \left(\{2 \} , \{1 \} , \{2 \} \right) , &\hfill \left(\{1 \} , \{2 \} , \{2 \} \right) \end{matrix} \right\} \end{align*} \end{document}

Example 2

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_1 (\cdot , \cdot)$$ \end{document} ) Let M = 2, K = 2, k_g = 2 and k_g+1 = 3. Then 5 distinct configurations, upto reordering of the vertices in the rows, of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_1 (k_g , k_{g + 1})$$ \end{document} are as follows (vertices in row g + 1 are labeled t, u and v and vertices in row g are labeled x and y):

To avoid clutter, in the following Q₂( · , · ) is written simply as Q( · , · ). Thus, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q} (k_g , k_{g + 1})$$ \end{document} enumerates the distinct gm-annotated (in the genetic exchange model) configurations in two adjacent rows say g and g + 1, with k_g vertices at g and k_g+1 at g + 1. Note that this function does not depend on the value of depth g. A more precise definition of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q} (\cdot , \cdot)$$ \end{document} is as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{split}{\cal Q} (k_g , k_{g + 1}) = \left\{\begin{array}{ll} \coprod_{gm_g \in {\cal Q}_0 (k_g)} {\cal Q}_{ab} (gm_g , k_g , k_{g + 1}) , & \hbox{\hbox{for mixed subgraphs}} \ G_{\rm PGE} (K , N , M) \\ & (\hbox{\hbox{see Eqn 6 below}}) , \\ \hfill{\cal Q}_{cd} (k_g , k_{g + 1}) , & \hbox{\hbox{for monochromatic subgraphs}} \ G_{\rm PT} (K , N) \\ & (\hbox{\hbox{see Eqn 7 below}}) . \end{array} \right. \end{split}\tag{5} \end{align*} \end{document}

Mixed subgraph model. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_{ab}$$ \end{document} is the set of all the configurations with k_g vertices at some row g, with genetic material annotation gm_g, and k_g+1 vertices at the adjacent row g + 1. For N ≥ k_g, k_g+1 ≥ 1: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal Q}_{ab} (gm_g , k_g , k_{g + 1}) = \left\{(q, gm_{g + 1}) \left| \begin{matrix} q = (s_1, s_2, \ldots, s_{k_{g + 1}}), \ \hbox{where} \hfill\\ s_k \ne \emptyset, 1 \leq k \leq k_{g + 1}, \ \hbox{satisfying conditions:} \hfill\\ (1) \ s_1 \cup s_2 \cup \ldots \cup s_{k_{g + 1}} = \{ 1, . , k_g \}. \hfill\\ (2) \ {\rm Let} \ x_i \in s_{k_1} \cap s_{k_2}, \hbox{then} \hfill\\ \quad (a) \, {\rm if} \ k_ 1 \ne k_2 \ {\rm then} \mid gm_{g , i} \mid > 1 \ {\rm and} \ x_i \not \in s_k, k \ne k_1 , \, k_2, \hfill\\ \quad (b) \, (gm_{g , i} \cap gm_{g + 1 , k_1}) \cup (gm_{g, i} \cap gm_{g + 1 , k_2}) = gm_{g , i}. \hfill\\ (3) \, {\rm If} \mid gm_{g, i} \mid = 1 \ \hbox{then there is unique} \ k \ \hbox{with} \ x_i \in s_k. \hfill \end{matrix} \right. \right\}. \tag{6} \end{align*} \end{document}

Condition (1) ensures that every vertex in row g has at least one parent (in row g + 1); condition 2(a) states a vertex with more than one nonmixing unit associated with it, could have at most two parents; condition 2(b) states that the genetic material is split between the parent(s); condition (3) states the condition where a vertex can have only one parent. Further details are presented in Section 6.3.2.

Monochromatic subgraph model. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_{cd}$$ \end{document} is the set of all the configurations with vertex set X_g at some row g, with exactly one parent, and k_g+1 vertices at the adjacent row g + 1. For K ≥ |X_g| ≥ k_{g + 1}  ≥ 1: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal Q}_{cd} (X_g , k_{g + 1}) = \left\{ q \ \left| \begin{matrix} q = (s_1 , s_2 , \ldots , s_{k_{g + 1}}) , \ \hbox{where} \hfill \\ s_k \ne \emptyset , 1 \leq \ k \leq k_{g + 1}, \subset \ X_g \hbox{satisfying conditions:} \hfill \\ (1) \ s_1 \cup s_2 \cup \ldots \cup s_{k_{g + 1}} = X_g. \hfill \\ (2) \ s_{k_1} \cap s_{k_2} = \emptyset \ {for\ all} \ 1 \leq k_1 < k_2 \leq k_{g + 1}. \hfill \end{matrix} \right. \right\} . \tag{7} \end{align*} \end{document}

Condition (1) ensures that every vertex in row g has a parent (in row g + 1); condition (2) ensures that no vertex has more than one parent. Further details are presented in Section 6.3.1.

Back to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q} (\cdot , \cdot)$$ \end{document} . Let Q(k_g, k_g+1) be the number of configurations between two gm-annotated rows with the second row being additionally vertex-labeled. Thus, using Eqn 3. (also equivalently Eqn. 4), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} Q (k_g , k_{g + 1}) = wt (k_{g + 1})\mid {\cal Q} (k_g , k_{g + 1})\mid . \tag{8} \end{align*} \end{document}

Also,

Lemma 9

For all k_g and k_g+1, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} 1 \leq Q (k_g , k_{g + 1}) = {\cal O} (N^{k_{g + 1}}) . \end{align*} \end{document}

4.1.1. Equivalence classes

We identify isomorphic graphs, i.e., the graphs that are isomorphic after forgetting the labels, but not the color. Recall that k_g is the number of vertices at row g of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$G \in {\cal G}_h$$ \end{document} . Furthermore, these isomorphism classes of graphs are characterized by the signature of the graphs contained in them where the signature of a graph G is defined as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \hbox{\rm sig} (G) = (k_1 , k_2 , k_3 , \ldots , k_h) . \end{align*} \end{document}

See Figure 7 for an example of the forgetful graphs. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal G}_{(k_1 , k_2 , \ldots , k_h)} = \left\{G \in {\cal G}_h \mid \hbox{\rm sig} (G) = (k_1 , k_2 , \ldots , k_h) \right\} . \end{align*} \end{document}

OPEN IN VIEWER

FIG. 7.

To limit the number of equivalence classes, here we focus only on the ones where no vertex has only one parent. Then with K = 2, N = 2 and depth h = 2, the equivalence classes are shown with the unlabeled, forgetful member graphs.

To aid in computing the expected location of LCAA in the models, we also define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal F} (g , k) & = \left\{G \in {\cal G}_g \mid G\ has\ k\ vertices\ at\ depth\ g \right\} \\ & = \coprod_{(k_1 , k_2 , . , k_{g} = k) } {\cal G}_{(k_1 , k_2 , . , k_g)} , \quad \hbox{\rm and} \\ F (g , k) & = \mid {\cal F} (g , k) \mid . & (9) \end{align*} \end{document}

Lemma 10

For each h > 0, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \sum_{{\cal G}_{(k_1 , k_2 , \ldots , k_h)} \subset {\cal G}_h} \hbox{\rm len} \left(k_1 , k_2 , \ldots , k_h \right) = 1. \end{align*} \end{document}

Then the uniform probability measure μ on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal G}$$ \end{document} is nothing but the pull-back by ϕ of the usual uniform probability measure (i.e., Lebesgue measure) on [0, 1]. Recall the restriction mapping \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \pi_h: {\cal G} \rightarrow {\cal G}_h , \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$G \in {\cal G}$$ \end{document} is mapped to a π _h (G) that is identical to G upto depth h. Notice that for any fixed h > 0,

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\mid {\cal G}_h \mid < \infty$$ \end{document} , and

For some (event) \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal H} \subset {\cal G}$$ \end{document} and for each fixed h > 0, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} P_ {\cal H} (h) = \frac {\mid \pi_h ({\cal H}) \mid} {\mid \pi_h ({\cal G}) \mid} . \end{align*} \end{document}

Suppose that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \lim_{h \rightarrow \infty} P_{\cal H} (h) = p. \end{align*} \end{document}

Then,

Lemma 11

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal H}$$ \end{document} is measurable and μ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal H}$$ \end{document} ) = ρ.

Proof. For each h > 0, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal H}_h \subset {\cal G}$$ \end{document} denote the measurable set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\pi^{- 1}_h (\pi_h ({\cal H})) .$$ \end{document} Then

Using the bijection ϕ, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mu ({\cal H}_h) & = \sum_{G \in \pi_h ({\cal H})} \mu \left(\pi_h^{- 1} (G) \right) \\ & = \sum_{G \in \pi_h ({\cal H})} \hbox{\rm len} (\hbox{\rm sig} (G)) . \quad \hbox{(\rm by Eqn 11)} \end{align*} \end{document}

 Thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mu ({\cal H} _h) = \frac {\mid \pi_h \left({\cal H} \right) \mid} {\mid \pi_h \left({\cal G} \right) \mid} = P_ {\cal H} (h) . \end{align*} \end{document}

Since each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal H}_h$$ \end{document} is measurable it follows from the above that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\mu ({\cal H}) = p$$ \end{document} .

5.1.1. Common Ancestor with Ancestry (CAA)

Lemma 12

In a relevant pedigree graph (for both models),

1. if there exists a CAA at depth g, then the same is true for all g′ ≥ g, and,

Further, using Lemmas 5 and 7, the probability of a common ancestor with ancestry at depth h of a graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$G \in {\cal G}_h$$ \end{document} is given by: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \frac {F (h , 1)} {F (h , 1) + F (h , 2) + \ldots + F (h , L)} = T (h) . \tag {13} \end{align*} \end{document}

Monochromatic Subgraph Model. To get a workable form of F(g), it is convenient to expand Eqn. 12 for monochromatic models as: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} F (g + 1 , 1) & = F (g , K) Q (K , 1) + \ldots + F (g , 3 ) Q (3 , 1) + F (g , 2) Q (2 , 1) + F (g , 1) Q (1 , 1) , \\ F (g + 1 , 2) & = F (g , K) Q (K , 2) + \ldots + F (g , 3) Q (3 , 2) + F (g , 2) Q (2 , 2) , \\ F (g + 1 , 3) & = F (g , K) Q (K , 3) + \ldots + F (g , 3) Q (3 , 3) , \\ & \vdots \qquad \vdots \\ F (g + 1 , K) & = F (g , K) Q (K , K) . \end{align*} \end{document}

Then, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} T (g) = \frac {F (g , K) Q (K , 1) + \ldots + F (g , 2) Q (2 , 1) + F (g , 1) Q (1 , 1)} {F (g , K) \sum_ {i = 1} ^K Q (K , i) + \ldots + F (g , 2) \sum_ {i = 1} ^2 Q (2 , i) + F (g , 1) Q (1 , 1)} . \end{align*} \end{document}

Mixed Subgraph Model. Expand Eqn. 12 for mixed subgraph models as: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} F (g + 1 , 1) & \leq F (g , L) Q (L , 1) + \ldots + F (g , 3) Q (3 , 1) + F (g , 2) Q (2 , 1) + F (g , 1) Q (1 , 1 ) , \\ F (g + 1 , 2) & \leq F (g , L) Q (L , 2) + \ldots + F (g , 3) Q (3 , 2) + F (g , 2) Q (2 , 2) + F (g , 1) Q ( 1 , 2) , \\ F (g + 1 , 3) & \leq F (g , L) Q (L , 3) + \ldots + F (g , 3) Q (3 , 3) + F (g , 2) Q (2 , 3) + F (g , 1) Q (1 , 3) , \\ & \vdots \qquad \vdots \\ F (g + 1 , L) & \leq F (g , L) Q (L , L) + \ldots + F (g , 3) Q (3 , L) + F (g , 2) Q (2 , L) + F (g , 1) Q (1 , L) . \end{align*} \end{document}

Back to Computations. Then for both models (see Eqn. 18 in Appendix), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} T (g) \geq \frac {F (g , L) + \ldots + F (g , 2) + F (g , 1)} {{\cal O} (N^L) (F (g , L) + \ldots + F (g , 2) + F (g , 1))} = \Omega (N^ {- L}) . \end{align*} \end{document}

5.1.2. Least Common Ancestor with Ancestry (LCAA)

Next we explore the event of the the common ancestor at depth h being the most recent as well, i.e., additionally there is no common ancestor below the depth of h. Recall that the LCAA for the monochromatic subgraph is just the LCA. We handle both the cases together. Let P(h) denote the probability of the LCAA at depth h for a graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$G \in {\cal G}_h$$ \end{document} . In other words, CAA occurs at depth h and has not occurred at a depth < h.

By Lemma 12, the event of occurrence of the LCA at depth h is not independent of the occurrence at h′ ≠ h. This dependence is captured in the following. Let F₁(h) be the number of instances in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal G}_h$$ \end{document} with CAA at depth h and no CAA at all depths < h. Let F₂(h) be the number of instances in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal G}_h$$ \end{document} with no CAA at all depths ≤ h. Then using L from Eqn 2 and using Lemma 9, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} F_1 (1) \geq 1 , \ \ \ \ & F_2 (1) \leq {\cal O} (N^L - 1) , \ \ \ \ \\ F_1 (2) \geq {\Omega} (N^L - 1) , \ \ \ \ & F_2 (2) \leq {\cal O} ((N^L - 1) ^2) , \ \ \ \ \\ F_1 (3) \geq {\Omega} ((N^L - 1) ^2) , \ \ \ \ & F_2 (3) \leq {\cal O} ((N^L - 1) ^3) , \ \ \ \ \\ F_1 (4) \geq {\Omega} ( (N^L - 1) ^3) , \ \ \ \ & F_2 (4) \leq {\cal O} ((N^L - 1 ) ^4) , \ \ \ \ \\ \vdots \ \ \ \ & \vdots \end{align*} \end{document}

Also note that, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mid {\cal G}_h \mid \leq {\cal O} (N^{hL}) . \end{align*} \end{document}

Then for all h ≥ 1, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\bf P} (h) \geq \frac {\Omega ((N^L - 1) ^ {h - 1})} {{\cal O} (N^ {hL})} . \tag {14} \end{align*} \end{document}

6.3.1. Vertices in row g with 1 parent

Consider two adjacent rows g and g + 1 with k_g vertices in row g. When a vertex always has exactly one parent, the vertices in row g + 1 can be considered to be monochromatic (for computational purposes).

Set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\bf {\cal Q}_c$$ \end{document} . Consider a set of labels X with |X| = k_g. Also k_g ≥ k_g+1 and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_c (X , k_{g + 1})$$ \end{document} is illustrated below.

Example 3

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_c$$ \end{document} ). Let X_k be such that |X_k| = k. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal Q}_c (X_4 , 1) & = \left\{\begin{matrix}4\end{matrix} \right\} , \\ {\cal Q}_c (X_4 , 2) & = \left\{ \begin{matrix}1 \leq 3 , \\2 \leq 2\end{matrix} \right\} , \\ {\cal Q}_c (X_4 , 3) & = \left\{\begin{matrix}1 \leq 1 \leq 2\end{matrix} \right\} , \\ {\cal Q}_c (X_4 , 4) & = \left\{ \begin{matrix}1 \leq 1 \leq 1 \leq 1\end{matrix} \right\} . \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix} {\cal Q}_c (X_6 , 1) = \left\{\begin{matrix}6\end{matrix} \right\} , \hfill \\ {\cal Q}_c (X_6 , 2) = \left\{ \begin{matrix} 1 \leq 5 , \hfill \\2 \leq 4 , \hfill \\3 \leq 3\end{matrix} \right\} , \hfill \\ {\cal Q}_c (X_6 , 3) = \left\{\begin{matrix} 1 \leq 1 \leq 4 , \hfill \\ 1 \leq 2 \leq 3 , \hfill \\2 \leq 2 \leq 2\end{matrix} \right\} , \end{matrix} \begin{matrix} {\cal Q}_c (X_6 , 4) = \left\{\begin{matrix} 1 \leq 1 \leq 1 \leq 3 , \hfill \\ 1 \leq 1 \leq 2 \leq 2\end{matrix} \right\} , \hfill \\ {\cal Q}_c (X_6 , 5) = \left\{\begin{matrix} 1 \leq 1 \leq 1 \leq 1 \leq 2\end{matrix} \right\} , \hfill \\ {\cal Q}_c (X_6 , 6) = \left\{ \begin{matrix} 1 \leq 1 \leq 1 \leq 1 \leq 1 \leq 1\end{matrix} \right\} .\end{matrix} \end{align*} \end{document}

Set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\bf {\cal Q}_d$$ \end{document} . For partition \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$q_c = i_1 \leq i_2 \leq \ldots \leq i_{k_{g + 1}}$$ \end{document} , let k be the number of distinct values with each repeated \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$l_1 , l_2 , \ldots , l_k$$ \end{document} times. Then the cardinality of set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_d (\cdot)$$ \end{document} is: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mid {\cal Q} _d (q_c) \mid = {k_g \choose i_1} {k_g - i_1 \choose i_2} {k_g - (i_1 + i_2) \choose i_3} \cdots {k_g - ( i_1 + \ldots + i_ {{k_ {g + 1}} - 2}) \choose i_ {{k_ {g + 1}} - 1}} \frac {1} {l_1 ! \times l_2 ! \times \ldots \times l_k !} . \tag {15} \end{align*} \end{document}

Example 4

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_d$$ \end{document} ). Let k_g = 6 and X = {u,v,w,x,y,z}. Also, k_g+1 = 4 with the partition q_c = 1 ≤ 1 ≤ 2 ≤ 2. Here l = 2 with j₁ = 2 and j₂ = 2, i.e., the number 1 is repeated two times and 2 is repeated 2 times. Then the number of distinct possibilities are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mid {\cal Q} _d (q_c = 1 \leq 1 \leq 2 \leq 2) \mid = {6 \choose 1} {5 \choose 1} {4 \choose 2} \frac {1} {2 ! \times 2!} = 45. \end{align*} \end{document}

To avoid clutter the set of sets notation is simplified: for example the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} s = \{\{u \} , \{v \} , \{w , x \} , \{y , z \} \} \end{align*} \end{document}

is written simply as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} s = \hbox{u v wx yz}. \end{align*} \end{document}

Then the 45 elements of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_d (q_c = 1 \leq 1 \leq 2 \leq 2)$$ \end{document} are as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix} {\cal Q}_d (q_c) = \hfill \\ \left\{\begin{matrix} \begin{matrix} \rm \hbox{u v wx yz,} \\ \rm \hbox{u v wy xz,} \\ \rm \hbox{u v wz xy,}\end{matrix} \begin{matrix} \rm \hbox{u w vx yz,} \\ \rm \hbox{u w vy xz,} \\ \rm \hbox{u w vz xy,}\end{matrix} \begin{matrix} \rm \hbox{u x vw yz,} \\ \rm \hbox{u x vy wz,} \\ \rm \hbox{u x vz wy,}\end{matrix} \begin{matrix} \rm \hbox{u y vw xz,} \\ \rm \hbox{u y vx wz,} \\ \rm \hbox{u y vz wx,}\end{matrix} \begin{matrix} \rm \hbox{u z vw xy,} \\ \rm \hbox{u z vx wy,} \\ \rm \hbox{u z vy wx,}\end{matrix} \begin{matrix} \rm \hbox{v w ux yz,} \\ \rm \hbox{v w uy xz,} \\ \rm \hbox{v w uz xy,}\end{matrix} \begin{matrix} \rm \hbox{v x uw yz,} \\ \rm \hbox{v x uy wz,} \\ \rm \hbox{v x uz wy,} \end{matrix} \begin{matrix} \rm \hbox{v y uw xz,} \\ \rm \hbox{v y ux wz,} \\ \rm \hbox{v y uz wx,}\end{matrix} \\ \begin{matrix} \rm \hbox{v z uw xy,} \\ \rm \hbox{v z ux wy,} \\ \rm \hbox{v z uy wx,}\end{matrix} \begin{matrix} \rm \hbox{w x uv yz,} \\ \rm \hbox{w x uy vz,} \\ \rm \hbox{w x uz vy,}\end{matrix} \begin{matrix} \rm \hbox{w y uv xz,} \\ \rm \hbox{w y ux vz,} \\ \rm \hbox{w y uz vx,}\end{matrix} \begin{matrix} \rm \hbox{w z uv xy,} \\ \rm \hbox{w z ux vy,} \\ \rm \hbox{w z uy vx,}\end{matrix} \begin{matrix} \rm \hbox{x y uv wz,} \\ \rm \hbox{x y uw vz,} \\ \rm \hbox{x y uz vw,}\end{matrix} \begin{matrix} \rm \hbox{x z uv wy,} \\ \rm \hbox{x z uw vy,} \\ \rm \hbox{x z uy vw,}\end{matrix} \begin{matrix} \rm \hbox{y z uv wx,} \\ \rm \hbox{y z uw vx,} \\\rm \hbox{y z ux vw}\end{matrix}\end{matrix} \right\} . \end{matrix} \end{align*} \end{document}

Wt( · ) function. See Eqn. 3.

Example 5

(on wt(k) function). Let k_g = 3 and X = {x,y,z}. Let q_c = 1 ≤ 2, with q_d = ({x},{y,z}), i.e., k_g+1 = 2. Let N = 4. Then the number of possible configurations is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} wt (2) = {4 \choose 2} = 6. \end{align*} \end{document}

The weight 6 corresponds to the 6 configurations shown below with the labels of row g + 1 implicit by their position (first, second, third or fourth): \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \left| \begin{matrix} \hbox{x yz - -} \\ \hbox{x - yz -} \\ \hbox{x - - yz}\end{matrix} \right| \left. \begin{matrix} \hbox{- x yz -} \\ \hbox{- x - yz} \\ \hbox{- x - yz}\end{matrix} \right| \end{align*} \end{document}

Note that for q_d = ({y, z}, {x}), the 6 possibilities are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \left| \begin{matrix} \hbox{yz x - -} \\ \hbox{yz - x -} \\ \hbox{yz - - x}\end{matrix} \right| \left. \begin{matrix} \hbox{- yz x -} \\ \hbox{- yz - x} \\ \hbox{- yz - x}\end{matrix} \right| \end{align*} \end{document}

6.3.2. Vertices in row g with 1 or 2 parents.

Set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_a$$ \end{document} . In the mixed subgraph, each vertex v of row g has additional information gm(v) of the associated genetic segments (that eventually flow to the extant vertices). If there is only one segment (|gm_j| = 1), then the jth vertex at row g can have only one parent, but if the number of segments is more than one, this vertex could have more than one parent. It is not possible that a vertex has zero parents, i.e., it must have an ascendant (an incoming edge) if it is a vertex in the mixed subgraph.

Example 6

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_a$$ \end{document} ). Let k_g = 3, k_g+1 = 4 with vertex labels x, y, and z (instead of x₁, x₂ and x₃ as in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_a$$ \end{document} definition, thus gm_g,x, gm_g,y, gm_g,z instead of gm_g,1, gm_g,2, gm_g,3) with gm-assignments as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} gm_{g , x} = \{1 , 3 \} , gm_{g , y} = \{4 \} \hbox{and} gm_{g , z} = \{5 , 7 \} . \end{align*} \end{document}

Thus S₁ = {y}, S₂ = {x,z}. Cardinality of C must satisfy the following: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \left(| S_2 | = 2 \right) \geq | C | \geq (k_{g + 1} - k_g = 1) . \end{align*} \end{document}

Thus the three possible C's are: C₁ = {x},C₂ = {z},C₃ = {x,z}.

Case C₁ = {x}: Let S₃ = (S₂ \ C) ∪ S₁ = {y,z}. The possibilities are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} S_{3 , 1} = \emptyset , S_{3 , 2} = \{y , z \} , & \quad X_1 = \{x \} , X_2 = \{x , y , z \} , \quad k_{1 , g + 1} = 1 , k_{2 , g + 1} = 3. \\ S_{3 , 1} = \{y , z \} , S_{3 , 2} = \emptyset , & \quad X_1 = \{x , y , z \} , X_2 = \{x \} , \quad k_{1 , g + 1} = 3 , k_{2 , g + 1} = 1. \\ S_{3 , 1} = \{y \} , S_{3 , 2} = \{z \} , & \quad X_1 = \{x , y \} , X_2 = \{x , z \} , \quad k_{1 , g + 1} = 2 , k_{2 , g + 1} = 2. \\ S_{3 , 1} = \{z \} , S_{3 , 2} = \{y \} & \quad X_1 = \{x , z \} , X_2 = \{x , y \} , \quad k_{1 , g + 1} = 2 , k_{2 , g + 1} = 2.] \end{align*} \end{document}

Case C₂ = {z}: Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$S_3 = (S_2 \setminus C) \cup S_1 = \{x , y \}$$ \end{document} . The possibilities are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} S_{3 , 1} = \emptyset , S_{3 , 2} = \{y , x \} , & \quad X_1 = \{x \} , X_2 = \{x , y , z \} , \quad k_{1 , g + 1} = 1 , k_{2 , g + 1} = 3. \\ S_{3 , 1} = \{y , x \} , S_{3 , 2} = \emptyset , & \quad X_1 = \{x , y , z \} , X_2 = \{x \} , \quad k_{1 , g + 1} = 3 , k_{2 , g + 1} = 1. \\ S_{3 , 1} = \{y \} , S_{3 , 2} = \{x \} , & \quad X_1 = \{y , z \} , X_2 = \{x , z \} , \quad k_{1 , g + 1} = 2 , k_{2 , g + 1} = 2. \\ S_{3 , 1} = \{x \} , S_{3 , 2} = \{y \} & \quad X_1 = \{x , z \} , X_2 = \{y , z \} , \quad k_{1 , g + 1} = 2 , k_{2 , g + 1} = 2. \end{align*} \end{document}

Case C₃ = {x, z}: Let S₃ = (S₂ \ C) ∪ S₁ = {y}. The possibilities are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix}S_{3 , 1} = \emptyset , S_{3 , 2} = \{y \} , \quad X_1 = \{x , z \} , X_2 = \{x , y , z \} , \quad & k_{1 , g + 1} = 1 , k_{2 , g + 1} = 3. \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ & k_{1 , g + 1} = 2 , k_{2 , g + 1} = 2. \\ S_{3 , 1} = \{y \} , S_{3 , 2} = \emptyset , \quad X_1 = \{x , y , z \} , X_2 = \{x , z \} , \quad& k_{1 , g + 1} = 3 , k_{2 , g + 1} = 1. \\\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad & k_{1 , g + 1} = 2 , k_{2 , g + 1} = 2.\end{matrix} \end{align*} \end{document}

Thus for the gm defined in this example, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$| {\cal Q}_e (gm , 3 , 4) | = 12$$ \end{document} .

Set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\bf {\cal Q}_{cdcd}$$ \end{document} . Each configuration \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$q_a \in {\cal Q}_a$$ \end{document} identifies X₁, the vertices in row g that have k_1,g+1 blue parents and X₂, the vertices in row g that have k_2,g+1 red parents in row g + 1. To avoid forbidden structures, the blue and red parents are treated separately, and then the results put together as shown in the example below.

Example 7

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_{cdcd}$$ \end{document} ). For \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$q_a \in {\cal Q}_a$$ \end{document} let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} q_a = (X_1 , k_{1 , g + 1} , X_2 , k_{2 , g + 1}) = (\{x , z \} , 2 , \{x , y , z \} , 2) . \end{align*} \end{document}

Thus, of the three vertices labeled x, y, z in some row g, only vertex y has one parent and the other two have two parents each in row g + 1. In the following we use the simplified notation of the configuration of Example 4. Then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$q \in {\cal Q}_{cdcd} (q_a)$$ \end{document} with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} q = q_1 \cup q_2 = ({x \ z \ x \ yz}) , \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} q_1 & = (\hbox{x z}) \ \in {\cal Q}_{cd} (X_1 , 2) , \\ q_2 & = (\hbox{x yz}) \in {\cal Q}_{cd} (X_2 , 2) . \end{align*} \end{document}

Set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\bf {\cal Q}_b$$ \end{document} . Recall that each configuration of the last step (with X₁ and X₂) implicitly assigns the number of ascendant edges on each vertex u in row g. If vertex v at row g has only one ascendant (incoming edge) e then gm(e) is assigned gm_g,v. If vertex u at row g has two ascendants e₁ and e₂ then the segments of gm_g,v are split into two nonoverlapping subsets gm(e₁) and gm(e₂) with gm_g,v = gm(e₁) ∪ gm(e₂). Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_b$$ \end{document} denote all the distinct possibilities (as shown in the example below). \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal Q}_b ({q \in {\cal Q}}_{cdcd}) = \{ gm \, | \, gm \ is \ the \ genetic \ material \ annotations \ for \ q \}. \tag{16} \end{align*} \end{document}

Example 8

(on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\cal Q}_b$$ \end{document} ). Let denote a descendant edge from a blue vertex in row g + 1 to a vertex in row g and denote a descendant edge from a red vertex in row g + 1 to a vertex in row g. The genetic segments in gm( · ) is displayed next the vertices (x, y, z in row g) and the edges in the examples below. Consider the following configuration: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} X_1 = \{x , y \} , X_2 = \{x , z \} , k_{1 , g + 1} = 1 , k_{2 , g + 1} = 2. \end{align*} \end{document}

The different possibilities of genetic material assignment to the vertices with two parents is shown here.

(1)–(4) model recombination event and (5)–(6) model gene conversion event at node labeled x. Then the (unique) gm_g+1 annotation for case (1) above shown in (c) below with labels of vertices in row g + 1 as {t,u,v} (for convenience, incident edges on blue parents is shown in blue in (a) and incident edges on red parents is shown in red in (b)):

Note that handling blue and red parents separately ensures that there are no forbidden structures (Fig. 2) between rows g and g + 1.

Lemma 13

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {\cal S}_{k_0 , k_1.k_h} \odot {\cal Q} (k_h , k_{h + 1}) \leq | {\cal S}_{k_0 , k_1.k_h} | Q (k_h , k_{h + 1}) . \end{align*} \end{document}

Thus for the mixed model, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} F (g + 1 , k) = \sum_{i = 1}^{L} {\cal F} (g , i) \odot {\cal Q} (i , k) \leq \sum_{i = 1}^{L} F (g , i) Q (i , k) . \tag{17} \end{align*} \end{document}

Also (see Eqn 13), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} T (g) &= \frac {{\cal F} (g , L) \odot {\cal Q} (L , 1) + \ldots + {\cal F} (g , 1) \odot {\cal Q} (1 , 1)} {\sum_{i = 1}^L {\cal F} (g , L) \odot {\cal Q} (L , i) + \ldots + \sum_{i = 1}^L {\cal F} (g , 1) \odot {\cal Q} (1 , 1)} \\ & \geq \frac {\left( F (g , L) + \ldots + F (g , 1) \right)} {{\cal O} (N^L) (F (g , L) + \ldots + F (g , 1))} . \tag {18} \end{align*} \end{document}