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

Monojit Choudhury, Niloy Ganguly, Abyayananda Maiti, Animesh Mukherjee, Lutz Brusch, Andreas Deutsch, Fernando PeruaniPhysical 2010 · DOI · arXiv

Abstract

Genes and human languages are classic examples of discrete combinatorial systems (DCSs), where a finite "alphabet" of elementary units—such as codons in DNA or phonemes in language—combines to form a virtually infinite variety of higher-order structures. This paper introduces Alphabetic Bipartite Networks ($\alpha$-BiNs) as a rigorous mathematical framework for modeling these systems. By extending analytical findings for ABNs, the authors investigate the growth mechanisms of real-world DCSs, specifically the codon-gene and phoneme-language networks. The study reveals that the popularity of basic units follows a family of beta distributions, providing a powerful tool to infer whether a system evolved through rigid preferential attachment or random mutation.

Introduction: The Logic of Combinatorial Systems

Most network science research focuses on "growing" bipartite networks where both sets of nodes increase over time (e.g., new actors joining new movie projects). However, many fundamental systems possess one fixed partition. In genetics, the "alphabet" of 64 codons is essentially fixed, yet the number of genes is vast and continues to expand through evolution. Similarly, in linguistics, the set of phonemes remains relatively stable while the number of possible words and languages is virtually limitless.

The authors address the lack of analytical models for these systems, termed Alphabetic Bipartite Networks ($\alpha$-BiNs). The central question is whether the degree distribution—how frequently each "letter" in the alphabet is used—can be predicted based on the system's growth rules.

Representation of a Discrete Combinatorial System (DCS) as an Alphabetic Bipartite Network (ABN).

Theoretical Framework and Methods

An $\alpha$-BiN consists of two node sets:

  1. Partition $U$ (The Alphabet): A fixed, finite set of $M$ elementary units.
  2. Partition $V$ (The Combinations): A set that grows as new combinations are added over time.

The researchers propose a growth model driven by preferential attachment with a tunable randomness parameter ($\gamma$). In this model, a new combination node $v$ connects to a subset of alphabet nodes $u \in U$. The probability of connecting to a specific unit depends on its current popularity (degree). A high $\gamma$ indicates strong preferential attachment (a "rich-get-richer" effect), while a low $\gamma$ suggests more random selection.

A key theoretical contribution of this work is the derivation of exact evolution equations for parallel attachment, where a new combination node connects to multiple alphabet nodes simultaneously. This generalizes previous models that were limited to sequential, one-by-one attachment.

Empirical Validation: Codons and Phonemes

The authors tested their theory against two distinct real-world datasets:

  • CoGNet (Codon-Gene Network): Analysis of 8 organisms, from the bacterium Myxococcus xanthus to Homo sapiens, using the Codon Usage Database.
  • PlaNet (Phoneme-Language Network): Analysis of the UCLA Phonological Segment Inventory Database (UPSID), encompassing 317 languages and 541 distinct consonants.
Degree distributions of alphabet nodes in real-world systems: (a) CoGNet for H. sapiens and (b) PlaNet.

Key Insights

The Emergence of Beta Distributions

The study proves that the degree distribution of alphabet nodes asymptotically approaches a family of beta distributions. Depending on the randomness parameter $\gamma$, these distributions can manifest as normal, exponential, or even U-shaped curves.

Evolutionary Complexity vs. Randomness

In the CoGNet analysis, a striking trend emerged: "simpler" or evolutionarily older organisms (like soil-living amoeba) exhibit higher $\gamma$ values, indicating highly preferential codon usage. In contrast, more "complex" or recent organisms, such as humans, show much lower $\gamma$ values. This suggests that as evolution progresses, more randomness (mutations) is introduced into how codons are selected for genes.

Language as a "Copy-Paste" System

For the phoneme network (PlaNet), the best fit was found at a high $\gamma$ ($\gamma \approx 14$). This implies that phonological systems evolve largely through a "copy-paste" mechanism, where certain sounds are highly preferred and reused across different language families.

Conclusion and Future Directions

The $\alpha$-BiN framework successfully classifies organisms and languages based on their growth dynamics. While the model accurately predicts the popularity of units, it faces challenges in predicting co-occurrence (which units appear together), suggesting that real-world systems are influenced by additional constraints, such as the "ease of articulation" in speech. Future work may incorporate slowly growing alphabets or non-linear attachment kernels to better capture these nuances.

Summary updated

Abstract

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, 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.
BibTeX
@inproceedings{choudhury2010modeling,
  author = {Monojit Choudhury and Niloy Ganguly and Abyayananda Maiti and Animesh Mukherjee and Lutz Brusch and Andreas Deutsch and Fernando Peruani},
  title = {{Modeling discrete combinatorial systems as alphabetic bipartite networks: Theory and applications}},
  booktitle = {Physical},
  year = {2010},
  doi = {10.1103/physreve.81.036103},
}
Figure