Relationship between Ploidy, Alleles and Genotypes

Introduction

The VCF format encodes genotypes by the index of the enumeration of genotypes give a ploidy number and alleles. This allows for direct access to a genotype value within an array particularly when one works with genotype likelihoods.

Motivation

Plants species exhibit a diverse number of ploidy, for example, the strawberry is an octoploid and the pear is a triploid.

While there are explicit functions that could be googled for handling haploid and diploidy cases. It seems to be difficult to find the closed forms for the general case. This wiki fills in that need.

The number of genotypes given a ploidy and alleles

${\begin{aligned}F(P,A)={\begin{cases}{\binom {P+A-1}{A-1}}&,A<P\\\sum _{i=1}^{P-1}{\binom {A}{i}}{\binom {P-1}{i-1}}+{\binom {A}{P}}&,A\geq P\end{cases}}\end{aligned}}$

where P is the ploidy number and A is the number of alleles.

The indexing of genotypes given a ploidy and alleles

${\begin{aligned}G(a_{1},..,a_{p})={\begin{cases}a_{1}&,p=1\\F(a_{p},p)+G(a_{1},..,a_{p-1})&,p\neq 1\end{cases}}\end{aligned}}$

where a_1, a_2 .... are the alleles in numeric encoding (0 to A-1) and are ordered (AB, ABCCCC). For example ACB is not ordered.

Simple cases

Ploidy	Alleles	Genotypes	Index
1	A	$F(1,A)=A$	$G(a_{1})=a_{1}$
2	A	$F(2,A)=A+{\binom {A}{2}}$	$G(a_{1},a_{2})={\binom {a_{2}+1}{2}}+a_{1}$

Derivation for counting the number of genotypes

For the case where A < P, there must always be P observed alleles and there can only be at most A alleles. This can be modeled by P+A-1 points where you choose A-1 points to be dividers to define the alleles. Thus the number of ways you can observe this is ${\binom {P+A-1}{A-1}}$.

For the case where A >= P,

${\begin{aligned}F(P,A)&=\sum _{i=1}^{P}\|\{{\text{i distinct alleles observed in a set of P alleles}}\}\|\\&=\sum _{i=1}^{P-1}\|\{{\text{i distinct alleles observed in a set of P alleles}}\}\|+\|\{{\text{P distinct alleles observed in a set of P alleles}}\}\|\\&=\sum _{i=1}^{P-1}\|\{{\text{i distinct alleles observed in a set of P alleles}}\}\|+{\binom {A}{P}}\\&=\sum _{i=1}^{P-1}\|\{{\text{no ways to choose i distinct alleles}}\}\|\|\{{\text{no ways to arrange i distinct alleles in a set of P alleles}}\}\|+{\binom {A}{P}}\\&=\sum _{i=1}^{P-1}{\binom {A}{i}}{\binom {P-1}{i-1}}+{\binom {A}{P}}\end{aligned}}$

Derivation for indexing the number of genotypes

An important observation here is that the enumeration of a A alleles for a given P ploidy, the enumeration of A-1 alleles for P ploidy is a subsequence.

a_1, ... a_P is ordered and indexed 0 to A-1. Clearly when P = 1, the enumeration is of the genotypes is trivially the same as the allele.

when P > 1,

${\begin{aligned}G(a_{1},..,a_{P})&=\|\{{\text{genotypes of }}a_{P}{\text{ alleles for ploidy P}}\}\|+G(a_{1},..,a_{P-1})\\&=F(a_{P},P)+G(a_{1},..,a_{P-1})\end{aligned}}$

This gives a recursive relationship that is a chain of P-1 calculations.

Algorithm for enumerating the genotypes given A ploidy and alleles

   uint32_t no = 0 // some global variable
   void print_genotypes(uint32_t A, uint32_t P, std::string genotype)
   {
       if (genotype.size()==P)
       {
           std::cerr << no << ") " << genotype << "\n";
           ++no;
       }
       else
       {
           for (uint32_t a=0; a<A; ++a)
           {
               std::string s(1,(char)(a+65));
               s.append(genotype);
               print_genotypes(a+1, P, s);
           }
       }
   }