Modeling discrete combinatorial systems as alphabetic bipartite networks: Theory and applications

Genes and human languages are discrete combinatorial systems (DCSs), in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence, and letters or words in a language. Different combinations of these finite units give rise to potentially infinite numbers of genes or sentences. This type of DCSs can be represented as an alphabetic bipartite network (ABN) where there are two kinds of nodes, one type represents the elementary units while the other type represents their combinations. Here, we extend and generalize recent analytical findings for ABNs derived in [Peruani et al., Europhys. Lett. 79, 28001 (2007)] and empirically investigate two real world systems in terms of ABNs, the codon gene and the phoneme-language network. The one-mode projections onto the elementary basic units are also studied theoretically as well as in real world ABNs. We propose the use of ABNs as a means for inferring the mechanisms underlying the growth of real world DCSs.

Figure 1

DNA modeled as a bipartite network (ABN). The set $U$ consists of 64 codons, whereas the collection $V$ of genes is virtually infinite. Multiple occurrences of a codon in a gene have been represented here by multiedges. For instance, the codons “ACG” and “AAU” have, respectively, 2 and 3 edges connecting to the node ${\text{gene}}_3$. Alternatively, this could have been represented by single edges with weights 2 and 3.

Figure 2

(Color online) Comparison for random attachment $\left(\gamma =0\right)$ between the numerical integration of Eq. (7) (solid black curve) and stochastic simulations (blue circles). Circles correspond to average over 500 simulations. In both figures $N=100$. (a) corresponds to $\mu =20$ while (b) to $\mu =40$. The dashed red curve corresponds to the approximation given by Eq. (8). The inset in (b) shows in log-log scale the deviation between Eq. (8), the integration of Eq. (7), and simulations.

Figure 3

(Color online) Comparison for strong preferential attachment $\left(\gamma \ge 1\right)$ between the integration of Eq. (7) (solid black curve) and stochastic simulations (blue circles). Blue circles correspond to an average over 500 runs. In both figures $N=100$ and $\mu =40$. (a) corresponds to $\gamma =1$ while (b) to $\gamma =16$. The dashed red curve in (a) indicates the approximation given by Eq. (8), which falls out of the range of the figure in (b).

Figure 4

(Color online) Comparison between stochastic simulations for the one-mode projection (blue circles) and Eq. (9) (solid black curve). In both figures $N=500$ and $\gamma =1$. Blue circles correspond to averages over 1000 simulations. In (a) $\mu =5$ while in (b) $\mu =15$.

Figure 5

(Color online) Comparison between stochastic simulations for the one-mode projection at different times (symbols) and Eq. (13) (solid curves). In (a) $\tau =0$, $N=1000$, $\mu =5$, $\gamma =1$. The blue circles and the red (light gray) curve correspond to $t=20$, while the blue squares and the black curve to $t=100$. The slight deviation of the simulation results from the theoretical predictions is due to the rounding of the values. In (b) $\tau =10$, $N=100$, $\mu =20$, $\gamma =1.5$. The blue circles and the red (light gray) curve correspond to $t=50$, while the blue squares and the black curve to $t=100$.

Figure 6

(Color online) Degree distribution of the codon nodes for Xenopus leavis. In (a) a comparison between the empirical data (blue circles) and the theoretical $p_{k,t}$ obtained using Eq. (8) (black solid curve) is shown. The cumulative distribution of the real data (blue circles) and the theory (black solid curve) are shown in (b).

Figure 7

(Color online) Error as defined by Eq. (15) as function of $\gamma$ for the eight organisms using fixed bin size. Steps in $\gamma$ correspond to 0.01.

Figure 8

(Color online) Cumulative degree distributions for the empirical data (blue circles) and their corresponding theoretical best $\gamma$ fits through Eq. (8) (solid black curve) for the organisms. (a) Myxococcus xanthus, (b) Dictyostelium discoideum, (c) Plasmodium falciparum, (d) Saccharomyces cerevisiae, (e) Xenopus laevis, (f) Drosophila melanogaster, (g) Danio rerio, and (h) Homo sapiens.

Figure 9

Illustration of the phoneme-language ABN (referred in the figure as PlaNet) and its corresponding one-mode projection (referred as PhoNet).

Figure 10

(Color online) Cumulative degree distribution of $U$, i.e., the consonant nodes. Red squares correspond to the empirical data and the solid black line corresponds to the theoretical solution obtained through integration of Eq. (6) with $\gamma =14$.

Figure 11

(Color online) Cumulative degree distribution of the one-mode projection. Red squares correspond to the empirical data, while the solid black curve refers to the theoretical approximation.